2014年10月21日 星期二

[UVA] 11439 Maximizing the ICPC


github: https://github.com/wilson100hong/UVAOJ/tree/master/Volume_114/11439


This problem is a combination of binary search + general graph matching. The binary search part is easy, you just search the max ICPC that makes graph completely matched. For general matching part, you can implement Edmond's algorithm. I found java version which is very clear, or you can refer my c++ version, based on other's website 演算法筆記.

I wish I have time in future to write down a walk-through for Edmond's implementation, introducing interesting parts of blossom contract / relax, which involves some nice tricks.



這一題是一個Binary Search + General Matching的組合題。把每個選手看作node，相對的ICPC看成是edge，要做的是尋找最大的ICPC值，使得圖完全匹配。Binary Search 的部份相當簡單，而General Matching的實作相當有挑戰性。

看了網路上一些素材，演算法筆記對graph matching深入簡出：核心便是Augmented Path，matching 算法即為尋找圖中所殘留的augmented path。而augmented path只有可能從偶點 (Even Node) 出發，所以這收斂了圖searching的複雜度，也是為什麼Bipartie Matching的實作簡單的原因。了解了這個之後，就可以理解Edmond's Algorithm -- 一種general matching的算法了。Edmond's algorithm的核心是Blossom -- 也就是當偶點與偶點有cross edge時，這兩個偶點與其Least Common Ancestor形成的一個cycle，這樣特殊的集合。Blossom的特性是其上的每一點都可以被當作偶點，包含之前為 奇點(Odd Node)的點！所以augmented path現在不只是從偶點上出發了，它也可以從在blossom的奇點出發。

然而理解跟實作是兩回事。Blossom的contract 與 relax 非常的tricky，常常要把node union起來，blossom中又包著blossom，代碼非常容易寫錯。我是參考演算法筆記的C++的版本，裡面對union的處理第一次看也是一頭霧水。反而，我認為這個java的實作相當清楚易讀，是我比較喜歡的版本。

有空的話希望可以深入go through 一下 Edmond的 implementation，把幾個比較模糊的地方給釐清。


張貼者： 於 沒有留言:

2013年12月30日 星期一

[UVA] 183 Bit Maps

基本的遞迴題目 小心看懂規則 尤其是output format即可


test case

INPUT
=======
B 0 0
B 16 16
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011110000
0000000011110000
0000000011110000
0000000011110000
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011110011
0000000011110011
0000000011110000
0000000011110000
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011110010
0000000011110011
0000000011110000
0000000011110000
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 1 1
1
B 2 2
0001
B 3 3
001101010
B 4 4
0001110101010101
B 5 5
0010011101110100111110101
B 1 10
1001010101
B 10 1
0100011010
B 2 20
00111011101001101010
11010001010101000010
B 20 2
00111000000010100000
01011111000001010001
D  16  16
0
D  16  16
D0100
D  16  16
D0D101100
D  16  16
D0D1D01001100
D  16  16
D0D1D0D1011001100
D   1   1
1
D   2   2
D0001
D   3   3
DD00101D010
D   4   4
DD0011D0101D0101D0101
D   5   5
DDD0011110D0D0110DD011D101D1101
D   1  10
DDDD100D10DDD101D01
D  10   1
DDDD0100DD10D10
D   2  20
DDDD011DDD011D10DDDD1001DDD010D10DDD10D10DD01D01DDDD010D10D0D10
D  20   2
DDDDD0110DDD0110DDDD01000DDD01D100DD1D10DDD011D01
#
OUTPUT
=======

D   0   0

 D  16  16
0
D  16  16
D0100
D  16  16
D0D101100
D  16  16
D0D1D01001100
D  16  16
D0D1D0D1011001100
D   1   1
1
D   2   2
D0001
D   3   3
DD00101D010
D   4   4
DD0011D0101D0101D0101
D   5   5
DDD0011110D0D0110DD011D101D1101
D   1  10
DDDD100D10DDD101D01
D  10   1
DDDD0100DD10D10
D   2  20
DDDD011DDD011D10DDDD1001DDD010D10DDD10D10DD01D01DD
DD010D10D0D10
D  20   2
DDDDD0110DDD0110DDDD01000DDD01D100DD1D10DDD011D01
B  16  16
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111111110000000011111111000000001111111100
00000011111111000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111100000000000011110000000000001111000000
00000011110000000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111100110000000011110011000000001111000000
00000011110000000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111100100000000011110011000000001111000000
00000011110000000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B   1   1
1
B   2   2
0001
B   3   3
001101010
B   4   4
0001110101010101
B   5   5
0010011101110100111110101
B   1  10
1001010101
B  10   1
0100011010
B   2  20
0011101110100110101011010001010101000010
B  20   2
0011100000001010000001011111000001010001


