Showing posts with label Training. Show all posts
Showing posts with label Training. Show all posts
Saturday, 13 November 2010
Tuesday, 26 October 2010
Tuesday, 19 October 2010
Saturday, 16 October 2010
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的
是帶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的
Thursday, 7 October 2010
Tuesday, 5 October 2010
Thursday, 30 September 2010
Wednesday, 22 September 2010
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(N3)解決
做 geom 其實幾有趣的 (如果唔使處理精度)
H - Heapsort
有容易有 idea 但又唔知點 code 那種題..
目標是每次將 1 shift down 到 label 最大的 node
做法先把 heap 的 node label, 每次再把 heap[1] map 返做 pop number
G - Gunman
其實不是第一次看到這題目, 不過 training 才認真想
turns out 可以分做 x axis 和 y axis 做
y axis 較簡單, 因為 fix 了一點, 只是處理一些 slope
x axis 則較複雜, 但其實是經典問題, 如果存在 valid 的線的話一定可以 rotate 到直至碰到兩點, 所以可以O(N3)解決
做 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
部份搜索法, 未過到
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
部份搜索法, 未過到
Sunday, 5 September 2010
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(N2), 而最多合併 N-1 次
所以總時間為 O(N3)
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(2n), 要用到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(E2)
之後想到用 augmenting cycle 的概念
for 每個 node, 搵哂所有由佢出發的 cycle, 途中所走的 edge 就是可選的 edge
但這個方法是O(VE), 也過不到
最後想到, 要搵所有 cycle 出黎可以用 SCC!
首先對個圖 (只走 augmenting path) 做 SCC
然後 check 所有由左連去右的 edge, 如果佢地係同一個 SCC, 咁 implies 佢地係一個 augmenting cycle 入面, 咁即係可以用
KO!
很優美的一條:D
估唔到SCC都可以同flow類扯上關係..
不過也沒有想像中難
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(N2), 而最多合併 N-1 次
所以總時間為 O(N3)
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(2n), 要用到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(E2)
之後想到用 augmenting cycle 的概念
for 每個 node, 搵哂所有由佢出發的 cycle, 途中所走的 edge 就是可選的 edge
但這個方法是O(VE), 也過不到
最後想到, 要搵所有 cycle 出黎可以用 SCC!
首先對個圖 (只走 augmenting path) 做 SCC
然後 check 所有由左連去右的 edge, 如果佢地係同一個 SCC, 咁 implies 佢地係一個 augmenting cycle 入面, 咁即係可以用
KO!
很優美的一條:D
估唔到SCC都可以同flow類扯上關係..
Wednesday, 28 July 2010
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 完成
上次還有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得很快
其中一題比較有趣
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得很快
Wednesday, 14 July 2010
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有關的題目.. 未識做
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有關的題目.. 未識做
Wednesday, 30 June 2010
Individual Training 29/06/2010
F - PKU 1065 Wooden Sticks
給定 N 組數 (ai, bi), 每次用一個 cost 可以 cover 一條 sequence 且每項的 (ai, bi) 都小於之後的那項, 問 min cost
首先很直觀的想到用greedy, sort by (a,b), 然後順著做, 如果未被 cover 就拎, 再順序掃後面的, 拎到就拎
這個greedy是對的, 時間O(N2)
後來學到 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
之後順序判斷+合併就是了, 要注恴的是無限slope的segment
由於見input只去到小數後兩位, 明顯地可以純整數咁做 (記分數form), 由於我用左
去食input
WA 兩棍後才發現我會將例如 3.05 和 3.5 都化作 305
頗深刻的bug
給定 N 組數 (ai, bi), 每次用一個 cost 可以 cover 一條 sequence 且每項的 (ai, bi) 都小於之後的那項, 問 min cost
首先很直觀的想到用greedy, sort by (a,b), 然後順著做, 如果未被 cover 就拎, 再順序掃後面的, 拎到就拎
這個greedy是對的, 時間O(N2)
後來學到 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
- 斜率
- y - 截距
- x1 值 (設 x1<x2)
之後順序判斷+合併就是了, 要注恴的是無限slope的segment
由於見input只去到小數後兩位, 明顯地可以純整數咁做 (記分數form), 由於我用左
scanf("%d.%d",&x,&y);
p=x*100+y;
去食input
WA 兩棍後才發現我會將例如 3.05 和 3.5 都化作 305
頗深刻的bug
Wednesday, 23 June 2010
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
搵 a1^a2^a3...^an mod m
有少少想法.. 但如果真係要做應該有排 struggle ...
比較興奮的是做到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
搵 a1^a2^a3...^an mod m
有少少想法.. 但如果真係要做應該有排 struggle ...
Wednesday, 2 June 2010
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 | 3:42 | 1:09 | 2:26 | 1:44 | 3:37 | 0:25 | 8 | 975 | |
| 2 | chin | 1:23 | 1:58 | 3:15 | 2:11 | 4:26 | 0:48 | 2:48 | 0:30 | 8 | 1139 | |
| 3 | dannyyip | 4:01 | 2:26 | 1:17 | 2:58 | 4:16 | 0:45 | 6 | 1063 | |||
| 4 | Prof.QQ | 2:18 | 3:08 | 0:30 | 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
Subscribe to:
Posts (Atom)