POJ 2826 - An Easy Problem?!

A geometry problem. Not complex, but need to be careful and it is easy to miss some cases.

First, there are some conditions that the answer will be 0.00
1. Either one segment is horizontal
2. The segments have no intersection
3. The segments are parallel

If the segments passed those cases, then find the intersection point P of the segments.
The area will be a triangle.



However, there are one more case that needed to be consider.

URAL 1124 - Mosaic

Solution

Model the solution to a graph.
Each box is a vertex, and if box x has a piece with color y, add a directed edge (x, y).
Then, the number of movement is the number of edges plus the number of jumping to another node.

If the graph is undirected, then what we need to do is count the number of odd degree node. (211 homework!)
However, since there are equal number of pieces for all colors, that means for all node x, the number of incoming edges = number of outgoing edges.
That means the number of jumping required = number of connected component - 1

Overall time complexity = O(|V|+|E|) = O(M²)

URAL 1077 - Travelling tours

Solution

First, the number of tours = |E| - |V| + |C|, where |C| is the number of connected component.
The algorithm will explain it.

For each connected component, find an arbitrary spanning tree.
For each back edge (u,v) in the spanning tree, the back edge (u,v) + the tree edge connecting u to v forms a cycle.
Since the back edge is used only in this cycle, it is a valid tour.

Hence the number of tours = the number of back edges = |E| - number of tree edges = |E| - |V| + |C|.

This is optimal because after we create a spanning tree, each cycle must include some back edges.

USACO DEC10 Threatening Letter

這是 USACO DEC10 GOLD division 的題目, 據說提交率/通過率很低
不過說穿了其實不難, 只是看對 Suffix Array 的運用是否熟練

題目大意是, 給出兩條 string A, B
現在可以不斷 copy 出 A 的一段 substring, 問最少要 copy 多少次去砌出 B
N ≤ 50000

首先想到的是很 greedy 地砌出 B, 即在 A 中選出和 B 的 prefix 有最長 common prefix 的suffix
所以就要用 suffix array
題解 suggest 了兩種做法

1. 設 S = A+B, 對 S 做 suffix array, 然後每次在 S 中 process
2. 對 B 做 suffix array, 然後不斷做 binary search

由於我覺得方法 2 好像在 worst case 中會達到 O(N² lg N), 所以很理所當然的用了方法1
每次找出 B 由 current 開始的 prefix 與 A 的 suffix 中最長 LCA 的一條
即是在 SA[] 中, 分別向上和向下找出第一條在 A 開頭的suffix

版本1 我是真的向上下掃一次的, 其實理論上應該會去到 O(N²), 不過還是水過了
版本2 對每條在A開始的 suffix 中向上下掃, O(N) preprocess (case 10 run 了 300ms)

POJ 3415 Common Substrings

做做下竟然要用到尋日果個data structure!
真不知是巧合還是甚麼

很正路的先compute S=A+B 的suffix array和計算height array
然後數法就是對於每一條在A開頭的suffix去數map到幾多條B開頭的, 分別向上和向下掃一次
所以就要用昨天的data structure去計算了, 因為LCP在SA中是decreasing的

題外話
我的O(N lg N lg N) 武器 run 了 34xx ms
但貼左個 O(N lg N) 的就變成 18xx ms了

COCI 2010/2011 Contest 3

香港時間2200-0100..!
十分合適我的生理時鐘

Q1-Q4: 頹
Q5: 望下去很有趣, 直覺會想到
最後還是做到了, 方法大概是

計算的次序:
1: [1,1]
2: [1,2],[2,2]
3: [1,3],[2,3],[3,3]
4: [1,4],[2,4],[3,4],[4,4]
..

首先想到的是每一個range都儲著max和min
做到第i步時, 把a[i]和每一個range的max和min比較和update, 再把每一個range的(max-min)加落answer

但續個range計和update是O(N²), 所以運用了一個很trivial的fact:
(max[1]-min[1])+(max[2]-min[2])+...+(max[n]-min[n]) = (max[1]+max[2]+...+max[n])-(min[1]+min[2]+...+min[n])

即是, 每一步儲著兩條list: max list 和 min list
而這條list要support以下operation
1. Push(x) - change all elements smaller than x to x
2. Sum() - sum of all elements

然後就想到條list其實就是一條類似stack的東西, 而每一個entry儲著frequency和value, 其中value是increasing/decreasing的
每一次Push(x)就一直pop走大於x/小於x的entry, 並累計frequency, 最後push返落條list度, 途中maintain Sum
由於每一個entry只會入/出條stack一次, 所以整個算法為O(N)

Q6: 未想到, 暉好像想到, 其實這樣挺好的, 因為如果我們一隊的話便可以把所有題目solve了(想像)

ACM ICPC 2010 - Kaohsiung 戰記

照舊是由我分題目。這次只有一份題目, 和training的時侯一樣。分好後便設定好vim, gedit等環境, 這次用的是Linux, 加上keyboard十分順手, 令打字速度提升了10%。一開始看到J, 立即發現是很簡單的動態規劃, 便上機了。寫到一半呀暉告訴我A是赤裸裸的最大生成樹, 加上看到不少隊伍過了A, 便先寫A, 秒殺之。

24 min - Problem A - MST (1Y ; GagGuy)

過了後繼續寫J, 過了樣例便提交, 返回WA。此時whh的F可以做, 是很經典的二分圖匹配, 便換他上機。不久, 發現了J的錯處, 改之, 第2個Yes。

37 min - Problem J - DP (2Y ; GagGuy)

過題後呀暉問了我題D的一些東西, 和最近點對有關, 我便告訴他中大一直以來的做法, 便列印whh的F並由呀暉做D。我便隨手拿起G看看, 原來是prufer code, 211才剛學完, 不過不太肯定做法, 便先用樣例來試驗。過了不久, 便傳來呀暉射鵰的聲音。

50 min - Problem D - Closest pair (1Y ; Fai)

此時whh也找到F的錯處了。我便找呀暉討論一下G, 確定了做法。本來我打算寫的, 但是呀暉告訴我B是一條計算幾何的題目, 我想用些時間準備一下, 便很放心的把G交給呀暉。同時, whh的F也過了。

56 min - Problem F - Bipartite matching (1Y ; whh) 

B是一條和判斷相似圖形有關的題目。由於數據很小, 應該可以用很直觀的方法做。於是便先計劃一下怎樣寫。不久, 便傳來第5個Yes。

64 min - Problem G - Prüfer code (1Y ; Fai + GagGuy)

由於頭5條都做得頗順利, 使我們一度在scoreboard上稱霸。此時的分工是由我做B, 呀暉做E - 一條頗麻煩的題目, whh看H - 一條很長的題目。準備了一會後, 我便開始寫B。寫的過程不算順利, 很多細節要處理。因此中途先給呀暉做E。然後就開始卡題了。我的B和呀暉的E都不斷返回WA, 眼見其它大學不斷超前我們, 而我們又沒有題可以過, 使我十分焦急。幸好, 呀暉的E在第3次提交時通過了。

172 min - Problem E - Ad Hoc? (3Y ; Fai)

我繼續做B, 而呀暉和whh聯手看H。H是一條graph題, 但看似不簡單。這時我才發現理解錯了B的題意, 但更改也不算太麻煩。可惜仍是返回WA。此時他們的H想到了做法, 便先給他們寫H, 可惜又返回WA。此時剩下一小時多一點, 已經有不少隊伍9題, 我們又卡了2題, 使我再一次十分著急, 便先出去吃東西冷靜, 並整理了一下思路, 決定換另一種方法寫B。而他們再看一次H後, 發現好像理解錯了, 把題目深化了很多。回來後重新寫B, 並處理了有重點的case, 但仍是WA。幸好, 在封board後18分鐘, 我們的H在更改後通過了。

258 min - Problem H - Shortest Path (2Y ; whh)

剩下40分鐘, 而我又覺得B差一點就能過了, 呀暉的C好像又很有想法, 使我一度想過上9題的希望。接下來的時間都是我和呀暉交替寫B和C, 可惜最後B仍是不能通過, C則不夠時間完成。最後以7題結束, 排名12。

ACM ICPC 2010 - Jakarta 戰記

這是 IsolatE 有史以來最發揮到 teamwork，很認真也很開心的一場 acm。
Scoreboard : http://competition.binus.ac.id/icpc/result/final.html


一開始便夾好了由我分題目，自己分到了數條graph的題目。通常 A 較簡單，但一看 A，怎看也很難，先放下。然後看看 B，二叉樹計數，直覺是動規規劃。這時whh已差不多完成 C。再想了一會 ，whh 便作出了比賽的第一個提交，發現是全場第一個提交，1Y。我接著上機做 B，但再想一想，發現有些地方不清楚，便先給呀暉做 D。然後看到 F，疑似是強連通分支，這時呀暉提交了 D，WA。此時 whh 可以做 I，不久呀暉發現 D 的錯，第2個Yes。緊接著 whh 的 I 也很快 1Y了。輪到我上 F，很熟練的寫出強連通分支，寫完提交，WA。 然後想起SCC收縮後形成的是有向無環圖，我卻當成了樹，很低級的錯誤，修改，第4個Yes。之後呀暉上機寫I，我則看whh給我的E，也是和樹有關的題目，十分合我的口味。一開 始想到了輕重邊割分，但細心想，可以用簡單的 DFS+LCA 代替。不久，呀暉完成 J，提交，WA。在等待列印的時侯，我上機寫 E，由於有武器的關係，很快便完成，過不了樣例，由於未有其它題目可以上機，因此可以很奢侈的輸出訊息除錯。中途呀暉發現 J 的錯，第5個Yes。發現找LCA出錯了，但又找不到是哪裏錯。時間一秒一秋的過去，終於發現打少了一個分號，眼殘了。改回，立即過樣例，提交，1Y，第6個Yes。和whh討論B，呀暉則研究A。B的動態規劃是O(N^3)，應該超時，因此遲遲未敢上機。whh指出總時間應該會是O(N^2) ，於是便開始寫了。寫到一半覺得很多細節，便先讓給呀暉做 A，中途whh 發現可以最後才乘以C(m,n)，把動態規劃降為O(N)! 這時想起武器中有求C(n,r) mod P 的快方法，便很興奮的打下去。這時和上一次過題目差不多一小時了，有點焦急。過樣例，提交，返回RE。和whh一起除錯，同時呀暉提交的 A 也 WA了。這時兩題也卡了，有點危機的感覺。試了一個case，發現迅速RE了。原來理解錯了武器中的參數，立即修改，擔心了一會long long的問題，這時呀暉的 A 也改好了，不久我也提交 B，出現第 7 和第 8 個 Yes。剩下兩題，一題是有點難的數學題，另一題竟是training中見過的AC自動機+DP，但我沒有太大信心可以寫出。這時分工是 whh 和呀暉想 G，我想 H。需然知道 H 解法的大概思想，但很多細節也很麻煩，預計在比賽中做到的可能性不高。不久後便封board了。差不多時侯他們的 G 也可以寫了，呀暉和whh每人負責一部份，不久便完成了。提交，TLE。想辦法優化，再改，再試，第2個TLE。這時大約餘下20分鐘，焦急，再改，再試，再提交。最後，第9個Yes就出現了(293+3)。興奮得跳了起來。最後以9題結束。後來得知冠軍也是9題，就感到有些可惜，如果之前做回training時做不到的那題AC自動機的話，我有信心在半小時內完成 H，不過比賽就是會有遺憾的。