張貼者： 於 沒有留言:

2013年6月24日 星期一

[Hackathon] API Hackday SF

 

    早上八點頂著貪睡的慾望，硬是跟Stan殺到舊金山參加API Hackday SF. 比賽場地在Parisoma，也就是那種專門給宅宅們週未coding取暖的空辦公室。街道充斥著酒後狂歡嘔吐物的臭味，不用咖啡就很提神，算是很酷的地方。

    API Hackday比的是看誰利用別人的API，拼出最酷的產品，也就是看誰二次創作的能力最強，就像比誰站在巨人的 肩膀上跳得更高一樣。Sponsor的APIs主要有幾類：
1. 提供e-mail API, 讓你不用自己架SMTP mail server的 SendGrid, context.io
2. communication: VOIP的twilio, video streaming的open-tok
3. API manager: 上面放著其它一堆公司的API, 如Mashery, Mashape。基本上有open你想得到的廠商的API都有。
4. 不知道來幹麻的，應該說只有sponsor但是沒派人來，而且api也不清不楚：Apiphany，BigCommerce,

   經過一番討論後，我們決定利用open-tok來架一過即時拍賣網。簡單說就是針對很希望把垃圾趕快清掉的賣家，讓他開一個限時的 video conference room。買家們可以挑選有興趣的房間加入參與拍賣，一起來享受趁火打劫的樂趣。理想中的互動是賣家用video streaming跟買家們介紹他這個蟠龍花瓶多古老多名貴，買家不斷的挑毛病殺價說你這花瓶怎麼看起來像花盆，或是互想競標加價。最後買家321成交，結案。出發點是讓拍賣過程變得即時刺激有趣，增加互動。合理性商業可能性全不在考慮，反正hackathon重視的是創意！

   實作過程不像想像中那麼順利，首先我們到12點在開工，距離結束只剩6小時。再加上我貧弱的front end，還有完全不熟悉的node.js跟express, 要不是有stan大大，恐怕這個idea會一直都只是idea。話雖如此，進度也是嚴重落後，到了四點時只把最基本的首頁(商品頁)做好.…不過工程師的效率一向都是exponential的，越到最後關頭越強大，越到最後關頭越隨便....來不及做的server push也只好砍了。甚至slide是最後一分鍾做的....

   demo過程尚稱順利，該動的都會動，presentation也還ok，台下應該有聽懂我們是來hackathon不是來賣藥的。結束的時候還有人鼓掌跟吹口哨，工程師們果然都是好人！最後如預料的與前三名無緣，不過open-tok看到我們的努力，加上是唯一兩組用他們API的，把best open-toke prize給了我們...好吧也算是肯定了，誰叫另一組不爭氣呢？

   做個檢討的話，就是
1. hackathon是比好玩的，但是要贏就要偷跑。今天得獎的作品莫不是精美異常，有些參加人還是ceo拿自己公司的產品來介紹。
2. presentation大概佔七成吧，設計的好的簡報還是蠻有利的，雖然我認為今天報得都不怎麼樣。
3. UI, front end 真的很重要...最後關頭UI是投資報酬率最高的。好的首頁一秀出來，自己吹牛也吹得有自信起來。
4. 自己的T-shirt的size要記牢，女朋友的T-shirt size要記得更牢。

 行文至此，倍感勞累。古人有 云, no pain no gain!

 https://www.hackerleague.org/hackathons/api-hackday-sf-2013/hacks/live-bid
張貼者： 於 沒有留言:

2013年6月3日 星期一

[UVA] 198 Peter's Calculator

題目：http://uva.onlinejudge.org/external/1/198.html

code & tests:
https://github.com/wilson100hong/UVAOJ/tree/master/Volume_1/198

