2011年10月15日 星期六

Codeforces #90

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月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的版面說明, 假設第一行是一個橫放的domino, 那第一行的mask 就是"11"

那麼第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;
}

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...嗚呀呀呀呀呀呀呀呀呀呀呀呀!!!!!!!!

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 =[ )