網頁

Wednesday 26 January 2011

CodeForces Contest #53

題目
Scoreboard

A - Square Earth?
看了兩次才看明題目, 我的做法是給每一點一個label, 最後兩點相減
看到很多人都用分case的方法, 但不少人寫漏了case, 因此得到了不少hacking 分:D


B - Martian Architecture
我的做法是先找出每一點的高度, 對於每一個update (a,b,c), 可寫成
add[a]+=c;
chg[a]++;
add[b+1]-=c+a-b;
chg[b]--;
之後traverse一次array便可求出每一點的高度

Submit 第一次錯了, 但又找不到bug, 用了5分鐘才發現是把所有query的答案加起而不是續個output...
Hacking 時發現有 O(QM) 的做法, 十分簡潔


C - Array
數increasing+decreasing sequence的數目, 由於想不到公式, 因此先找出細case的答案, 然後當然是OEIS :D
得出公式是 C(2n,n)-n
老老實實, 答案要mod P, 因此要找 n! 的 inverse, 其實上了CSCI2110 才懂做的
後來發現每個dp[n][k]都對應 C(n+k-1,n), 總算接受了條公式


D - Journey
其實是問所有pair的total path length
對於每點 (X,Y), 計算在 total path 中 X 和 Y 分別被加和減了多少次
但有些path 不是走 shortest path 的, 因此要對每條這樣的 path +2
很可惜地, 我漏數了一些 case, 因此在 system test 中 fail 了

最後由於有7個hacking 和很多人也 fail 了 D (pretest 很弱), 離奇地排到第 15
也升了紅色:D

CodeForces Contest #51

題目
Scoreboard

A - Flea travel
直覺是當 t>N 就不會再去一些未去過的 node, 因此用O(N)頹做就submit了
後來再check, 發現只有 N 是 2 的 power 時才會行哂所有 node


B - Smallest number
應該有一些 greedy 方法, 不過由於懶加上只有4個數字, 就用vector 暴力枚舉
後來看到別人一些「正解」的方法: 加則加最大的兩個數, 乘則乘最小的兩個數


C - Pie or die
在紙上畫畫下, 發現/覺得只要考慮最接近邊界的一個點
第一次submit時是判斷距離<=3, 過不到pretest, 才發現應該是距離<=5
(其實這個錯頗幸運的, 因為如果寫距離<=4 是過到pretest 的)


E - Very simple problem
由於 D 是看似很難的數論, 又發現E 是geom, 便覺得可以一試
E 是 given 一個 convex polygon 和一點 p (保證不在 polygon 任意兩頂點連成的線上), 問有多少種方法選 polygon 的三點形成一個三角形使得 p 在三角形內



做法: 先預處理每一個頂點連到該點的線左邊有甚麼點 (如圖, Right(E) = {A,B,F})
我用binary search 做, 但其實可以一度做一度 rotate

然後, 枚舉三角形其中一點
假設其中一個包含 p 的三角形 XYZ, 必有 Y in Right(X) 和 Z in Right(Y)
這個可以用類似 partial sum 的方法做 (方便起見, 我寫得時侯是由 1 到 2n 的)
但也會數了像 EFA 的三角形, 所以最後要減去 C(|Right(x)|,2)

由於做到 E, 使得排名很幸運地入到頭 20, 開心了好一會

Thursday 20 January 2011

Xian 2006 - Gargoyle

雖然是上星期做的題目, 但還是想記錄下來
是 Lower Bound Min Cost Equal Flow

首先, 要找出 equal edge set 流量的 feasible range
根據論文[1], 這個 range 會是連續的, 即是 [0, u] 的 form
但是, 這題有 lower bound 的限制, 所以 range 應該會是 [l, u]

然後就想找 feasible range, 分別對上下界做 binary search
但是, 在做 binary search 時需要知道是大於 upper bound 還是小於 lower bound
一開始完全沒頭緒, 後來觀察到兩種情況下不滿流的邊是不同的, 就解決了這個問題

然後有一點要注意, equal edge set 取最小可行值 不等於 最小費用
再一次根據論文, cost 在 [l, u] 中是一個 convex function
所以可以用 ternary search 去找 min cost


[1] Algorithms for the Simple Equal Flow Problem, Ravindra K. Ahuja, James B. Orlin, Giovanni M. Sechi, Paola Zuddas

Saturday 8 January 2011

URAL 1043 - Cover an Arc

First, find the center and the radius of the circle.
Since we are looking for a bounding rectangle, we need to calculate minX, maxX, minY, maxY.

Intuition: Just compare with the up-most, leftmost, rightmost and the down-most point of the circle!
Next, we have to determine whether a point on a circle is on an arc.

Arrange the two ends of the arc A,B such that A->B is clockwise.
To check whether P is on the arc, just see whether triangle APB is clockwise or not, which can be easily done by cross product.

Last Bug:
mnx = (int)(mnx+1e-10);
mny = (int)(mny+1e-10);
mxx = ceil(mxx-1e-10);
mxy = ceil(mxy-1e-10);

Correct version:
mnx = floor(mnx+1e-10);
mny = floor(mny+1e-10);
mxx = ceil(mxx-1e-10);
mxy = ceil(mxy-1e-10);

Incorrect version won't work with negative numbers..

Friday 7 January 2011

URAL 1130 - Nikifor's Walk


好像是很經典的題, 題解十分巧妙
做法在這裏

回溯答案我用了tree去記錄, 如果merge i+j, 則由i到j連一條weight 0的edge; 如果merge i-j, 則連weight 1的邊, 最後從source做一次dfs
其實那些properties對我來說並不明顯, 所以還是在這裏做個記錄吧