HKOI 2011 Final Event Detail

Final Event

Date:	Saturday, 4th December, 2010
Registration Time:	Senior Group: 8:30 a.m. Junior Group: 1:30 p.m.
Event Time:	Senior Group: 9:30 a.m. - 12:30 noon Junior Group: 2:00 p.m. - 5:00 p.m.
Venue:	Rm924, Ho Sin Hang Engineering Building, The Chinese University of Hong Kong, Shatin, Hong Kong.

SPFA: Negative Cycle

剛發現原來一直寫錯 SPFA 中的 detect negative cycle
以前一直以為是 update ≥ N 次則有負圈
實則是 入queue ≥ N 次
因為每入一次 queue, 就表示 shortest path 所經的 edge 數 +1
由於無負圈的 shortest path 最多只走 N-1 條 edge, 所以入 queue ≥ N 次 = 有負圈

Team Training 10/11/2010 - Harbin 2010

POJ 2152 Fire

Problem statement

Given a undirected tree, each vertex can be selected or not. The cost is defined as:

If vertex x is selected, cost = prize[x]

If vertex x is not selected, cost = distance to the nearest selected vertex

In addition, for each vertex x, the distance to the nearest selected vertex must <= distance[x]
Find the minimum cost, |V| <= 1000

Solution

其實都幾 obvious 係 dp on tree
不過個 state 比較難諗

dp[x][y] = minimum cost for subtree rooted at x, with the nearest vertex is y

就係個 state
進行 state transfer 時, 主要分的 case 為
1. y 在 x 的 subtree
2. y 不在 x 的 subtree
(畫下就可以推到)

time complexity = O(N²)

類似方法應該可以解決 Hsinchu 2009 的 D

Size Balance Tree vs Segment Tree

假設想有一個data structure, 想support:

1. add(x)
2. rank(x)
3. delete(x)

在O(log N)時間內做到

做法可以用陳XX的Size Balance Tree, 不過個人覺得code很長, 在爭分奪秒的ACM上, 用 segment tree 代替可能更好

先把所有 data discretize
(不過可能就要store起所有query.. um..)

揼個 segment tree, 每個 node store sum = left subtree's sum + right subtree's sum
leaf's sum initialize = 0

每次add(x) 就把對應的 leaf set 做 1
delete(x) 就 set 做 0
rank(x) 就在途中加起 left subtree 的 sum

劃分樹

Definition

給出一條array A[], 對A[]建立劃分樹可以在 O(log N) 時間內解決
1. query(x,y,k) : 在 A[x..y]中的第k小元素
2. rank(x,y,k) : A[k] 在 A[x..y] 內排第幾

Structure

劃分樹和 segment tree 相似, root 代表 [1,n], 兩個 child 為 [1, n/2], [n/2+1, n]
每一個 node 是一條 array

Root是原本的A[]
然後, 把較少的一半分到 left subtree, 較大的一半分到 right subtree, 而各自的相對次序不變

例如

Root = [3 1 5 4 6 8 2 7]
Left child = [3 1 4 2]
Right child = [5 6 8 7]

同時要記著哪些元素分到了左子樹
以上面為例

[3  2  8  4  6  5  1  7]
[3  2  4  1][8  6  5  7]
[2  1][3  4][6  5][8  7]
[1][2][3][4][5][6][7][8]

Query

對於 query(x,y,k)
可視為 "在 [1,n] 入面 [x,y] 中的第k元素"
然後就要發揮二元樹的精神: 把問題 reduce 做一半

先判斷我們要的答案在 left subtree 還是在 right subtree
就可以把問題 reduce 成
"在 [1, n/2] 入面 [x', y'] 中的第 k' 元素" 或
"在 [n/2, 1] 入面 [x'', y''] 中的第 k' 元素"

那些 x',y',k' 怎樣計出來
方法不外乎利用記了哪些元素分到左子樹

至於 rank(x,y,k), 則原理相近

Implement

為方便起, 先把 A[] 離散化
就可以快速判斷分去 left subtree 還是 right subtree

然後棵 tree 其實是 log N 條 array
因為每一層都要記 N 個element的資料

記錄哪些元素分到了左子樹實際上是記 "在這個 node 中, 每個 element 左邊有多少個分到左子樹"
可用 partial sum 解決之
因為計那些 x', y', k' 等等都要用到 partial sum

其實 code 不長
不過細節很煩, 計 index 的式有 4-5 個 variable
寫了一次後便放入武器庫

SRM 486

300
直接DFS
一開始沒看到先比較length, 以為是直接按lexicographical order, 浪費了一些時間


450
想了一陣覺得memorization dp可行, 時間主要花在coding上
神奇地過到sample, 於是便很有信心地submit


1000
看完題目後很興奮, 因為和CUHK ACM TFT其中一題非常相似
由於有武器, 以division 第二的速度完成了!


種種因素令我在system test前在division排第九


可是..
system test 悲劇了
1000 failed system test
原因竟然是 n=1 的時侯炒了orz... (本來還想一舉破2000的.. 唉)


唉.. 灰鳥
不過結論是, 要保持rating穩步上升, 至少要做到兩題或以上
意外炒了一題也不至於太傷

Team Training 20/10/2010 - Jakarta 2009

Team Training 18/10/2010 - Hangzhou 2008

ZOJ 2676 Network Wars

Problem statement: Given a undirected graph, each edge has a cost c, select k edges to disconnect vertex 1 and N, the goal is to minimize c/k

直覺是 binary search 答案
對每條edge, 如果 cost[x][y] < mid, 則直接選取
對餘下的 edge 做 flow 搵 min cut

算法不難想到, 比較挑戰的是 handle precision
發現有些位寫

R < 1e-8 WA
R <= 0 AC

後來想到可能是因為做 flow 的部份和用 dfs 搵 cut set 的 handle 方法要一致

係段 code 既邊個位用 epsilon 也要小心處理

Team Training 13/10/2010 - Phuket 2009

Training 時做不到 K, 在 Joe 的指點下現在做到了
是帶cost的lower bound flow

Problem statement:
Given a directed graph, each edge has 2 cost: Patrol cost and Video cost. Each edge must be either patrol or video, the in-degree of patrol road must equals the out-degree of patrol road on each node. Some edges are pre-assigned to be patrol road. At least one road must be patrolled.

看下去很多條件..
入度和出度其實implies patrol edge是一個個的cycle
所以題目其實是要找一些patrol cycle 去 minimize total cost

先假設所有edge都是video, 每條edge的cost便是轉為patrol的費用

第一步是滿足有些edge必定是patrol的條件
用lower bound做circulation
先不用理cost, 找一個任意的feasible flow

第二步處理cost
其實就是不斷在residual network找negative cycle
用bellman-ford做時, 要注意即使第V個iteration update了node x 並不implies node x 是在 negative cycle 中

最後處理at least one edge must be patrolled
即係搵minimum cycle
由於沒有限定cycle length一定要>2, 可以直接用floyd-warshall做


做完這題終於搞清了lower bound flow的一些概念
有Source和Sink的graph如果有cycle做lower bound flow是NP的

Team Training 11/10/2010 - SWERC 2006

Team Training 7/10/2010 - NWERC 2004

Team Training 5/10/2010 - Danang 2007

Team Training 29/9/2010 - SEERC 2005

其實打係度好大一個原因係想做返未做到/隊友做的題目.. 不過都積左一大堆了..

Team Training 27/9/2010 - SEERC 2004

Team Training 20/9/2010 - NEERC 2005 Northern Subregion

SRM 483

今次的SRM十分刺激, 過程峰廻路轉

---

Coding Phase

一入房, 沒見到甚麼勁人
分數的分佈是 250 500 900

看完250, 由於 maxDen 十分小, 因此立即想到窮舉 A,B
搞左一輪, 慢慢的解決掉 (203)

之後不知為甚麼想先開 900, 看完題目後感覺不難
但有想過 900 不會這麼簡單, 懷疑佢 valid 的 range 並不是 [x,INF) 的 form, 於是寫左個 program generate test case 試, 得出來的結果又好像 work
又見很多人 submit 了 900, 於是便開始 code, 過程十分順利, 幾乎沒有錯, 過sample便submit了 (636)

由於做到900 心情很好, 便滿有希望地開 500
看完題目第一件想到的是 greedy 唔 work !
呃..
之後朝著 dp 的方向諗, 又真係好似可以用 dp

Define dp[i][left][right] = 第i個有left influence傳去左面和right influence 傳去右面
由於 500+500/2+500/4+... <1000, 所以大約是 N*1000²
看起來很合理, 剩下15-20分鐘, 便很興奮地揼.. 啪啪啪
很順利的把 sample 都通過了, 在完場前3mins submit