想法：一行一行parse，根據三種不同的指令做如下動作
1. Assign
    含有 ":=" (assign operator) 的line都執行Assign。:=的左邊是variable name，右邊會是一個Expression。由於Expression內含recursive的桔構，我這裡使用tree來存儲Expression內的每一個Term，而每一個Term也是一個tree，包含著子Factor。由於題目的input皆是合法輸入，對於tree的每個children可以recursive parse。
    這個命令執行完時，我們會產生/取代一組variable name -> Expression的key value pair，也就是變數的定義。把定義存在global的map裡。

2. Reset
   去空白後，以RESET開頭的line皆執行Reset。把 variable name -> Expression map 清掉即可。

3. Print
    去空白後，以PRINT開頭的line皆印出變數evaluation出的數值。由於我們必需考慮undefined variable 和cyclic dependency的情況，我們必需先
  a. 確認當前變數被定義過
  b. 從當前變數往源頭變數們(":=" 右邊的變數們)迴溯，它們也必需被defined過。不斷迴溯，直到所有involved的變數為
   b1. 所依賴的變數皆定義過    或
   b2. 不依賴其它變數 (eg. a:=3)
   c. 如果符合，那麼所有會被evaluate到的變數都有被定義過了。第二步是check cyclic dependency，這一步用DFS即可。有cycle就是UNDEF

  排除undefined之後，就是evaluate變數。我這裡是用topological sort把所有involved變數的依賴性排序後，依ts order做evaluate。每次evaluate完一個變數後就存進cache裡來reuse。這樣的好處是evaluate一個變數時它依賴的變數們都有值了，可以值接從cache取出來，免除重複計算。


GY：
  這一題考的就是coding而已。不過還是有GY之處，而且都非常賤：
1. 空白行是合法的，跳過即可
2. token之間是可以沒有空白的。簡單起見，一開始就把空白trim掉
3. RESET 跟 PRINT 的前面也可以有空白 <-- waste me 4 hours
張貼者： 於 沒有留言:

2013年5月6日 星期一

[UVA] 171 Car Trialling

這一題是很典型的語法分析題目。由於此題只需要判別句型是否合文法，最簡單的作法就是依照文法的優先序，不斷把token們組合成更高level的token。最後檢查是不是只剩一個類型為"instruction"的token即可。舉例來說：

//  組合結果     (粗體為token，細體為普通字符, ___ 為待組合tokens，// 文法)           
GO FIRST RIGHT AT "SMITH ST." AND CAS TO 20 KMH 
=> GO FIRST RIGHT AT sign AND CAS TO 20 KMH    
=> GO FIRST RIGHT AT sign AND CAS TO nnn KMH    // CAS -> cas
=> GO FIRST RIGHT AT sign AND cas TO nnn KMH    // cas TO nnn KMH -> change
=> GO FIRST RIGHT AT sign AND change            // AT sign -> where
=> GO FIRST RIGHT where AND change              // change -> time-keeping
=> GO FIRST RIGHT where AND time-keeping         
=> GO when RIGHT where AND time-keeping
=> GO when direction where AND time-keeping     // GO when -> how
=> how direction where AND time-keeping     // how direction where -> directional
=> directional AND time-keeping            
=> navigational AND time-keeping  // navigational AND time-keeping -> instruction
=> instruction


如此一來，題目就變成字串匹配及取代的問題。每次從文法庫中，選一個最優先的文法。從字串中尋找一組符合文法的tokens( -> 的左邊)組，找到的話該刪除該tokens 組，並插入新的token (->的右邊)。文法的優先性從下到上，即從 nnn 跟signwords做到instruction。有recursive定義的文法可以拆成兩組取代:


navigational = directional tex2html_wrap_inline61 navigational AND THEN directional
可以變為：
direction -> navigational
navigation AND THEN navigational -> navigational


有分崎的文法 :
instruction = navigational tex2html_wrap_inline61 time-keeping tex2html_wrap_inline61 navigational AND time-keeping
要先做
navigational AND time-keeping -> instruction
再做
time-keep -> instruction
跟
navigational -> instruction


可以自己想想看。