Claim 1. For any two vectors u,v where |u|,|v| <= L, either |u+v| <= sqrt(2)*L or |u-v| <= sqrt(2)*L

Proof.
|u+v|2 = |u|2+|v|2-2|u||v|cos(θ)
|u-v|2 = |u|2+|v|2+2|u||v|cos(θ)
In either case, the square of magnitude will not greater than |u|2+|v|2 = 2*L2


Claim 2. For any three vectors length not greater than L, it is always possible to choose 2 of them such that the length resultant vector performing addition OR subtraction is not greater than L.


Proof.
I seen a proof on other's blog using the formula above, using the fact that there must exists a θ >= 120 degree.

Let three vectors be v,w,u.



Let the brown vector = v.
If v+w or v+u falls in yellow, then the length of v+w or v+u <= L
Else if v+w or v+u falls in red, then the length of v-w or v-u <= L
Else, v+w and v+u falls in blue or green, then the length of w+u or w-u <= L

Tuesday 4 January 2011

IOI 2008 Pyramid Base

揼了 200 行 code
應該是 IOI 有史以來 code length 最長的題目

其實咁複雜是因為 CASE 3 和 CASE 1, 2 的 approach 是不同的, 所以要分開兩段 code 去寫
做法分為 (1) Budget≠0 (2) Budget=0

對於(1), 可以 O(P * lg(P)* lg(Min(W, H)) 解決
對於(2), 可以 O(P * lg(P)) 解決

(1)
對答案做 binary search, 設 search length = d
想知有冇得 cover 一個 d * d 的 square 等同於將每一個 obstacle 向左和向下延伸d格, 然後睇下有冇一格個cost ≤ budget
用 segment tree 實現, 每個 node 記住 cover 和 best

(2)
對於 bugdet = 0, 即是要找全空的最大正方形
方法是, 用兩支指針指著 x1, x2, 每次 x1++ 就增加 x2 使得在 [x1, x2] 中最長的連續空白 ≥ (x2-x1+1)
也是要用 segment tree, 每個 node 記 cover, left max, right max, max

由於 W, H 可以去到 1,000,000, 所以一是離散 y 軸, 或者動態開樹
動態開樹應該比較易寫, 出錯的機會也較低

Saturday 1 January 2011

2010比賽總結


CCC Stage 1

基本上5條都識做, 係第5條input非常煩膠, 但出來的成積只有58/75, 比想像中低很多, 雖然也是第一
雖然CCC不是甚麼大比賽, 也撞了AL沒去stage2 (而且覺得暑假已經會去UW, 去年都去過)
很快便淡忘了

TopCoder High School

頭500有T-shirt, 但參加人數<500, 所以好像沒有甚麼壓力
R1,2打得頗不錯的, 但R3,4卻是悲劇, 印象中兩次也錯了些很低級的錯 記得打得最好的一次入到TOP25的

IOI/NOI TFT

第四次玩TFT, 這次做完時的感覺很差, 而出來的成積比想像中又是低了很多, 可能RP高剛好可以去IOI
第4條的bug非常低級, 真是太感激CTLi第3條讓我水到90分了, 否則便兩手空空而回
最後不得一提, 其實我連續3年TFT第3
總覺得自己這兩年的TFT都發揮都很差, 可能是緊張吧

Google Code Jam

R1a非常順利, 以滿分進入R2
而R2剛好就是TFT的晚上, 不知怎麼的在HKU lab打, 打到一半又要回家, 結果當然就是非常的差, 而且可能是TFT用盡了RP, 加上十分疲累, 竟然rank 502 (頭500入R3)
幸好後來有2個人被DQ (有一個更是在R3開始前數分鐘才被DQ), 入到R3, 不過也不是打得很好
總括來說就是實力不足, 對著題目無從入手

IOI 2010

出發時剛好去完細o, 可能因為不夠睡弄得有點病, 幸好在機上長睡後便沒事
每年去IOI的感覺都不同, 一開始總覺得和其它三人有點不熟, 但最後的效果很好很有趣
以食物來說, 今年的最難吃。不過其實我很享受去cafe, 酒吧和蒙古燒那三餐 (不論是食物還是吹水方面)
day1 打得還不錯的, 雖然rank只有4x, 但其實分數差距很小, 而且再打也應該差不多
day2 回想很失策。maze那題聽完Fai的做法, 就覺得自己浪費了2小時去opt果幾分, 而且我覺得自己有機會去想到safeit的
雖然只是假設性, 但好像因此而灰了一段時間
最終也沒能取得IOI金, 十分遺憾

第一年NOI, 銅2, 差一點銀
第二年IOI, 銀4, 差一點金
不過最接近, 最有機會IOI金的還是IOI09, 其中salesman我做了85便去想region, 但那15分本應是唾手可得的, 十分遺憾
三次IOI和一次NOI的經歷是我十分喜歡的, 雖然回想起來4次也表現得不好(用ideal case的角度看), 但那些時光真是十分快樂

Jakarta Regional

IsolatE第一場實戰, 不少失誤, 但294AC真的很興奮
總結是IsolatE潛力很大, 進步空間也很大

KaoHsiung Regional

好像除了開局時做的簡單題外就沒有了
B過不到是我的責任, 雖然不是說過就能過, 但也顯示了我的經驗不足和實力不足


總括來說, 這一年的比賽好像沒有哪個是滿意的, 即是說2011還要繼續努力