Challenging Phase

做500的時侯已經想到很多人會用greedy做500!
所以 intermission 時已經出定 greedy 的 exceptional case
一開
果然有不少一看便知道不正確的方法, 不過估唔到連greedy都有好多種.. 有對 influence greedy 的, 有對影響人數 greedy 的, 有雙重 greedy 的.. 真係諗得出都有

看到一個用"double greedy"的, 睇明佢段 code 再諗左個反例, 由於做左3題, 因此當時很勇敢的 cha 下去

Challenge success

+50! 還想如果3題全過再加上 challenge 的分數就是一場完美的 SRM 了
可是, 突然發現自己的500被cha掉了, 灰哂
不過仍然無阻繼續嘗試cha別人的 code
差不多夠鐘時看到一個肯定錯的, 但又不太明白他在幹甚麼, 於是gen左一個大數據去cha佢, 可惜失敗, -25
最後以剩加分25結束

System test

看divison summary, 很多人都提交了500級900, 其中900的submission比500還要多
而且自己也莫明奇妙的入了頭100(好似係)

system test 開始後不久, 就發覺唔係好妥.. 900果行放眼盡是 failed system test
再看看自己也是同一命運, 但很幸運地有+25 的優勢 (突然變得非常重要, 因為突然大剖份參賽者只pass了250), 居然還可擠進頭100
Rating 的升幅也是近數月來最大的, 而且創了新高

很莫明奇妙的一次SRM

CodeForces Contest #30

題目
Scoreboard

---

很久沒有打 CodeForces 了, 今次見佢係新 style 又夾時間就玩下
server 還是很慢, 但至少還在可接受的程度

所謂的 CodeForces style可以看這

---

題目:

A - Accounting
解 A*Xⁿ = B, 給出 A, B 為 -1000 到 1000 之間的整數, n 為 1 至 10 之間的整數, X 也要是整數

B - Codeforces World Finals
和日期有關的data processing

C - Shooting Gallery
普通的dp

D - Kings Problem?
看起來很有趣, 不過沒有精神去想

E - Tricky and Clever Password
沒看題目..

---

戰況:

今次的題目都比較直接, 不用想很久就有整個算法的 outline
但仔細做的時侯, 發現A有不少地方要小心處理, 所以完成時間比較慢, 而且還要錯了2棍 (有一棍 submit 錯 file )

由於 B 的題目太長因此跳過, 發現 C 是比較簡單, 少 trap 的 dp, 很輕鬆地完成了
看題 B , 其實也不太難處理, 只要小心一點就可以了, 大約一小時完成了三題

由於看到題 D 和 E 比較絕望, 以前的話一早去做其它事
但 CodeForces 的特點之一便是 coding 和 hacking (即 challenge) 是同時進行!

把 3 題都 check 一次便 Lock 起它們 (即不再 resubmit )
才可看別人的 code
看了幾個 A, 都有 overflow 的情況出現, 但找不到數據去炒佢
找到一段 A handle 錯了 X 為負的情況, 見佢幾短便打落自己部電腦試, 勇敢地按下 hack

Successful hacking attempt

+100, ranking 頓升了不少, 發現 hacking 是一個分數的重要來源 (比SRM 的+50分更有影響)
在臨完場時, 又發現有人沒有處理 B%A!=0 的情況, 又多100分

最後排52

---

感想:

比起 SRM, challenging 別人的 solution 的壓力似乎比較小
因為自己的 code 已經 pass 了 pre-test, 對自己的方法有一定信心
而且也不太需要擔心別人搶先 hack 掉, 因為一間房比較多人而且別人不一定在 hack

總括來說 hack 人頗划算的
不過今次要把別人的 code 打來試, 應該更有信心 hack 才是

Team Training 15/9/2010 - NEERC 2004

今次懂做又比較的有趣的是 G 和 H

G - Gunman

其實不是第一次看到這題目, 不過 training 才認真想
turns out 可以分做 x axis 和 y axis 做

y axis 較簡單, 因為 fix 了一點, 只是處理一些 slope
x axis 則較複雜, 但其實是經典問題, 如果存在 valid 的線的話一定可以 rotate 到直至碰到兩點, 所以可以O(N³)解決

做 geom 其實幾有趣的 (如果唔使處理精度)

H - Heapsort

有容易有 idea 但又唔知點 code 那種題..
目標是每次將 1 shift down 到 label 最大的 node
做法先把 heap 的 node label, 每次再把 heap[1] map 返做 pop number

Team Training 13/9/2010 - NEERC 2007 Northern Subregion

時間不足, 只記下有意思的題目吧

C - Crosses and Crosses

game題, 應該要用 sg function, 不過還是未學懂, 遲點要研究一下

D - Domestic Networks

由於以前做過所以由whh做, WA 了很多次也找不到 bug, 最後發現是一個很小但又很容易犯的錯
trace answer 的時侯, 如果 dp[i] 已經能砌到的話則不用再試, 因為可能會 cover 了原本的 path

E - Elevator

做法: 求出 mod a 為 0,1,2..,a-1 中每個能到達的最小數層. 做法類似找 shortest path

G - Given a string

其中一部份是判斷 string A 是否 string B 的 rotation, 用 KMP

H - History of football

部份搜索法, 未過到

SRM 481

在 lab 和大家一起打.. 感覺挺好的

250, 一開頭覺得一頭霧水, 好像很複雜
但後來唔知係咪因為上完2510, 突然想到用linear equations
以一個中等的時間完成 (206.11), 總算是一個好開始..

500, 計 expected value 沒有太信心..
猜測了一個方法, 對住 sample 試了試, 覺得 work 便開始 code

900 有一點想法但時間不足

在 contest 完的時侯, 開了自己的 500 來看看
突然發現有一個位沒有用 long long !
立即「頂」了一聲..

