d1 & d2 一齊打既比賽。
最後因為條B official soln 出錯變成unrated...如果rated應該會升的..
只做了A,B,C
不過條B 如大部分人一樣都係比佢陰左..題目本身出得很好, 個trick好反直感。
A:
頹, simulation
B:
其實題目就係要你搵min / max of avg of given既cards, 同埋剩番落黎足夠theorems可以組成一張card (視乎min定max, 總之sort左佢一路pick就係). 陰位係: 由於題目講明卡可以重複出現, 但一題題目只會出現係一張卡上面, total係有k 張卡的, 姐係話如果你已經知道哂所有 k 張卡, 而剩番既theorems仲可以組多一張卡, 咁答案都仍然係given 個k 張卡入面搵...
唉
C:
DP...雖然人地話好standard, 但我覺得唔算太容易..所以比賽入面過到真係幾開心。
思考過程有兩個observation, 第一, sort by complexity 先再做dp, 不過做dp時仍然要check到transition時唔可以由一樣complexity既update (因為要strictly increasing) ; 第二, 我諗好明顯, bi - ai <=100 而ai 同 bi <=10^16!! 記得ZQ講過呢d好明顯就要諗下點利用。 不過先將呢個問題放係一邊, 直接諗下state 同transition先~
state: dp( X, i , n ) := max total # of homework from 0 to i lessons, pick up n lessons, and the i-th lesson have X+a[i] homework
transition:
dp(X, i, n) =
max ( dp (X+a[i] - k - a[j], j , n -1), if( (X+a[i])%k==0) { dp((X+a[i])/k - a[j], j, n-1} )
for all j < i
奇妙就係度..因為bi - ai <=100 , 所以我用offset X , 0<=X<=100 黎代表第 i 個lesson既homework 數都係得既! 咁樣table size就係 100 * 50 * 50 , 非常合理既數字, 亦都大大提升左我對呢個做法既信心
當然仲有好多野要handle.. X +a[i] <= b[i] 啦.. complexity 要strictly increasing 啦..
call答案時 試哂所有X 同 i (因為可以係簡頭個d 已唔簡後面個d, 如果直接將 i 變做m 會錯)
tX = X in argmax (dp (X , i, n) )
tI = i in argmax( dp(X , i, n) )
最後recursion trace條path出黎就ko~
ps: 記錄條path 都幾麻煩...由於無咩時間加唔識, 夾硬用pair < int, pair<int, int> > naive記住parent (o:以後可以試下用map<node , id> ... by gary
2011年10月15日 星期六
2011年10月5日 星期三
PKU 2411, PKU 3797
糾結, 唔係尋晚TRAINING都唔知DP真係 一D都唔X識 (O:
PKU3797 EXACTLY係 GYN 個題
PKU 2411 係general 版 (for small h, w)
ps: 呢個問題有combinatorics既formula, 類似summation of sqrt( f(h,w) ); where f(h,w) 係 有cos function
==> for large h,w 就要用呢條野了..放入武器吧 =.=?
詳情google下d 解題報告就會見到
back to the question,
問題: given 一個 h * w 既grid, 有幾多種方法可以用 2*1 domino 鋪滿
想, 加睇人code, 學識左一個極簡單code法, code落仲有d微少野學到
思路:
dp 四大元素: state define, transition, base case, 答案既state
state: dp( i , mask) := 直到第 i 行的masking 為 mask, 共有幾多種排法
base case: 第 0 行 所有可行既mask x, 設dp(0, x) 為1
答案 : dp( h, (1<<w) - 1)
transition: 重點要理解既部分..為左自己記憶深刻, 詳細說明之
首先設 bit 1 代表該格已經放左野, 0 就係無, 注意此處未有咩打橫打直既考慮
假設依家我想做緊 第 i 行, 已知第 i - 1 行既state, 例如 1001
顯然 第2 , 3 個bit 一定要放一個打直既domino 黎填上面既空位
so 可行既state 一定係咁既樣: x11x where x 係未知數, 注意呢度既1 係代表打直既domino
so 點樣先知x 係咩呢?
其實輕鬆 recursion, 0同1都試下就ok, 不過 係呢一步放既一定要打橫既domino, 即一定要連住兩個1
當然, x 可以係一個打直既domino as well (霸左 第 (i, j) 同 下一行既(i+1, j) )
但係唔使理佢, 只要留佢係0, 做第 i+1行時自然會補番個 1 做到相同既configuration
so transition係: dp( i, mask ) = sum of dp(i-1, possible mask such that row i can be mask)
講咁多, 其實因為好吊詭地, 打直同打橫唔係太重要, 又或者應該話...
打直同打橫唔係直接可以表示到出黎, 所以較難明..
同一個bitmask : 例如 "1111" 配合唔同既 上一行 (只關上一行事) 可以係完全唔同既configuration:
那麼第2行也只可以放個打橫的吧, 而第2行的狀態亦為"11", 所以 dp(2, "11") 現在是 1
來看第二種排法: 我們想要2個打直的domino.
而第一行的狀態是"00" (不是"11" ! 我們希望透過"00", 讓下一行發現有空格從而補上一個 "1" , 代表打直來填補)
最後在紀錄第二行時, 正如上面所講, 我地被迫要放兩個"1" , 以填補正上方既空格
所以, 第二行的狀態都是 "11", 但代表不同的排法。
但所表示 "排滿第二行" 的狀態還是叫 dp( 2, "11" )
最後dp(2,"11") 就是 2
簡易版code:
注1: ~a 係 bit negate, 不過會連埋sign bit , so ~a & ((1<<a)-1) 先做到想要既效果
注2: 1<<a+1 = 1<<(a+1)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL dp[20][1<<12];
int h,w;
// given a state , update all state wif horizontal block
void d(int st, int i, int pos, LL from){
if(pos >= w){dp[i][st] += (i==0? 1: from ); return;}
d(st,i,pos+1, from);
if(pos+1<w && !(st & (1<<pos)) && !(st&(1<<pos+1)))
d(st | (1<<pos) | (1<<pos+1), i, pos+2, from);
}
int main(){
while(scanf("%d%d", &h,&w), h||w){
memset(dp,0,sizeof(dp));
d(0,0,0,0);
for(int i=1; i<h;i++){
for(int j=0; j < (1<<w);j++){
if(!dp[i-1][j]) continue;
d(~j & ((1<<w)-1), i, 0, dp[i-1][j]);
}
}
printf("%lld\n", dp[h-1][(1<<w)-1]);
}
return 0;
}
PKU3797 EXACTLY係 GYN 個題
PKU 2411 係general 版 (for small h, w)
ps: 呢個問題有combinatorics既formula, 類似summation of sqrt( f(h,w) ); where f(h,w) 係 有cos function
==> for large h,w 就要用呢條野了..放入武器吧 =.=?
詳情google下d 解題報告就會見到
back to the question,
問題: given 一個 h * w 既grid, 有幾多種方法可以用 2*1 domino 鋪滿
想, 加睇人code, 學識左一個極簡單code法, code落仲有d微少野學到
思路:
dp 四大元素: state define, transition, base case, 答案既state
state: dp( i , mask) := 直到第 i 行的masking 為 mask, 共有幾多種排法
base case: 第 0 行 所有可行既mask x, 設dp(0, x) 為1
答案 : dp( h, (1<<w) - 1)
transition: 重點要理解既部分..為左自己記憶深刻, 詳細說明之
首先設 bit 1 代表該格已經放左野, 0 就係無, 注意此處未有咩打橫打直既考慮
假設依家我想做緊 第 i 行, 已知第 i - 1 行既state, 例如 1001
顯然 第2 , 3 個bit 一定要放一個打直既domino 黎填上面既空位
so 可行既state 一定係咁既樣: x11x where x 係未知數, 注意呢度既1 係代表打直既domino
so 點樣先知x 係咩呢?
其實輕鬆 recursion, 0同1都試下就ok, 不過 係呢一步放既一定要打橫既domino, 即一定要連住兩個1
當然, x 可以係一個打直既domino as well (霸左 第 (i, j) 同 下一行既(i+1, j) )
但係唔使理佢, 只要留佢係0, 做第 i+1行時自然會補番個 1 做到相同既configuration
so transition係: dp( i, mask ) = sum of dp(i-1, possible mask such that row i can be mask)
講咁多, 其實因為好吊詭地, 打直同打橫唔係太重要, 又或者應該話...
打直同打橫唔係直接可以表示到出黎, 所以較難明..
同一個bitmask : 例如 "1111" 配合唔同既 上一行 (只關上一行事) 可以係完全唔同既configuration:
以一個2*2的版面說明, 假設第一行是一個橫放的domino, 那第一行的mask 就是"11"
而第一行的狀態是"00" (不是"11" ! 我們希望透過"00", 讓下一行發現有空格從而補上一個 "1" , 代表打直來填補)
所以, 第二行的狀態都是 "11", 但代表不同的排法。
但所表示 "排滿第二行" 的狀態還是叫 dp( 2, "11" )
最後dp(2,"11") 就是 2
簡易版code:
注1: ~a 係 bit negate, 不過會連埋sign bit , so ~a & ((1<<a)-1) 先做到想要既效果
注2: 1<<a+1 = 1<<(a+1)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL dp[20][1<<12];
int h,w;
// given a state , update all state wif horizontal block
void d(int st, int i, int pos, LL from){
if(pos >= w){dp[i][st] += (i==0? 1: from ); return;}
d(st,i,pos+1, from);
if(pos+1<w && !(st & (1<<pos)) && !(st&(1<<pos+1)))
d(st | (1<<pos) | (1<<pos+1), i, pos+2, from);
}
int main(){
while(scanf("%d%d", &h,&w), h||w){
memset(dp,0,sizeof(dp));
d(0,0,0,0);
for(int i=1; i<h;i++){
for(int j=0; j < (1<<w);j++){
if(!dp[i-1][j]) continue;
d(~j & ((1<<w)-1), i, 0, dp[i-1][j]);
}
}
printf("%lld\n", dp[h-1][(1<<w)-1]);
}
return 0;
}
2011年9月25日 星期日
4條近日的graph題目 - Codeforce#88C, ICPC4218 , ICPC4210, POJ3522
我好像是負責隊中的GRAPH, GEOM 和 (SIMULATION?) 老實說SIMULATION 信心很小, 因為很少做相關題目
前幾天上立志的GRAPH課大開眼界...知道GRAPH世界好大好大, 目前第一步還是先把TEXTBOOK PROBLEM學好, CODE得出 CODE得快。
做了幾道GRAPH題, 再把matching , AP, bridge那些相關題目做多一點就要轉攻geom了吧..?
雖說regional 出的機率很小就是了..
Codeforces #88C
很特殊既一題graph...雖然佢地大家都覺得好頹..
比賽中我fail system test, 但原來係錯柒bug...一有得practice再改就過了..起碼諗法係岩既
題目:
given 1個tournament (ref: http://en.wikipedia.org/wiki/Tournament_(graph_theory) )
verify 有無 3-length cycle, 有則output 任意一個solution( 3 個vertex id), 無則output -1
畫呀畫, 畫呀畫, 發現由於圖特殊
如果搵到any length既directed cycle, 呢個cycle入面一定就有 3-length cycle
我估大約可以用mi proof, but 可以畫幅類似self explained既圖:
黑edge既係搵到既 n length directed cycle, 顯然(!?) n 係幾多都無所謂。 紅線係greedy 地 唔想造成3-length cycle 既edge, 藍線係最後一條, 發現, 點畫都好, 一定會造成3-length cycle。(而紅線如果掉轉方向, 一早就會造成3-length cycle)
好, 當claim已岩, 點搵 呢個3-length cycle出黎呢?
by observation(雖然場上係帶點guessing), 呢個3-length cycle 其中 2粒一定係連住(可以試下掉轉d 紅線試下)
So...Algo 就係:
1. DFS 搵DIRECTED CYCLE
2. N^2 睇下有無 a_i, a_i+1, ???? 造成3-length cycle
ps: step 2 chin爺貌似係O(n) 都做到, GG/ whh 直頭唔係咁做...sign
ICPC4218
Training 既一題題目...其實過左都好似無過咁, 覺得下次未必做得出..at least比賽上做唔到的吧。
題目:
Given n個城市, 每個城市有兩支有顏色的旗, 假設城市A , 有R 旗及 B 旗
要進入A, 身上就要先帶住R旗或B旗;
當你離開某個城市時, 可以獲得另一種旗, i.e: 你用R旗進入A, 離開時則帶著B旗, or vice versa。
問: 任意從一個城市開始, 能否travel 全部城市, 並且全部城市只經過一次? 如果可以則output 開始的城市id , multiple ans時則output id最小的。
當時完全無idea。之後學會euler path, 知道此題係euler path應用題。
跟uva necklace 一樣, 將顏色當做node, 城市當做edge, 有self loop 和 multiple edges, 問題便由NPC的TSP 變成P 的euler path了。
然後還剩一個問題: 如何找id 最小的起始點? 來個分析:
1. 先查existence of euler path: connected 和 odd degree node = 0 or 2
2. 若odd degree node = 0, 就是有euler circuit了, 就是從任何點出發都可以, 所以 答案直接就是最小的城市id
3. 若odd degree node = 2, 可以出發的城市(亦即圖中的edge) 就是這兩個node 連住的 edge
問題是要找出可以行並且id 最細的城市( 就是說是圖中的edge啦, edge!)
idea 就是: remove 該條edge, 然後check 圖會否變成edge disjoint。
==> simply dfs
然而 implement上好多野要注意...亦係我擔心既主因, implement 上可以
查哂所有edge, 當 兩端有一粒係 odd degree先進一步test。
PS: 呢題最煩係個INPUT...亂咁黎, 轉換成graph 都搞左好一陣...
ICPC4210
係acm wiki上面搵到既practice 題目, Singapore 2007年。
被chin爺X, 因為話咁樣又少左一個SITE 用黎打team training...我都係睇左呢題姐..
題意:
given 一個connected SIMPLE undirected weighted graph, 圖中可能會有好多loop, 問如果每個loop 上面都最小要pick一條edge, minimum total cost係幾多
kn一句: 試下exhaust 所有你識既graph algo。
果然很快就發現, 根本就係maximum spanning tree嘛
原圖減走max spanning tree就係要安裝偷拍器材既road
今日再認真諗下correctness先code, 覺得好直觀嘛?
因為spanning tree T, for 每一個loop 當有n 條edge, 咁T 一定係包左入面n-1 條weight最大的edge,
剩番個條就係cover左呢個loop 而 cost最小既edge了 。
夾硬要話有咩theorem, 我會覺得係326學既red rule定blue rule吧?
POJ3522
kn比既一條題目, interesting~
題意:
define SLIMNESS(瘦度?) of a spanning tree T is the highest T's edge cost - smallest T's edge cost
given 一個simple graph, 係眾多spanning tree 入面, find the one with smallest slimness。(just output the required slimness)
無咩idea as well, 諗左一陣, 發現題目好好, given 埋spanning tree既definition; 而入面又強調: spanning tree係 for n vertex, 有n-1 條edge...
加上圖係simple,
我就發現...有個頹algo!! 其實就係greedy 咁試..
先sort by weight,
試諗下, 當 edge i 係某spanning tree入面weight 最細既edge
咁我要搵多 n-2條edge such that 佢地form到一棵tree。
假設所有 edge j, for all j > i, 都係possible既edge, 咁第 (i + (n-2)) 條edge 一定係最optimal
(因為第 (i+(n-1)) 條edge 或者之後既edge, weight 都會再大d, 自然difference 就再大d了.. 對於同一個minimum edge i 黎講)
所以algo就好明顯了
1. sort m 條edge by it's weight
2 fix i as minimum weight edge, linearly find n-2 more possible edge (by disjoint set checking, like normal mst algorithm!) for all i !
3 take minimum !!
嗚呀..其實, 好似仲未點做過matching / bridge / AP 既題目, 仲有geom, 仲有simulation
其實仲有fyp * 2, 仲有414...嗚呀呀呀呀呀呀呀呀呀呀呀呀!!!!!!!!
前幾天上立志的GRAPH課大開眼界...知道GRAPH世界好大好大, 目前第一步還是先把TEXTBOOK PROBLEM學好, CODE得出 CODE得快。
做了幾道GRAPH題, 再把matching , AP, bridge那些相關題目做多一點就要轉攻geom了吧..?
雖說regional 出的機率很小就是了..
Codeforces #88C
很特殊既一題graph...雖然佢地大家都覺得好頹..
比賽中我fail system test, 但原來係錯柒bug...一有得practice再改就過了..起碼諗法係岩既
given 1個tournament (ref: http://en.wikipedia.org/wiki/Tournament_(graph_theory) )
verify 有無 3-length cycle, 有則output 任意一個solution( 3 個vertex id), 無則output -1
畫呀畫, 畫呀畫, 發現由於圖特殊
如果搵到any length既directed cycle, 呢個cycle入面一定就有 3-length cycle
我估大約可以用mi proof, but 可以畫幅類似self explained既圖:
好, 當claim已岩, 點搵 呢個3-length cycle出黎呢?
by observation(雖然場上係帶點guessing), 呢個3-length cycle 其中 2粒一定係連住(可以試下掉轉d 紅線試下)
So...Algo 就係:
1. DFS 搵DIRECTED CYCLE
2. N^2 睇下有無 a_i, a_i+1, ???? 造成3-length cycle
ps: step 2 chin爺貌似係O(n) 都做到, GG/ whh 直頭唔係咁做...sign
ICPC4218
Training 既一題題目...其實過左都好似無過咁, 覺得下次未必做得出..at least比賽上做唔到的吧。
題目:
Given n個城市, 每個城市有兩支有顏色的旗, 假設城市A , 有R 旗及 B 旗
要進入A, 身上就要先帶住R旗或B旗;
當你離開某個城市時, 可以獲得另一種旗, i.e: 你用R旗進入A, 離開時則帶著B旗, or vice versa。
問: 任意從一個城市開始, 能否travel 全部城市, 並且全部城市只經過一次? 如果可以則output 開始的城市id , multiple ans時則output id最小的。
當時完全無idea。之後學會euler path, 知道此題係euler path應用題。
跟uva necklace 一樣, 將顏色當做node, 城市當做edge, 有self loop 和 multiple edges, 問題便由NPC的TSP 變成P 的euler path了。
然後還剩一個問題: 如何找id 最小的起始點? 來個分析:
1. 先查existence of euler path: connected 和 odd degree node = 0 or 2
2. 若odd degree node = 0, 就是有euler circuit了, 就是從任何點出發都可以, 所以 答案直接就是最小的城市id
3. 若odd degree node = 2, 可以出發的城市(亦即圖中的edge) 就是這兩個node 連住的 edge
問題是要找出可以行並且id 最細的城市( 就是說是圖中的edge啦, edge!)
idea 就是: remove 該條edge, 然後check 圖會否變成edge disjoint。
==> simply dfs
然而 implement上好多野要注意...亦係我擔心既主因, implement 上可以
查哂所有edge, 當 兩端有一粒係 odd degree先進一步test。
PS: 呢題最煩係個INPUT...亂咁黎, 轉換成graph 都搞左好一陣...
ICPC4210
係acm wiki上面搵到既practice 題目, Singapore 2007年。
被chin爺X, 因為話咁樣又少左一個SITE 用黎打team training...我都係睇左呢題姐..
題意:
given 一個connected SIMPLE undirected weighted graph, 圖中可能會有好多loop, 問如果每個loop 上面都最小要pick一條edge, minimum total cost係幾多
kn一句: 試下exhaust 所有你識既graph algo。
果然很快就發現, 根本就係maximum spanning tree嘛
原圖減走max spanning tree就係要安裝偷拍器材既road
今日再認真諗下correctness先code, 覺得好直觀嘛?
因為spanning tree T, for 每一個loop 當有n 條edge, 咁T 一定係包左入面n-1 條weight最大的edge,
剩番個條就係cover左呢個loop 而 cost最小既edge了 。
夾硬要話有咩theorem, 我會覺得係326學既red rule定blue rule吧?
POJ3522
kn比既一條題目, interesting~
題意:
define SLIMNESS(瘦度?) of a spanning tree T is the highest T's edge cost - smallest T's edge cost
given 一個simple graph, 係眾多spanning tree 入面, find the one with smallest slimness。(just output the required slimness)
無咩idea as well, 諗左一陣, 發現題目好好, given 埋spanning tree既definition; 而入面又強調: spanning tree係 for n vertex, 有n-1 條edge...
加上圖係simple,
我就發現...有個頹algo!! 其實就係greedy 咁試..
先sort by weight,
試諗下, 當 edge i 係某spanning tree入面weight 最細既edge
咁我要搵多 n-2條edge such that 佢地form到一棵tree。
假設所有 edge j, for all j > i, 都係possible既edge, 咁第 (i + (n-2)) 條edge 一定係最optimal
(因為第 (i+(n-1)) 條edge 或者之後既edge, weight 都會再大d, 自然difference 就再大d了.. 對於同一個minimum edge i 黎講)
所以algo就好明顯了
1. sort m 條edge by it's weight
2 fix i as minimum weight edge, linearly find n-2 more possible edge (by disjoint set checking, like normal mst algorithm!) for all i !
3 take minimum !!
嗚呀..其實, 好似仲未點做過matching / bridge / AP 既題目, 仲有geom, 仲有simulation
其實仲有fyp * 2, 仲有414...嗚呀呀呀呀呀呀呀呀呀呀呀呀!!!!!!!!
2011年9月17日 星期六
入隊後處男文
2年後既我奇蹟地入左隊... 感覺唔係好真實
知道自己實力好弱, 唔想拖累隊友, 所以我諗比起學業, 提升自己比賽水平更重要吧..
見david做緊 一條visibilty 既難題(?) moth...
GG 叫我做另一題相同意味但易少少既: A Safe Way
http://poj.org/problem?id=2966
題意簡單, 算法則要做過才知道吧..而且CODING上亦好麻煩
題意: given polygon (maybe convex!) ,任意2點, a,b, find shortest path from a to b, path cannot go through the polygon (but can go along the edges)
算法如下:
1. build visibility graph for vertex of polygon & a & b
2. shortest path on the graph
Coding上就好麻煩了..
首先build visibility graph...請教左GG之後, 我既實際做法係
1. for 每pair 點, i 同 j
check mid - point 係咪 completely inside polygon (係edge上唔算)
呢度要用上 sum-of-angle 黎check as polygon maybe convex, 係edge上既直接return false
2. 如果pass 1, check intersection
--> proper intersection: 當然fail
--> improper intersection: 當 intersect 條edge 叫PQ (vector) ,如果intersect既當係[P.....Q) (無錯, 係唔包尾個個vertex, 原因....要畫下先解釋到) 則當有intersection , fail
--->else PASS!
短短幾句, 已經要寫 spfa, intersection checking, sum of angle...
還好最後過到...原來錯個一棍係係feq( ) 入面少左個 ()...雖然唔知有咩所謂...嘛
Geom果然係無底深淵, 原來仲可以玩visibility graph + shortest path...
遲下再試下moth 吧...(進化版...n個polygon =[ )
知道自己實力好弱, 唔想拖累隊友, 所以我諗比起學業, 提升自己比賽水平更重要吧..
見david做緊 一條visibilty 既難題(?) moth...
GG 叫我做另一題相同意味但易少少既: A Safe Way
http://poj.org/problem?id=2966
題意簡單, 算法則要做過才知道吧..而且CODING上亦好麻煩
題意: given polygon (maybe convex!) ,任意2點, a,b, find shortest path from a to b, path cannot go through the polygon (but can go along the edges)
算法如下:
1. build visibility graph for vertex of polygon & a & b
2. shortest path on the graph
Coding上就好麻煩了..
首先build visibility graph...請教左GG之後, 我既實際做法係
1. for 每pair 點, i 同 j
check mid - point 係咪 completely inside polygon (係edge上唔算)
呢度要用上 sum-of-angle 黎check as polygon maybe convex, 係edge上既直接return false
2. 如果pass 1, check intersection
--> proper intersection: 當然fail
--> improper intersection: 當 intersect 條edge 叫PQ (vector) ,如果intersect既當係[P.....Q) (無錯, 係唔包尾個個vertex, 原因....要畫下先解釋到) 則當有intersection , fail
--->else PASS!
短短幾句, 已經要寫 spfa, intersection checking, sum of angle...
還好最後過到...原來錯個一棍係係feq( ) 入面少左個 ()...雖然唔知有咩所謂...嘛
Geom果然係無底深淵, 原來仲可以玩visibility graph + shortest path...
遲下再試下moth 吧...(進化版...n個polygon =[ )
訂閱：
文章 (Atom)