[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

[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下來的範例:

5 
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了。

[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

[UVA] 139 Telephone Tangles

智障題。毫無演算法，考的是細心跟龜毛

 1. For 2nd part of input (the real telephone log), avoid using getline(). Use cin >> instead

 2. The presentation format seems does not matter

 3. Remove illegal IDD and STD code by checking their country code / area code length

 4. Validate the telephone number even when the code match, by their subscriber's length

TESTS:

088925 Broadwood0000000baaaaaaad$81
03  Arrowtown $38
01 $24
0061 Australia$140
00852 Hong Kong.012345678901234$1111
00 Los Angelos$10
000000
031526        22
0889256287213   122
008520123456789   64
779760    1
002832769       5
001234 1  
0123456 3
0123 4
00134 5
00123456789012 9
0061234 600
0061853279  300
00611234567890 700
006112345678901 800
123456789 2
123456789012345 4
#

OUTPUT

031526   Arrowtown  1526 22 0.38 8.36
0889256287213  Broadwood0000000baaaaaaad 6287213 122 0.81 98.82
008520123456789  Hong Kong.012345678901234 0123456789 64 11.11 711.04
779760 Local 779760 1 0.00 0.00
002832769 Unknown  5  -1.00
001234 Unknown  1  -1.00
0123456   23456 3 0.24 0.72
0123 Unknown  4  -1.00
00134 Unknown  5  -1.00
00123456789012 Unknown  9  -1.00
0061234 Unknown  600  -1.00
0061853279  Australia 853279 300 1.40 420.00
00611234567890  Australia 1234567890 700 1.40 980.00
006112345678901 Unknown  800  -1.00
123456789 Local 123456789 2 0.00 0.00
123456789012345 Local 123456789012345 4 0.00 0.00

[UVA] 143 Orchard Trees

給一個三角形，求出在其內的格點(整數座標)個數。
這一題我是用scan line。從y = 1 掃到 y = 99. 每次scan時，計算scan line和三角形的三個邊的交會點。如果有的話，把交點依x排序，對min 取ceiling (left), max 取 floor (right):
於是  right - left  + 1 即為該條scan line 上貢獻的格點數。累加即可。

這一題的陷阱有：
1. floating precision. 把 double 換成long double

2.  c++ 的ceil 和 floor不夠準。要用
    left = ceil( min - EPS)
    right = floor(max + EPS)
   
    其中正 負的的order自己想想

3. 只計算  1 <= x <= 99, 1<= y <= 99的格點，所以其實left跟right和要做處理：
    left = max(1, left)
    right = min(99, right)
    而且只考慮 right >= left的情況

Test case
input

5.0 31.9 3.5 63.4 66.5 46.6
1 1 1 1 1.1 1.1
99.00001 99.00001 99.99999 99.99999 99.99999 99.99999
1.5 1.5  1.5 6.8  6.8 1.5
10.7 6.9  8.5 1.5  14.5 1.5
71.67 88.3 45.02 49.09 98.49 0.1
5 3 7 1 3 1
3 3 3 3 3 3
1 1 50 1 100 1.01
1 1 100 1.01 1 1.01
0 1 4 1 2 3
0 0 4 0 2 2
0 0 0 0 0 0

output (blogger的indent沒做好，請自行調整)

743
    1
   0
  15
  17
1701
   9
   0
  50
   1
   8
   4

[UVA] 134 Loglan

這一題考你對parser的觀念如何。關鍵在於grammar要經過轉換成正規格式，以及grammar的ordering。利用重新整理後的grammer rules一一比對pattern，取代symbol即可。這個網頁有非常好的解答。

這一題我卡了好久，一是對正則文法的轉換理解不足，一方面是對程式架構沒有清析的思路。也是看了解答 (還不只一次)才理解該如何下手 ^ _ ^ bb

test case:


le bcade ga fgiho.
le bcade ge fgiho le bcade.
le bcade gi fgiho li bcade.
le bcade go fgiho lo bcade.
le bcade gu fgiho lu bcade.
foobar ge juklo li manpi.
lo qrase ba tviwu a xiyzu.
lo qrase ba tviwu a xiyzu e futye i
futno o blara u jukko.
da ztoya.
de ztoya i grota u thomo.
di ztoya.
do ztoya a brute.
du ztoya.
la mutce
bunbo mrenu ba ditca a ghoto.
futon be ditca.
gruton bi ditca.
le blara bunbo mrenu bo ditca.
jhqdhjqdwhjqwdhjqdjhwefdjhqwedhjwefzz bu ditca.
djb ba bbaba.
djan ga vedma le negro ketpi.
bad starts now.
la fumna bi le mrenu.
dja blarg.
djb ba.
.
le bcad ga fgiho.
le bcade gn fgiho le bcade.
le bcade gi fgiho ly bcade.
le bcade go fgiho lo bcadf.
bcade gu fgiho lu bcade.
lo qrase ba tviwu x xiyzu.
lo qrase ba tviwu a xiyzu e futye i
futno o blara u jukk.
la ztoya.
ge ztoya i grota u thomo.
bi ztoya.
do ztoya a bruten.
du zaoya.
futon e ditca.
gruton li ditca.
le blar bunbo mrenu bo ditca.
djan da vedma le negro ketpi.
#

Ans

Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!

[UVA] 187 Transaction Process

智障題。證明了我是智障的一題...還是寫下來做個警惕
幾個要點:
1. 每個exception 後印換行
2. Our of balance 是summation 乘 -1
3. 空白padding數目注意...

幹 太蠢了...