果然在 challenging phase 被 cha 掉了..
同時找找有沒有人和我一樣錯.. 竟然沒有=[
幸好 250 的分數不錯, rank 也不是太差

最後 rating 微升 43..
又浪費了一個升 rating 的機會

---

250

最後用的方法是列方程..
首先分成四種人:

A = 得到答案是 egg 而沒有說謊的人
B = 得到答案是 egg 而說謊的人
C = 得到答案是 chicken 而沒有說謊的人
D = 得到答案是 chicken 而說謊的人

如果真的答案是 egg, 可得

A + B + C + D = n
A         + D = eggcount
        C + D = liecount
   B      + D = liarcount

只要判斷有沒有 A,B,C,D 都在 [0,n] 中的整數解便可以了

判斷答案為 chicken 的方法一樣

Team Training 31/8/2010 - NEERC 2003

據說很難的一個 site..
不過也沒有想像中難
joe+kn+ctli solve剩一題!

題目: http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=nea&year=2003

---

A - Alternative Scale of Notation

Solution: Solve by yym

---

B - Bring Them There

Solution: Binary search (optional) + Flow

當時想不到, 不過joe一說分層圖便明白了
binary search 完成時間T, 再將每個 node split 開 T 層, 第 i-1 層的連去第 i 層
做 max flow 睇下做唔做到

也可以先設 T=1, 做唔到再一層層加上去
呢個方法較快, 但感覺上較難code

---

C - Code Formatting

Solution: 同 parsing 有關, solve by danny

---

D - Data Mining
E - Entropy

當時都沒想到的2題, 聽完solution也只是半明, 題型完全不是我的type..

---

F - Farmer Bill's Problem

Solution: 不斷把正方形合併

由於每次搵有無touch/overlap要 O(N²), 而最多合併 N-1 次
所以總時間為 O(N³)

---

G - Game

Solution: 不斷刪去可能性

分析為甚麼會 "I don't know the answer", 可以知道每說一次, 就知道一定不是 sum/product 唯一的 pair
然後不斷重覆此過程就是了

---

H - Hypertransmission

Solution: Sorting + Update

先把所有距離對 sort by distance, 然後逐條加上去, 再即時 update 那些值就可以了

---

I - Illumination

Solution: 未有人識做

---

J - Jurassic Remains

Solution: 試哂所有可能性

不過都要試得有技巧, 要做到純O(2ⁿ), 要用到bitwise operation

---

K - King's Quest

Solution: SCC

Given 一個 bipartite graph, 要 output 所有在其中一個 perfect matching 的 edge
|V| = 2000
|E| = 200000
題目已 given 一個 perfect matching


首先佢 given 一個 perfect matching 一定有意思, 因為就咁做一次都要 O(VE)
應該係用佢個 perfect matching 去搵其它 perfect matching 出黎

第一個諗到方法是試一條 edge 時, 看看能不能以最小的改動去維持 perfect matching
但這個方法最差是 O(E²)

之後想到用 augmenting cycle 的概念
for 每個 node, 搵哂所有由佢出發的 cycle, 途中所走的 edge 就是可選的 edge
但這個方法是O(VE), 也過不到

最後想到, 要搵所有 cycle 出黎可以用 SCC!
首先對個圖 (只走 augmenting path) 做 SCC
然後 check 所有由左連去右的 edge, 如果佢地係同一個 SCC, 咁 implies 佢地係一個 augmenting cycle 入面, 咁即係可以用
KO!

很優美的一條:D
估唔到SCC都可以同flow類扯上關係..

POJ 1741 Tree

男人八題之一

Problem

Given 一 undirected weighted tree, 問有多少 pair vertices (u, v) 的 distance ≤ k
|V| ≤ 10000

Solution

這題是經典的 divide and conquer on tree

假設現在的 root 為 x, 可以把 path 分為 2 類: 經過 x 和不過經過 x 的
現在先數經過 x 的
如果 (u, v) 是經過 x 的 path, u 和 v 一定來自 x 的不同 subtree
所以先對 x 的每棵 subtree 做一次 traverse, 取得每個 vertex 和 x 的 distance

但是目標這步要 linear
具題方法是先 traverse subtree 1, 取得 dist1[]
然後 traverse subtree 2, 取得 dist2[]
對這2條array做一次sliding window, 就計到所要的 pair
然後把 dist1[] 和 dist2[] merge 起, 如此類推

之後就要數不經過 x 的
那些 path 是獨立在 x 的 subtree 的
這步就是做 divide 了!
把 x remove, 然後 recursive 對 x 的 subtree 再數

但這樣 worst case是 O(N²)的
目標是要使得每次 divide 後每棵 subtree 的 size 盡量接近
這就要搵 CG of tree

CG of tree 的定義是 delete 該 vertex 後, 所形成的 component size 不大於 n/2 , n = tree size
又是可以做一次 traverse 找到
數學上證明了總時間複雜度為 O(N lg²N)

IOI 2010 總結

IOI 2010 Day 8

Departure day
一朝早就要走sosad
由於佢地仲未搵返我個keyboard, 睇黎要等佢地寄返黎..

比想像中快到達機場, 就快入禁區時撞到黃安之- -'
Toronto -> Hong Kong 第一次坐咁長途的機..
不過感覺還是很快便過了, 順利回到香港

IOI 2010 Day 7

今天是closing.. 早上和下午都是free time, 當然要出去逛啦
坐巴士show個IOI badge就可以免費坐! 第一站: waterloo uptown
很平靜的地方, 很舒服

之後搭車去了mall, 途中出現走失事件
食完lunch去了附近的玩具反斗城, 不過d玩具仲無聊過香港的..
hea左陣便回UW了

由於個closing是所謂的semi formal, 而佢地又無預先通知
我們還是穿了HKOI的黑Tee出席.. (其實著得正式的不足一半..)
個場地又幾grand的, 但食物水準只是一般
今年繼續無video睇, 個人認為video是十分重要的=[

由於排名一早public了, 頒獎禮也沒有甚麼驚喜
不過今年塊牌形狀比較特別吧
大家都係度等 tourist 上台拎佢的第4金
完左之後有很多隊走得勁快- -' 不過還是成功和數隊合照了
個人覺得還是上年比較有氣氛..

回到residence也沒甚麼做.. 只好收拾行李
又是沒有沖涼便訓了

IOI 2010 Day 6

今日要六點起身, 原因係六點九開車..
在車上訓了2hr, 去睇Niagara falls!

看到了才感受到真正的「奔流到sink不復回」
成個falls就係屈你機, 完全感受到nature的威力
途中不知怎的被fake了回旅遊巴集合, 去到發現無人..原來改左去排隊近距離睇個瀑布

一開始唔知點解要著雨衣, 落到去終於明
瀑布幾十米內就好似落雨咁, d 水花勁到..
很有趣的經歷

中午坐車去了個新奇的地方吃飯, 果然還是residence的野食最難食
食完又坐車回到Niagara falls附近, 今次是坐船去睇:D
由於有上一次的經驗, 今次有心理準備會濕哂, 大家都把雨衣索緊和收好電子產品
今次仲屈機.. 離個瀑布50m左右已經好似黑雨咁
不過大家都愈濕愈開心:D

坐完船仲有時間去左附近行
不過沒有甚麼有特色的東西所以手信都無買了..
不過條街好colorful..

回程的時侯又是ZZZ..
抖左陣又準備出去食飯啦:D
今次去左間蒙古菜, 任食, 有d似鐵板燒
自己盛滿一碗生的食物佢地就會幫你整熟
非常好食

就這樣遊玩了一天

IOI 2010 Day 5

比賽天2

發現有output only
先秒殺Q5, 然後發現Q6很簡單後便很不安..
因為要靠2條追分很困難

Q7 寫了個暴搜, 幾個細case都表現的很好, 很滿意, 於是先submit一下
看了看Q8, graph題但新題種, 有少少信心, 便一邊讓暴搜run Q7一邊想Q8
中途發現不對勁, 把細case 都做到>9分後, 發現大case不能用這方法..
因為佢grading係exponential, 大case全部得1,2分

於是又想想Q8, 途中想過用spanning tree, 最後還是放棄了
於是又回到Q7, 利用map的特性, 嘗試分成一個個column做searching, 比之前好了一點, 總分數上升了10分左右
最後1小時還是想不到Q8, Q7也沒有甚麼進展, 就這樣完結了

之後感覺很差, 發現Q8只有6人做到50分以上, 即係主要還是鬥條output only..
第2天Rank 7x, 但overall還是Rank 45- -'
之後就很頹的去食飯

晚上又是聽完lecture之後出去食飯:D
thyu突然爆發好似飲醉左咁:D
總於食到比較正常的一餐..

IOI 2010 Day 4

今日去一個叫"Canada's Wonderland"的地方
其實是玩機動遊戲的

當然係玩一些香港沒有的遊戲!
趴係度的過山車, 倒後行的過山車和木製的過山車
可惜沒有時間玩企係度的過山車

mlwong經常淆底=[
還有會一邊坐過山車一邊爆粗

有個ride是六人坐一隻橡皮艇
去到最後會經個一個小型瀑布, 由於隻橡皮艇會不斷自轉, 可視為會有random一個人(或一段連續的人)會濕身
非常有趣, 大家都用來測試人品和等住leader濕:D

由於明天是比賽天
又早訓了

IOI 2010 Day 3

比賽天!
早餐時還沒有甚麼比賽氣氛..
一去到比賽場地(gym)就感受到了

不幸的是, 坐正門口位.. 不斷有人出入去廁所
比賽開始
迅速解決Q1後才看其餘3條
Q2 第一感覺是存在很精巧的方法, 不過唔易諗
Q3 是自己較熟悉的grid題, 也是唯一的batch題
Q4 第一次睇, 睇唔明, 不過見到個program要「隨著query之後, 你的程序要學習..」就知應該方到最後做..

之後是同步想Q2和Q3
有>1hr 幾乎沒甚麼進展
後來才突然想到 二分 ! 在看到Q3 100後, 放心去想Q2
寫了個program出來試, 發現 n=500 要 18 次
後來才發現沒有善用equal的case, 搞到每次cut少左 1
第一次 submit 有 77 分

終於睇明Q4.. 看來應該是決勝關鍵
一開始的方法係對每句句字同之前的句字compare, 計相似度, 計每種語言的平均相似度
竟然有 60% 準備度!
之後加埋對每種character睇下佢會出現係邊種language
愈出現得少, 有果個character的句字就愈可能係果種language
最後結合2個function令準備度升至70%!
後來再改下2個function的比重都無咩幫助.. 之後就一直停在78分

回到Q2, 改左少少野, 高左1分
之後就完場了

還未走出gym leader已經衝左入黎
Rank 45.. 不過分數非常接近
要看day 2了
還有被電視台訪問了

夜晚去聽talk, 之後終於出左去食野:D
吹水吹到11點先返residence

IOI 2010 Day 2

朝早, opening ceremony
早餐和去年CCC一樣, 5樣任揀, 2⁵種可能性
不得不提那些橙汁, 連橙味都無, 純糖水sosad

opening ceremony要坐車去!
場地感覺細過上年
Troy 一開始就搞gag: IOI10 = 10110 = 22 (剛好是第22屆IOI), 叫絕全場
不過之後的speech還是一如以往的悶, 表現也沒08旳精彩

午飯覺得很不安, 想到仲要係度食多7日
之後試機, 第一次用佢個system
由於今年係implement一個procedure(好似SRM咁), 所以無得正常compile
方法轉為把program save在特定的folder內, 再用terminal打runc grader.cpp
就會自動compile同試哂folder內的所有test case, 這點十分方便
要output debug msg就output去stddout, 佢會自動direct去一個file
雖然有點不慣, 但總括來說沒有甚麼大問題

晚飯仍舊難食
之後去行左校園一次就回去訓了

IOI 2010 Day 1

本來1230集合, 不過因為剛出細o, 返到屋企先再執野.. 又要搞下報宿的事, hea hea下去到機場已經1300
去到發現本來直飛變左要係taipei轉機sosad
本來己經夠遲去到的了..

食完lunch就入禁區, 由於剛出camp又唔夠訓, 感覺病病地咁, 去到果個gate就訓到有得上機
上到機又係ZZZ, 一套戲都無睇, 到左台北等轉機行左陣就又訓過.. 感覺很頭暈=(
台北->Toronto 十幾個鐘, 訓訓下就到左喇, 當地時間九點幾..

等埋其它隊搭車去到waterloo己經23XX (上年15XX左右架..)
個guide係當地香港人..
搵 residence 的時侯搵左好耐都搵唔到sosad
最後同mlwong同一間房

IOI 2010 小記

在 closing ceremony 上, Troy Vasiga (今屆的 chair) 說了一句很難忘的話, 大意是這樣的:

You are the few who knows the power of this knowledge, and knows how to use it.

很 encourage 的一句話!

IOI 2005 Mountains

不簡單的 segment tree 題..
麻煩在於 memory 不夠開整棵 segment tree

解決方法1: 離散化query, 感覺很難寫
解決方法2: 動態開樹

最後用了方法2, 可分為用 pointer 或 array 模擬.. 我用了後者, 應該分別不大

每個 node 記的資料為:
1] 是否整段都是同 slope
2] 總上升高度
3] 最高點的位置

就足夠了 (注意要用long long..)

IOI 2005 Mean Sequence

首先留意到 fix 了 s[1] = fix 了整條 sequence
然後觀察到, 合法的 sequence 的 s[1] 必定是一個連續區間的整數

做法: 先設合法的 upper bound 和 lower bound 為 U = m[1] 和 L = -INF

s[2] = 2*m[1] - s[1], 而且 s[2] <= m[2] 可得 2*m[1] - s[1] <= m[2], 即 L >= 2*m[1] - m[2]

如此類推, 從而縮窄 upper bound 和 lower bound
最後 number of mean sequences = upper bound - lower bound + 1

IOI 2005 Garden

對於任何長方形的放法, 總有方法用一條橫/直線把它們分開
做法就是窮舉那條分界線

先假設是打橫切
問題就變為在 row[x..y] 中要包住 k 支roses 的長方形的最小邊長

先 pre compute 長方形的邊 exactly 由 row x 到 row y 的情況
然後用兩條掃描線就可以了

總時間O(N³)

IOI 2004 Phidias

由於有「一刀切」的條件, 很容易想到用 dp

dp[x][y] = 分割一 x*y 長方形最小的浪費空間

於是有

• dp[x][y] = 0 if size[x][y] exists
  
• dp[x][y] = min{ dp[x-i][y] | 0<i<x , dp[x][y-j] | 0<j<y }
  

但係我猜想, 其實會唔會每一次切都係切一些 plate size 的長度, 即

dp[x][y] = min{ dp[x-height[i]][y], dp[x][y-width[i]] }

最後發現是可行的
不過未 prove 到..

IOI 2004 Farmer

一開始以為係 knapsack, 後來又發現可以分開拎

睇明題目後做法很簡單, 如果樹圈的數目 >= 可以拎的, 咁就睇下砌唔砌到剛剛好N (即答案是N或N-1)
如果唔夠, 就對餘下的線樹繼續做 knapsack..

ICPC 2691 Evacuation Plan

本身在 poj 的「網絡流專項」見到的
不過 poj 近排的 special judge 成日死 (同一段 code 隊幾次會出現 AC 同 WA.. )..

Problem

given 一個 cost flow 的 graph (沒有 negative cycle), 及給出一個滿流的流方案 , 問這個方案是否已經是 min cost, 如果不是, 給出一個更好的方案 (不用 optimal)

|V| = 200, |E| = 10000

---

Solution

首先重新做一次 min cost flow 一定會超時..
注意到其實不用求出最 optimal 的 solution, 應該有其它方法

細心想, 如果它的方案不是 optimal, 咁應該可以行一些 augmenting path 去「調整」流量及流向
但由 source 出發已經滿流了

於是想到其實題目是找negative cycle
如果在 residual network 中沿著 augmenting path 搵到 negative cycle 即是存在更 optimal 的 solution
而且 negative cycle 上的 path = 要改流量的邊

Implement

由於只要搵到比佢個方案稍為 optimal 的便行, 所以流量有 1 就夠了
因此第一步找出 residual capacity > 0 的 edge

然後找 negative cycle
我用 SPFA 寫, 如果一個 node 被 update >= |V| 次就表示有 negative cycle..
效率比 bellman ford 好多了, worst case 也只是和 bellman ford 一樣

最後就是起返個 negative cycle 出黎..
呢步卡住左一陣!
一開始以為果個被 update >= |V| 次的 node 一定是在 negative cycle 上
不過其實可以係一些 negative cycle 指出去的 node

最後稍加修改, 不斷行 from[x] 直到走到 cycle 上的 node 便可以了 (一定會走到)

SRM 477

250

和六角型grid有關的題

速度一般般吧, 分基偶行來處理, 只得227.22

500

一看便想到是用 bipartile matching

第一個問題: 食input

先把string轉做array of char, 再用sscanf
不過寫的時侯也不太肯定, 花了少少時間去test這個寫法, 又損失了一些分數


第二個問題: Perfect square checking

想了想好像沒有甚麼標準又好的做法, 腦中想到有3個可用的寫法

1. sqrt + eps
2. sqrt 後掃前後5-10個數
3. 二分

最後在精確度和coding速度之間選了方法2

之後matching那part是貼武器的

過不到sample 2, 又花了很多時間去debug
浪費了超過10mins才發現題目中的 concencate 是就咁 concencate!
即係 "19", "5" 應看成195而不是19和5

又慢了一大截.. 終於可以submit

submit後睇下段code啦.. 突然發現由於改了為將d string concencate哂先轉為array of char, 又忘了開大array..!
逼不得已要resubmit..

得返 228.91

1000

疑似 dp on tree, 未諗到

---

system test 過了, rating 升了 ~100
500 浪費了很多時間又resubmit實在有很大影響, 尤其是找不到bug又不知為甚麼過不到sample那種心情, 還是要看清題目

---

條500原來因為有一個很重要性質才可用bipartile graph matching的, 之前一直無想過
原來我對 matching 的理解還是有不清楚的地方.. 不過也好, 經過今次後終於明白了

Team Training 27/7/2010 - CEPC 2003

今次的題目比上次的還要難..
上次還有2條可以有機會過的, 今次過完做到的就渣灘了..

最後 我+bill+danny 共過了4題.. (onsite champion solve了6題)

題目: http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=ce&year=2003

---

A - Easy Task?

data processing, bill 做的

---

B - Bundling

題目長得很過份.. danny看明後跟我說題目大意, 判定為不想做

---

C - Shortcut

我的方法是先按 x->y 和 y->x 兩種方法排序..

然後找出每點的四個方向會最先碰到哪點, 用二分的lower bound和upper bound
但由於不懂用stl的, 所以還是寫了4個binary search

雖然similar code可以copy, code length還是爆了100
在戰略上不應做呢題先的..

---

D - Dice contest

後來大家一起討論.. 得出「局部shortest path」的猜想
不過 code 起上來好像很煩..

---

E - November rain

看到這類題最先想到segment tree
但發現很多地方唔work

於是想到由左做到右的方法
便可好好利用題目中的 "there are at most 100 segments placed above any point on the ground level"!

解法是先把所有點 sort by x
用一條 list keep 住每點 x 上 segment 的高低順序

每次 maintain (add, delete) 都可以用 linear 的方法去做
可以求出
1. 每條 segment 接收了多少由天來的雨水
2. 每條 segment 會流去邊條 segment

之後便很簡單了

WA 的幾棍都是在 sorting 上有誤
如果 x 值相同, 應該是「先入後出」的
如果同是先入, 則應該由下至上的入
如果同是先出, 則應該由上至下的出

code的時侯便會明白的了..

---

F - Football
G - Which is next?
H - Hang or not to hang

0 idea..

---

I - Minimizing Maximizer

一起做的, 我寫 segment tree 的部份, 其餘由 bill 和 danny 完成

Team Training 20/7/2010 - CEPC 2002

今次的題目都不易.. 做了3題

其中一題比較有趣

---

G - Timetable

題目是 given 一些 node 和一個火車時間表 (departure time, arrival time), 定義一條由 1 到 n 的 optimal connection 為在 A 時由 node 1 出發而在 B 時到達 node n, 並且沒有其它方法可以在 A' (A'>=A) 時出發而在 B' (B<=B') 到達