這一題讓我吃了史無前例的七個WA。最主要的原因又是不小心看題目：
"There will be one or more spaces between items except before a period (.), after the opening speech marks or before the closing speech marks."
要ok, 也就是說要特別check 
1. ""裡面不能是空的
2. 左"後不能直接空白
3. 右"後不能是空白
4. period " . " 前不能是空白


非常靠盃。






如果你還是WA，那麼這個從UVA forum偷來的test case 可能可以幫到你。t2.out是sample output.




May the AC be with you.




































張貼者：



於





沒有留言:
  


































          

        

          

        

2013年4月23日 星期二


          

        









[UVA] 150 Double Time










這一題不難，只是麻煩。總之把新曆跟舊曆元年一月一日各是星期幾找出來，然後每次都從元年元旦當基準點推即可。我基本上是參考這裡。 



debug的話，就直接把萬年曆印出來吧，新曆可以跟這裡比。舊曆的話，這裡有dropbox 的link:

https://www.dropbox.com/s/dti6vrcdxy18h19/old.out












張貼者：



於





沒有留言:
  


































          

        

          

        

2013年4月20日 星期六


          

        









[UVA] 179 Code Breaking










思路：這個目題有兩部份，一部份是求k，即encode的period。另一部份是求encode的permutation。

我求k的作法比較暴力，即從 k = 1開始，試到 k = n (n為cypher字串長，而非plain text長度)。如果中間遇到可以用的permutation，就可以結束迴圈作decode了。其中又可以發現，k必為 n 的因數 (n % k == 0)，所以可以跳過不可能的k值。



求permutation就比較講究。最直接的作法是做 k 窮舉，即 1234, 1243, .... 4321然後一一驗證。不過經由上次facebook hackercup 的教訓後，我發現這種匹配的問題，只要能將plain text與cypher的關係建構成二分圖，都可以用Bipartie match來解。只要能找到完全匹配，即為合格的permutation。建構二分圖的步驟如下：

1. 把plain text (P) 與 cypher (C) 每 k 個字元切一個chunk。cypher一定會沒有餘數，而plain text呢？只要在後面補?即可。如:  k = 3, plain text = abcd  --->  abc, d??。補問號可以讓P 與 C 的長度相同，把matching的邏輯簡化，也不失一般性，算是實作的一個trick。



2. 對 P 與 C 的第一個chunk，每個相同的 P[i] 與 C[j] 建一條邊，代表它們有潛力被匹配。於是我們得到左右兩邊各為 k 個 vertex的二分圖，而其上的邊代表相同字位交換位置的可能性。如果P或C有vertex沒被邊連到，那代表無法完全匹配，即此 k 不可行。



3. 對 P 和 C 之後的chunk，一次處理一個chunk。讓offset 代表 目前這個chunk離字串首的位移，對每個不同的P[offset + i] 與 C[offset + j]，如果之前有邊的話 (因為前幾個chunk該位置都可以match) , 便把邊移掉，不然無視。這一步是確保在每個chunk 中，P_chunk的第i 個字元 都可以匹配到 C_chunk的第j 字元。注意，我們的二分圖一直都是 兩個各有k點。





void BuildGraph(string text, string cypher, int k, vector< set<int> >&graph) {

   graph.clear();

   // Add edges

   for (int i = 0; i < k; ++i) {

      set<int> edges;

      for (int j = 0; j < k; ++j) {

         if (text[i] == cypher[j])

            edges.insert(j);

      }

      graph.push_back(edges);

   }



   // Remove invalid edges

   int len = text.length();

   for (int start = k; start < len; start += k) {

      for (int i = start; i < start + k; ++i) {

         int gi = i - start;

         for (int j = start; j < start + k; ++j) {

            int gj = j - start;

            if (text[i] != cypher[j]) {

               if (graph[gi].find(gj) != graph[gi].end()) {

                  graph[gi].erase(gj);

               }

            }

         }

      }

   }

}







最後把二分圖丟到Bipartie matching。完全匹配即為合格的k。permutation即為匹配。



有用的測資：



Input:

------

aaaaabbbbbcccccdddddeeeeefffff
aaaabacbbbcbddccdceeededfffeff
1234567890



aaaabbccuvwxuvwx

aaaaccbbxwuvxwuv

ABCD

#



OUTPUT:

-------

4632150?987?

CDBA










張貼者：



於





沒有留言:
  


































        

      









訂閱：
文章 (Atom)