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..