要list出所有optimal connection



首先想到的是對所有可能的出發時間做一次shortest path, 但可能會很慢

之後想到由decreasing的departure time開始不斷做shortest path
每次行過一條edge後便可以把那條edge delete!
因為是decreasing的departure time開始做, 所以如果在t=x出發行過某條edge, 咁對於出發時間早於x, 如果是optimal的話一定不會再用那條edge

實際implement應該先把edge sort好再加進edge linked list中
不過在training時由於覺得太麻煩而沒有做這步, 不過也run得很快

IOI 2004 Empodia

首先, for each i, 搵出由 i 開始且最短的 framed interval, 記完結位置為 p[i] (即 i..p[i] 為一 framed interval), 搵最短是因為一些更長的可以肯定不是 empodia


對每個 i, 可以在 O(N) 搵到
由於 framed interval 的特性, e[i..j] 滿足以下條件即為 framed interval

• e[i] < e[j]
  
• e[i] = min{e[k], i < k < j}
  
• e[j] = max{e[k], i < k < j}
  

很容易可以做到

之後就係delete一些不是 empodia 的 framed interval
方法就係 for each i, 睇下有冇 j>i 而且 p[j]<p[i]

總時間O(N²)


順帶一提, 解題報告話呢題有O(N)方法, 不過是論文來的.. (只有一個test case需要O(N), 佢應該唔預有人諗到..)

POJ 3493 Chessboard Puzzle

題目是說, 給出一個 n*n 的 grid, 每格有一個分數 (可以負), 現在要將每格染成白色或黑色, 總分計算的方法是:
----如果兩格相鄰而且異色, 把它們分數的乘積加到總分
問最大可能總分, n <= 16

---

做法是使用狀態DP
一開始是想用像炮兵陣地的方法DP, 即state是記一行的permutation, 但單是做一次transfer便要2²ⁿ了

後來聽超超說,
有一個很強的加速

考慮到每一格是黑/白最「遠」也只是影響到下面那格 (假設順序是一行行由左至右)
即 n 格後
可以順著做而且只記著前n步的狀態

即

......
......
......
......
......
......

做到紅色那格時, 只用記著藍色的排列, 每次transfer後只是把排列shift後一格 ->

......
......
......
......
......
......

把time complexity降至O(n²*2ⁿ)

Individual Training 13/07/2010

A - Adventure of Super Mario

Shortest Path
一開始以DFS來處理super run, 後來發現處理不到limit的情況
於是改用floyd-warshall preprocess, 改outer loop便巧妙地處理到castle不能經過的條件



B - Geometry with a ruler

geom題, 不過差不多要0誤差..
我用fraction + long long, 不斷取 gcd 約簡過了
理論上應該會有case搞到我 overflow..



C - Chessboard Puzzle

學到野的一題, 之後打篇entry詳細講..



D - Diamond Puzzle

簡單BFS



E - Discrete Square Roots

又係同mod有關的題目.. 未識做

IOI 2004 Hermes

一個很重要的 observation: 在 optimal case中, Hermes 每次移動都只會行一段直線 (即唔會行 x 再行 y )

由於傳完 message 去第 i 個點後, Hermes 的位置只有大約 4000 個可能性 (或2N), 所以諗到用 dp 做, transfer 時, 因為由上面的 observation, 所以可以 O(1) 完成每個 state 的 transfer, 總時間上限 O(N²)

IOI 2004 Artemis

O(N²) 時間可過! 但 memory 就唔得
做法也是用 inclusive-exclusive, 問題係點樣唔用 O(N²) memory 去 implement

先把點 sort by x
之後由左至右咁做, fix i for j, 每次都係 compute s[x_j][y_j]+s[x_i][y_i]-s[x_i][y_j]-s[x_j][y_i] 之類,
發現除了 s[x_j][y_j] 和 s[x_i][y_i], 其實都只係 depend on x_i, y_i

