這一題不難，只是麻煩。總之把新曆跟舊曆元年一月一日各是星期幾找出來，然後每次都從元年元旦當基準點推即可。我基本上是參考這裡。
debug的話，就直接把萬年曆印出來吧，新曆可以跟這裡比。舊曆的話，這裡有dropbox 的link:
https://www.dropbox.com/s/dti6vrcdxy18h19/old.out
2013年4月23日 星期二
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
我求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
2013年4月18日 星期四
[UVA] 157 Route finding
思路： 利用Dijkstra求起點到終點的最短路徑。同一條線上相鄰的車站距離為1，不同線相交轉車的距離為3，接著求最短路徑。parse input時同時建立graph。
Dijkstra在C++的實作要點在於，relax distance需要一個支援update value (decrease key) 的 min heap。常見作法有二，一是用priority_queue，每次relax 時塞一個新的(node, relaxed_distance)進heap。由於relax後的同node一定有比較小的distance，所以一定會在heap的較上方。舊的distance就會被擠到下面，而在pop時被忽略。
另一個作法是用set 配合pair (node, distance)。每當要update node時，先把(node, old_distance)從set中移除 ，再新增一個pair (node, new_distance)。也就是用 delete/insert來達到 decrease key的目的。Top coder有非常完整的解說。
這一題有一個蠻有趣的陷阱，害我吃了一個WA。這是從forum上copy下來的範例:
A:ab=Bbcdefghijk
B:abc=Ajdef=Cb
C:ab
D:cd=Eg
E:fg=Bf
AaAk
AcAk
AbBb
BaDd
#
The correct output is:
9: Aab=Bbc=Ajk
8: Acdefghijk
3: Ab=Bb
8: Babcdef=Dd
WA output:
9: Aab=Bbc=Ajk
8: Acdefghijk
3: Ab=Bb
11: Babcdef=Eg=Dd
陷阱在於，可能有複數個stations同為一個connection set，但是input沒有窮舉set中的任兩兩。如上題中，connection should be:
Bf=Cb=Dd=Eg
但是題目只列出部份:
Bf=Cb Bf=Eg Eg=Dd
也就是 Cb=Dd (以及 Cb=Eg, Bf=Dd)是需要程式自己推導出的。這種集合的驗證蠻麻煩的，所以我用了一些trick: 當'x=y'出現，可以知道x車站與y車站相連。製造出一個虛擬車站 C1，
且有邊： cost(x, C1) = cost(y, C1) = 3, cost(C1, x) = cost(C1, y) = 0 這樣 x 到 y, y 到x 的cost都是3。
接著當 y=z出現時，由於 y 已經連到 C1了，所以可以直接讓z 也連到 C1。如果z 之前連到另一個虛擬車站C2，那我們可以把C1跟C2連起來: cost(C1, C2) = cost(C2, C1) = 0，於是z 到 x 也是 cost = 3了。
2013年4月13日 星期六
[UVA] 172 Calculator Language
思路：
算式中有三種token。分別為正負整數，變數 (A ~ Z) 和運算元 ( +, -, *, /, =, (, ) )。前二種哥以統括為運算子。在parse算式時，運算元放一個stack (S1)，運算子放另一個stack (S2)。為了保證括號的優先性，當遇到算式結尾或是右括號時，不斷pop這S1 與 S2 直到S1空了，或是S1頂部為左括號。值得注意的是，'='會改變變數的值，所以要維持一個變數的mapping。
題目本身不難，吃了三個wa的原因主要有二：
1. 所有變數default為0
2. 比較變數有無更動要在算式做完才比對
eg,
A = 2
B = (A = 3) - (A = 2)
ans:
A = 2
B = 1
訂閱：
文章 (Atom)