2015年3月23日 星期一

VK Cup 2015 - Round 1

※ 本篇不含題解,只有簡單記錄一下比賽心得,方便以後搜尋及回憶

= = = = = = = = = = = = = =

馬上就毀了不久前說的 V 字形目標 XD

這場比賽無疑是我寫解題報告至今最簡單的一場Div. 1比賽,可是我出太多包了就掛掉了 Orz 總覺得當我有明確目標的時候就一定會爆炸 ... (看看我至今為止進不了任何 online round)。

這場比賽有幾個特殊的地方:1. 難度沒有按照順序排 2. Codeforces 第一次採用以 250 分為間隔的動態分數。

Problem B --- Group Photo 2 (online version)

tag:[ 枚舉 ][ greedy ]
關鍵字:矩形橫擺直擺

賽前我並不知道題目沒有按照難度排,但尤於求攻心切就先開了 pB (自負能以差不多的時間寫完 A 和 B),但是大概是太急躁了 ... 過了三分多鐘我都還沒看懂題目,在想要不要先回來讀 A 的題目時先看了一下 scoreboard,看了感到非常莫名, pA沒有人上傳,倒是 pE 有少數幾隻貓上傳 ... 這時心裡猜想或許 pE 是 well know 的難題才會發生這種事?於是決定繼續試圖理解 pB,終於理解意思後,立刻把這題連想到我曾經在 Topcoder SRM629 出的 Div1 250 都是橫擺或直擺的矩形問一些事情,馬上就會做了。

Problem E --- The Art of Dealing with ATM

tag: [搜索]
關鍵字:零錢

pB 過了 pretest 後看了 scoreboard,發現有大量的人傳了 pE,以及少數人傳 pB,但沒有人傳 p ,於是我開始相信這場難度沒有按照順序排,但看完 pE想了一下後並不知道怎麼做 ...,賽後看了別人 AC 的 code 才發現我看錯題目了。我沒有看到題目說的每次提領的錢至多只能提領兩種幣額的限制,賽中我不時回來思考這題,花了不少時間。

Problem D --- Social Network

tag:[貪心]
關鍵字:區間貪心

雖然 pE 卡住了,但是一直卡下去很不妙,所以就繼續開其他題,這題題目對我來說也是很難讀懂,但也是讀懂後就會做了,而且 code 很簡短,一個 for 迴圈掃過去就結束了。在我感覺上這題只有一般 Div. 1 B 以下的程度。

Problem A --- And Yet Another Bracket Sequence

tag:[字串比對][ 資料結構 ]
關鍵字:合法括弧

這題我也是看完題目後就會做了,但是覺得可能還會有比這題好寫的題目,在寫這題前先去看了 pC。

Problem C --- Rooks and Rectangules

tag:[ offline ] [ 資料結構 ]
關鍵字:矩形區域類資料結構

這題我倒是沒有讀完題就知道怎麼做 ...,應該說我第一個想到的做法有點困難,但看別人 AC這題的速度大概可以知道這題有更簡單的方法,但我覺得比起去思考更簡單的方法,還是去抄抄 codebook 寫 pA 會比較容易。賽後多想個幾分鐘就想到簡單的做法了。

我複製了 suffix array 和線段樹求 RMQ 的 codebook 迅速的寫完 pA, 但是之後一直 WA 在 pretest 第 12 組,直到賽末。賽中一直 de 不出 bug 時超心急的,我已經好久沒有卡 bug 卡那麼久了,我覺得 code 完全有按照我的思考寫啊!當下覺得要不是我想到的做法是錯的,要不然就是我的 codebook 有錯,可是無論重新檢視自己的做法證確性多少次,都還是覺得是對的,並且我那兩份 codebook 都用了好多次了。又重新看了幾次這份 code 我沒抄 codebook 的部分,都找不到錯誤,過程中索性先回去繼續想 pE 轉換情緒幾次,但也都處處碰壁。直到最後,沒有奇蹟。這場比賽我以兩題作收。

事後沉澱下繼續找 bug,當時心想,要是真的是 codebook 有 bug 的話那還蠻糟糕的,所以也幫抄 codebook 的部分 debug,然後就發現我的 bug 了...,原來我的 RMQ codebook 只當所有數是非負才會對 ...,把這部份修過後重上傳,在第 14 組 test TLE 了...,這也太崩潰 Orz 這代表就算我 RMQ 的 codebook 沒有 bug,我也一定無法 AC 這題 ...。難道我的方法太慢了嗎?我看了一下別人的 AC code,複雜度也和我一樣呀!也是一個 suffix array加一個 O(n log n) 的資料結構,我在測了一下我的 code,發現在 suffix array 的部分就 TLE 了 ...,這是怎樣,這已經是過去我把我自己寫的 suffix array code換成對友寫的快我幾倍的 code耶,結果還是不夠快 Orz,最後我去複製了一分別人 AC 的 code 裡的 suffix array 的部分蓋掉我用的 suffix array,終於 AC了。

雖然 rating 大降,不過這場收穫算是很多吧,把我的suffix array codebook 變得更快,以及除掉 codebook 裡的其中一個潛在 bug。不過上一篇 BLOG 裡寫的目標失敗了還是令人非常傷心 OAQ