所以只要把和 i 有關的 2N 個「關鍵點」(共N²個「關鍵點」)計出, 即 s[x_i][*], s[*][y_i], 便可把 memory 降至 linear

IOI 2001 - 2003 小結

小結一這3年的IOI題..

2001: 這年得3題batch題, 3題題目都straight forward, 不過算法不易想到. BIT第一次出現, twofive code 起上來也不容易一次就成功

2002: 很多 ad-hoc (除了 batch), 不過真係諗唔到就諗唔到 (例如utopia, bus). 有一條要用凸完全單調性來優化DP, 很不 IOI feel..

2003: 也是只得3條batch, 算法不難想到, 只是3條實現起來都很煩, code length 很長

IOI 2003 Amazing Robots

題意很簡單, 就是BFS

注意到guard cycle是12, 所以有 20*20*20*20*12 個 state

簡單還簡單, 試左好幾次先過哂所有data.. (仲要睇住data來debug..)
有一個比較麻煩的位是要 check 係咪同個 guard 換位

過之前段code最後一個不能handle的問題 (G = guard, R = robot)

...    .G.
.G. -> .R.
GR.    .G.

我會當左係換位, 但其實唔係

IOI 2003 Seeing the Boundary

因為障礙物是 convex polygon, 省卻很多麻煩 (如果可以 concave 我都未諗到點 handle..)

每個 polygon 會遮蔽其中一段連續的點
所以只要找出遮蔽的範圍就好做了

我的做法是先對每個 polygon 的頂點做極角排序
由於那些頂點會縮在 180^o 的範圍內, 用cross product就可以找出紅色那兩點

由於不想handle precision, 我所有計算都用哂 integer
之後麻煩在要找出射線和 boarder 的交點

經過一輪數學運算, 終於截到式
有個tricky的位, 就係「開始遮蔽點」和「結束遮蔽點」做除法一個是 round up 和 round off

最後一個bug就係我無handle到有些障礙物一個點都無遮到

IOI 2003 Comparing Code

做法類似搵 maximum common substring

首先map哂佢d variable名做數字
之後fix其中一條sequence, 窮舉第2條sequence係佢上面的位置 (或者調轉)

不同於搵common substring, 判斷valid唔valid要睇埋之前的
方法就係用2支pointer做掃描線!

valid 就 tail++
invalid 就 head++

判斷valid的方法
一開始諗住2個sequence, 把variable一個對返對應的variable
不過唔work

例如

Seq 1:

A = B + C
A = B + B

Seq 2:

X = W + Y
X = Y + Y


compare 第一句 statement 時, 對 X->A 無問題
但係 "W->B, Y->C" 和 "W->C, Y->B" 是有分別的, 而且要在之後先睇得出來


之後就想到了"記上一次出現的位置"的方法
位置指的是 第?句statement的左邉/右邊

即不再記 X->A, 而是記 "X對上一次出現是在第一句statement的左邊"
每次checking就係睇下這些 "位置" 是否吻合

就解決了問題

IOI 2002 Bus Terminals

做法離不開窮舉 2 個 terminal, 再計算 route distance

一開始以為剩返的 N-2 個 bus stop 會選擇連去離他最近的那個 terminal, 不過後來發現反例
解決方法有點像greedy (看contest report)

窮舉 terminal i,j
先把剩下的 N-2 個 bus stop 都連去 i
然後按 dist[k][i]的 decreasing order, 嘗試把 k 調到 j 看看能不能使最大距離下降

有點詭異的過了..
很直觀做法但又無prove過..

IOI 2002 Batch Scheduling

傳說中的凸完全單調性優化

要倒著做的
dp[i] = 處理 job i 到 job N 的 minimum cost

O(N²) 的做法是 dp[i] = min{dp[k] + (S+T_i+T_i+1+…+ T_k-1) * (F_i+F_i+1+…+F_N) | i < k < N+1}
(即是後面的 job 的 factor 在前面計)


優化到O(N) [照著contest report打]

在compute dp[i] 時, 例如有2個決策 k 和 l (k < l)
即 dp[i] = dp[k] + ... 還是 dp[i] = dp[l] + ...

k 不差於 l 的條件是

dp[l] + (S+T_i+T_i+1+…+ T_l-1) * (F_i+F_i+1+…+F_N) ≥ dp[k] + (S+T_i+T_i+1+…+ T_k-1) * (F_i+F_i+1+…+F_N)
dp[l] - dp[k] + (T_k+T_k+1+…+ T_l-1)*(F_i+F_i+1+…+F_N) ≥ 0
(dp[k] - dp[l]) / (T_k+T_k+1+…+ T_l-1) ≤ (F_i+F_i+1+…+F_N)

設 g(k,l) = (dp[k] - dp[l]) / (T_k+T_k+1+…+ T_l-1) ; f(i) =  (F_i+F_i+1+…+F_N)

會得出2個特性

Property 1: 如果 g(k,l) ≤ f(i) , 咁對 dp[i] 黎講, k 比 l 更好
Property 2: 如果 g(j,k) ≤ g(k,l) , 咁對於 dp[i] 黎講, j 比 k 好 或 l 比 k 好


property 2 implies 對於 g(j,k) ≤ g(k,l) , 計 dp[i] 的時侯可以不用試 k 這個 choice

整個 algorithm 就係由 dp[N] 做到 dp[1]
maintain 住一條 deque Q, 滿足

1. q[1] > q[2] > q[3] ... > q[r]
2. g(q[r],q[r-1]) > g(q[r-1],q[r-2]) > ... > g(q[2],q[1])


計 dp[i] 時, 由 property 1 得知如果 f(i) ≥ g(q[2],q[1]) 咁 q[2] 比 q[1] 好
由於 f 是 increasing 的 (因為倒著做), 所以知道 q[1] 之後都唔會再有用, 可以 pop 走
所以可以不斷 pop queue head 直至 g(q[2],q[1]) > f(i)


現在有 g(q[r],q[r-1]) > g(q[r-1],q[r-2]) > ... > g(q[2],q[1]) > f(i)
由 property 1 的相反得知.. 現在 q[1] 對 i 是最 optimal 的

就能計算出 dp[i] 了

下一步就是要把 i push 入 Q
方法是由尾開始 pop 走加左 i 落去會唔符合 g(q[i],q[r]) > g(q[r],q[r-1]) 的點 (類似做 convex hull)

Individual Training 29/06/2010

F - PKU 1065 Wooden Sticks

給定 N 組數 (a_i, b_i), 每次用一個 cost 可以 cover 一條 sequence 且每項的 (a_i, b_i) 都小於之後的那項, 問 min cost


首先很直觀的想到用greedy, sort by (a,b), 然後順著做, 如果未被 cover 就拎, 再順序掃後面的, 拎到就拎

這個greedy是對的, 時間O(N²)



後來學到 O(N lg N) 的做法, 方法也是 sort by (a,b), 然後找 b 的 longest decreasing sequence!

想一想也發現是很合理, 條 LDS 的每一項就是代了每條 sequence 最尾的那個 object
由於搵 LDS (LIS) 可以 O(N lg N), 整體也是 O(N lg N)





D - PKU 2036 I Conduit!

給定平面上 N 條線段 (input 準確至小數後兩位), 問合併哂 overlap 的後實際上有幾多條線段


其實呢個係做ctli在hkoj上的The keep都有寫過, 方法是把所有segment sort by

1. 斜率
2. y - 截距
3. x1 值 (設 x1<x2)

之後順序判斷+合併就是了, 要注恴的是無限slope的segment

由於見input只去到小數後兩位, 明顯地可以純整數咁做 (記分數form), 由於我用左

scanf("%d.%d",&x,&y);
p=x*100+y;

去食input


WA 兩棍後才發現我會將例如 3.05 和 3.5 都化作 305

頗深刻的bug

IOI 2002 Utopia Divided

諗左好耐, 最後都係去左搵果年既 report

的確是很巧妙的做法..! 不過唔易諗到



定義 alternating sequence為一數列 X1, X2, X3, ... Xn
其中 |X1| < |X2| < |X3| < ... < |Xn|
而且 sign 是互相交替的

例如 -1,4,-6,7
和 2,-3,7,-10




alternating sequence 有一個性質
就是 整條數列之和的正負 等同於 Xn 的正負

例如Sum (-1,4,-6,7) = 4  [與7同號]
Sum (2,-3,7,-11) = -5  [與-11同號]



1D 的情況
要將 n 個數字 X1, X2 ... Xn 排好和 assign 正負值, 而且頭 x 個之和是指定為正或負 ( S[x] = '+' OR S[x] = '-' )




先將果 N 個數字由小至大 sort
然後 assign 正負相間, 做成一條 alternating sequence

咁一開始取值正定負呢?


由 alternating sequence 的特性, 為了滿足 S[n] , 因此 Xn 應與 S[n] 同號

這樣便可確保 Sum( X1,X2,X3...Xn) 的正負號必滿足 S[n]
而且入面數字的次序點調都得


咁點先可以滿足 S[n-1] 呢?
由該性質可得, 如果可以整到一條 長度n-1, 最尾那個數字的正負號=S[n-1] 的話, 便能滿足 S[n-1]


現在是 X1, X2, X3, X4, ...Xn
有兩個選擇,

1)
X1, X2, X3... Xn-1

2)
X2, X3, X4... Xn


用邊個選擇? 就係睇 S[n-1] 同 Xn 同號 還是 同 Xn-1 同號 !!

由於是一條 alternating sequence, Xn 必與 Xn-1 不同號, 因此總能找到與 S[n-1] 同號的

By induction, 重覆此步驟 n-1 次, 便能滿足 S[1]..S[n] !


例子:
n = 5
S[ ] = {-,-,-,+,+}
X[ ] = {2,3,4,5,6}


Step 1 [ assign 正負, 使 X5 與 S[5] 同號 ]

X[ ] = {+2,-3,+4,-5,+6}


Step 2 [滿足 S[4] ]
X[ ] = {-3,+4,-5,+6,+2}

Step 3 [滿足 S[3] ]
X[ ] = {-3,+4,-5,+6,+2}

Step 4 [滿足 S[2] ]
X[ ] = {+4,-5,-3,+6,+2}

Step 5 [滿足 S[1] ]
X[ ] = {-5,+4,-3,+6,+2}

IOI 2002 The Troublesome Frog

用了一個看似是 O(N³) 的方法做..

pick 2 點, check 下佢可唔可以成為 path 的頭 2 點, 然後再行條 path , 睇下係咪 path 上的每一點都存在

另外很重要是加了一些優化

1. 由左面的點開始做
2. 如果假設條 path 是 valid 但長度也不長於 current max, 就唔使 check 了

所以看似是 O(N³) 的方法在 pku 只 run 了 16ms


不過再想, 其實可能是 O(N²) 來的

照解題報告的方法, 如果將兩點 (A,B) 視為一個 vertex, 咁只有 N² 個 vertex

而由於加了那2個優化, 應該可以確保每個 vertex 最多只行一次

Individual Training 22/06/2010

今次題目偏向數學..

比較興奮的是做到B (雖然其它人一開波就做到) , 但這題其實幾年前已見過, 但一直都未識/未敢做, 算是又對 number theory 踏前了一步..


F - PKU 1997 Word Puzzle

題目: given 一個 200*200 的 lowercase letter array, 再 given 1000 個長度不多於 20 的字串, 問係個 2D array 度起哂 d word 出黎後 (8方向) , 剩返邊d character


做法: 直接搵會超時 (200*200*8*20*1000) , 所以我將果 1000 個 word 用一棵 trie 儲起哂, 每次向8個方向行直接知道有無字, 將複雜度降為 200*200*8*20



B -  PKU 1061 青蛙的约会

題目: 在一個長為 L 的 ring 上, 兩隻青蛙分別為於 position x 和 y 上, 每一個 time period 它們都會向同一方向跳 m 和 n 格, 問最快幾時先會同時在同一個 position, 可以無解

L <= 2100000000


做法: 印象中第一年玩HKOI mini comp 就見過呢題, 不過當然唔識做.

如果把方程寫出.. 就是

x + T*m = y + T*n   (mod L)

T(m-n) = y-x   (mod L)

簡化一下.. 就是要解 T*a = b   (mod L) , 也就是所謂的解模方程

諗左好耐, 發現同 extended euclidean algorithm 有關 !

T*a = b   (mod L) 即

T*a + L*k = b

如果對 a 和 L 搵 GCD 的話, 由 extended 果 part 可以有

a*i + L*j = gcd(a,L)

結論 1: 如果 b % gcd(a,L) 不是 0, 則輸出 Impossible

如果將條方程左右乘大 b/gcd(a,L) 的話.. 就得到

a*i*b/gcd(a,L) + L*j*b/gcd(a,L) = b

解得 T = i*b/gcd(a,L)

但注意這只是 T 的其中一個解,  T 應該有無限個解的
output 要最小而非負的 T

由於 a*i + L*j = gcd(a,L) , 得知 T 的每一個解相差 L/gcd(a,L)

即一般解為 T + r*L/gcd(a,L) ,  r = integer

有呢樣野搞兩搞就可以將佢變返做最小而非負


其實做到呢題真係好開心, 算係一個突破吧
平時做 judge 一定唔會自己諗到, 要在果個環境下先會做到..



仲有一題很難但值得打出黎..

D -  UVa 10692 Huge Mod

搵 a₁^a₂^a₃...^a_n mod m

有少少想法.. 但如果真係要做應該有排 struggle ...

TCO 2010 Round 1

250 - 水題

500 - 兩個 register A,B 一開始 set 做 1 , 每次可以做 A = A+B 或 B = A+B, 問要將 A set 做 L (L <= 10^6) 最少 operation 數

1000 - given一個城市, directed graph, 其中一個 vertex 係酒店, 而家俾你 set 一些 tour, 每個 tour 收費 P, set 幾多條 tour 都得, 條件是每個景點 (vertex) 最多只能被一條 tour 所用, 每個 tour 的成本為 edge 的 cost, 求最大 profit  (|V| <= 50)



250 雖然頹, 但精神狀況太差, 又有頹bug, 得返~220

500 USACO 有條少少似, 不過果條唔識做. 打個表出黎睇下都睇唔出 pattern, 於是試下1000

1000 諗左陣, 發現係 max cost flow! 做法大約係拆點, hotel out = source, hotel in = sink, source 連出去之前有條容量無限 cost 為 P 的邊, 然後每 sent 一個 flow 就試下 update current max

諗到後很興奮, 因為睇落去得好少人做1000. bug唔多, 完場前5mins submit



challenging phase 由於500唔識做好難cha人500, 1000大家又都係flow咁

到system test.. 驚見 1000 failed system test 了  =(
就係咁, 跌出rank850之外, 無得出線..



之後搵返, 原來係做SPFA時,  initialize 我 set vis[ ] = -1, 但由於有負cost, 所以有機會做成明明無 path 都想起返條 path 出黎, 搞到 TLE ..

改善: 實現算法時要諗得全面, 尤其係topcoder, 與其貪code短, code得穩陣更重要

IOI 2001 Twofive

其實2個query最終也是要知道:

"Given current table, return the number of ways to fill the rest of the table"


單純的 recursion 會超時

如果是由 'A' 到 'Z' 看看有哪些未用, 然後填落去的話
由於是由小至大地填, 所以一定不會出現唔 valid 的情況



假設原本的 table是

A B C D E

F G H * *

I J * * *

K * * * *
L * * * *

例如某些方法填了 M 和 N,

A B C D E

F G H M *

I J N * *

K * * * *
L * * * *

A B C D E

F G H N *

I J M * *

K * * * *
L * * * *

這兩個方法之後再砌的方法的數目是相同的
重點是「形狀」!

可以用狀態 dp 去避免重複運算

dp 的狀態是每一row填了多少格 (不會中空, 一定是由左開始填)
每次加一個新的字母一定是加在某一row的後面

其實思路不是太複雜

不過這個構做法並不容易想出來
我是看著 sample code 來揼的..

Grey Code

scanf("%d",&n);
for (int i=0;i<(1<<n);i++) printf("%d\n",i^(i>>1));

霸氣。

POJ 2432 Around the world

今日打 individual 有呢題..
其實之前都見過不過唔識做

不過做左2題之後有一題勁難一題勁煩..
逼於無奈要攻呢題




題目大意 -

地球上有 N (N<=5000) 個 farm, given 它們的經度 (0..359), 有 M (M<=25000) bidirectional path 連接某些 pair farm, 行這些 path 都是以最短 (向東飛/向西飛) 方法到達

現在要環遊世界 (唔一定要 visit 所有 farm) , 「環遊」的定義為由 farm 1 開始, 行一條 path, 回到 farm 1, 而且 順時針飛行距離 不等於 逆時針飛行距離 (其實呢個唔係環遊的必要條件, 只是充分條件)

問: 最少要飛多少程




嘗試過各種 dp 的方法都失敗
BFS 又唔知幾多 states 先夠

係呢個灰暗既時刻, 突然想到把所有 node(#farm, distance difference) 扔埋入個 map .. 再開條 stl queue 硬做
諗住實 TLE, 點知.. AC!

仲要係250ms左右, 比想像中快很多

估計係因為實際狀態遠比想像中少, 同埋好多case好快就reach到終點
之後上USACO睇official solution, 都係差唔多 - -' (不過佢題解得solution code)

IOI 2001 Depot

三個字: 倒著做

原本是放數字入去, 其實等同於數有幾多個方法抽返 d 數字出黎

1) row 1 最右的可以就咁抽出
2) row 1 的數字可以抽走, 但留下空格
3) 對於空格, 可以係下面果行搵個適合的數字抽出黎填返, 然後再填返下面的空格

其實係睇寫 recursion 的功力..

South America 2009

#	Solved	Score	A	B	C	D	E	F	G	H	I	J	K
Hussar	10	1055	1/48	1/56	-/-	2/37	1/69	3/224	2/202	3/159	2/27	1/13	1/80
GAGGUY+AC	10	1354	1/33	1/43	-/-	4/296	3/37	1/244	1/165	1/203	1/62	1/54	1/117
Prof. QQ	8	1361	2/117	2/73	-/-	1/67	3/150	-/-	-/-	5/303	6/152	1/7	3/192
BDJ	8	1367	1/206	1/117	-/-	2/130	3/72	-/-	1/-	3/282	4/144	1/16	3/200

(Copy from kn)

開局不是很好, 很久才過到第一題



Summary
Team members: GagGuy, AlanC
Solved: 10/11
Penalty: 1354


Process
A (+0)  dp on tree
E (+1)  AC, math + 二分, hardcode一些東西打錯
B (+0)  simulation
J (+0)  by AC
I (+0)  sorting
K (+0)  在 [1,1000] 中記錄會影響個 value 的點
G (+0)  有點難度, 有很多方法做, 用了AC提出的binary search法, 很強大
H (+0)  似曾相識的 flow, 打武器 (ISAP), build graph 的 code 很長
F (+0)  suffix array, 要搵有幾多條唔同的 suffix 出現 > 1次, 對住 h[ ] 搞幾搞很神奇的出到答案
D (+4)  greedy by AC, 那 4 棍完全是我的錯 =[






Unsolved

C - 疑似 dp, 未諗到




Reflection


今次整體的流暢度不及上次, 不過題目相對較難, 有一些細節也需要更多時間去思考

體會到武器的重要性, suffix array 是因為真的很複雜, 而 flow 雖然徒手也揼得出, 但用武器的話真的可以節省不少時間和精神..!

D 本身並不難, 其它隊很快便過了, 詳細記下發生甚麼事吧

本身 greedy 方是 AC 諗到的, 我也覺得看下去正確, 便幫他寫 input 果 part, 不過第一次返回 WA
之後 de 左幾個 bug 仍然 WA, 我開始懷疑算法的正確性, 始終我無真係 prove 過個 greedy

一直搵唔到 counter example, 但段 code 睇極都無錯, 睇多幾次題目確定沒有理解錯誤
中段 AC 提出可能是 input format 的問題, 我認為這個可能性很低, 也不想糾纏係呢題, 就無咩點理到..

剩下 10 mins 時無野做改下食 input 的方法, 結果竟然 Accepted !


事後覺得我做了不少錯誤..

首先驗正隊友的算法是好的, 因為有些時侯可能想到一些隊友沒想到的 case
但,
AC後來提出是 input format 的問題時, 我 reject 左呢個可能, 某程度上自己的確有點驕傲, 恃著自己的經驗而沒有實行隊友的建議
結果當然是浪費更多時間對一個正確的算法搵錯, 完全影響之後的過程

即係, 改 input format 不用一分鐘, 但做左呢樣樣至少可以確定是不是算法的問題=[

對不起..


改進:
1) 學 suffix array O(N lg N) , 今次的 O(N lg N lg N) 差點就 TLE 了
2) 理解點樣 O(N) 起哂相鄰 suffix 的 longest common prefix 出黎
3) 放下自己, 相信隊友

最大平均值問題

Given a[N] 和 M, 找出長度不少於 M 而平均值最大的 continuous subsequence [1]
例如 a = [2, 5, 2, 5], M = 2 最大是 (5+2+5)/3

Algorithm 1

二分答案 d,  問題轉化為
設 b[i] = a[i]-d , 是否存在一段長度至少為 M 的子串而 sum ≥ 0
設 S[i] 為 b[] 的 partial sum array, 再計算 Suffix[i] = max{S[j], j ≥ i}
只要檢查最大的 Suffix[i+M] - S[i] 是否 ≥ 0
之後睇了 [2],  見到一個 linear 的算法

Algorithm 2

如果定義 s[i] = a[1] + a[2] + ... + a[i], 問題轉為搵 max {(s[y]-s[x]) / (y-x), y - x ≥ M}
將 (i, s[i]) 視為 2D plane 上的點, 等價於求 maximum slope

對於每個 y , 要考慮 p[0, y-M] 的點, 更進一步, 其實只要考慮 p[0, y-m] 形成的 lower hull 就足夠
所以要 maintain 著 lower hull (用一個 stack, 反角形成時便 pop)

直覺是類似 tangent 的連到 lower hull 上, 找 tangent point 可以用 binary search
也可以利用 lower hull 的 slope 是 monotonic increasing 這個性質
如果在 lower hull 上 p[y] 是對於 p[x] 的切點, 對於 x' > x, y' < y, 這個組合不會好過 (x, y)

所以只要記住當前的切點, 每次只向右移, 一共是 O(N)

References:
[1] POJ 2018 Best Cow Fences
[2] 周源 <浅谈数形结合思想>

Team Training 2/6/2010 - CERC 2004

Rank	Name	A	B	C	D	E	F	G	H	I	Total	Time
1	gagguy	-	+ 1:26	+ 0:46	+1 3:42	+2 1:09	+ 2:26	+ 1:44	+ 3:37	+ 0:25	8	975
2	chin	-	+ 1:23	+1 1:58	+3 3:15	+ 2:11	+ 4:26	+ 0:48	+1 2:48	+ 0:30	8	1139
3	dannyyip	-	+ 4:01	+ 2:26	-	+ 1:17	-	+1 2:58	+3 4:16	+2 0:45	6	1063
4	Prof.QQ	-	-2	+ 2:18	+1 3:08	+ 0:30	-	-4	-5	+ 0:10	4	386
5	Leo	-	-	-	-	-	-	-	-	-	0	0
	Submissions	0	5	5	8	6	2	8	12	6
	Accepted	0	3	4	3	4	2	3	3	4
	Solvability	0%	60%	80%	37%	66%	100%	37%	25%	66%

今天在CU打的training.. 老實說, 看結果是幾滿意的 (不要自滿 .\/.)
據說在 onsite 還有前三.. 算是一個 suprise 吧

學習一下 kn 的紀錄方法



Summary
Team members: GagGuy, AlanC
Solved: 8/9
Penalty: 975



Process
25 - I (+0)  本身在寫C的2-SAT, AC 說很頹便先做
46 - C (+0)  發現原來不是2-SAT, 只是普通DFS, 浪費了不少時間..
69 - E (+2)  AC 做的, array 開小了
86 - B (+0)  AC 看的, 本身無咩頭緒, 佢話係二分+貪心, 加左自己的猜想, 其實個算法沒有prove到的, 有點水過的感覺
104 - G (+0)  shortest path by AC
146 - F (+0)  DP, 其實不簡單的, 只是之前做過USACO很相似的版本, 當時還是看solution才做到
217 - H (+0)  bipartile matching by AC, build graph 看上去很煩
222 - D (+1)  convex hull, 一開始睇錯題目以為好難, 後來AC更正返+講埋solution, 我只係做coder XD 一開始用 monotone chain 把共線的點都 push 入 stack 又忘了開大 stack 而錯了一棍





Unsolved

A - 難+煩的geom, 有少少想法, 最後還是沒 code 出來.. (雖然有一小時剩, 剩30mins時回家了)




Reflection

其實今次個 system 不斷出現技術上的問題, 好多題都無緣無故一開始俾左個錯的 feedback (AC->WA, WA->AC), round down 又其實係 round up, EOF 寫做 0 0, 如果無呢d 真係可以再快好多
不過我覺得最大得著唔係 rank 或是和其它隊的比較, 而係對自己和隊友的進步
今次可以話打得幾順, 卡題情況甚少, 低級錯誤也可說是沒有, 過題時間基本上是很平均的
同埋我同AC的 coding 準繩度都不錯


另外, 合作性
我覺得今次真係合作得很好.. 基本上4hr 部機無空閒過的, 真係做到一題接一題..!
另外便是coding/debug上的合作, 可能因為大家平時打code既style都相近, 睇對方的code基本上不成問題, 而且還做到「一個打, 一個check」的 stragery
諗algo方面, 其實我覺得大家都進步左/成熟左, 可能是今次的題目簡單?
其實我覺得我和AC的默契真的不錯, 邊個上機/睇題目都好流暢, 大家都發揮好高既efficiency


改善方面, 今次無帶武器, 發現自己有些算法不是很熟 (matching/convex hull)
而且今次的題目也算是我們熟悉的 topic (沒有 Nim/geom/difficult maths 等) , 所以未來還是應該要去接觸更多的 topic

GCJ 2010 Round 1A

朝早九點開波..

A - "K"子棋, given current state, 問 rotate 90^o 後邊一邊會勝出 (可以both/neither)
但開頭 score 分佈出錯左, 以為有 trap, 所以無即刻揼.. 決定睇埋B,C先

B - given sequence {An} in [0,255], 可以 add/delete/change (各自有 cost) , 目標係試 neighbour 的 difference <= M, 求 min cost

C - 兩人玩的game, 一開始有兩個數 (A,B), 每一個 step 可以改為 (A , B-A*k) 或 (A-B*k , A) , k 是正整數, 問某個 range 入面有幾多 pair (A,B) 是 winning state



analyze下, B 明顯係 DP, 應該幾輕鬆 ; 但 C 疑似 Nim game 果類, 基本上係未 code 過
之後佢出 clarification 改返分數, 發現 A 佔分最少, 於是放心去寫A, 大約 30 mins 時 A-small  Correct!


今次打算用一個 strategy - 唔隊 large 住, 之後有時間再 double check 多次, 因為 large 得一次機會同埋GCJ 計時間係計最後 submission, 對penalty無咩影響 (如果之後會再 submit 的話)
寫 B - DP, change 同 delete 好易 handle, add 諗左一陣, 確定係 round up 除法, 過 test case, Correct!


之後就朝 C 進發
C - 睇多睇又唔似 nim, 於是用 memorization 的方法去打個表搵observation, 得到
 123456789
1*........
2.**......
3.***.....
4..****...
5...*****.
6...******


很明顯地有 pattern -- 之後就陷入一小時的掙扎
一開始以為係好簡單既 pattern, 但試左幾個 sequence 後後面又總係唔 work, 於是出動武器 - KMP 用電腦去搵 pattern, 但 turns out 佢係無一個 "repeat" 既 component ..!
唔忿氣, 出動埋 guassian , 話唔定係一條 polynomial , 入左頭 5 個數落去就知唔 work - solve 出黎的 coefficient 唔係 integer ... 睇黎條 sequence 唔係 polynomial ..


諗
諗
諗


剩返 20 mins 果陣, 突然發現

 123456789
1*........
2.**......
3.***.....
4..****...
5...*****.
6...******



每一行/列 * 的數目 等於 果行/列 的篇號!
諗深一層, 其實係同 self-describe sequence 差唔多  突然感覺到離答案只差一步

揼... 揼... 揼...

大約剩返 8 mins 時揼好, submit, Incorrect
灰左一灰, 但立即想到是 BIT 越界問題, 改, Correct!




Result ..

113

gagguy Me

100

2:30:38

32:50

1:36:12

50:27

1:39:01

2:26:02 1 wrong try

2:26:38

不過最滿足都係做到條 C







後記

睇返 official report, 原來 B 有 O(NM) 的做法, C 和 golden ratio 有關
GCJ 牽涉的範疇真的很廣泛, 學多d野才是上策

Code Forces Contest #11

這次的題目對我來說比較 thinkable 呢
一如以往, A 和 B 理論上都可以秒殺的, 不過 B 看漏了 input 可以 < 0 , WA 了一棍

C 是 given 一個 n*m 的01 matrix, 要數有幾多個由1圍成的 square , 一個 square 有兩種:

A)
01110
01010
01110
B)
00100
01010
10001
01010
00100

以且那些 square 不能在 edge or corner touch 到其它不屬於果個 square 邊界的 1, 例如
00001
01110
01110
01110
00000

n,m <= 250



D 是 given 一個 undirected graph, 數有幾多個 simple cycle (無self-cycle, 無 repeated edge/node)
|V| <= 19