[Hacker Cup 2013] Qualification Round

1. Beautiful String
    簡單來說就是對一個string，依照字母的出現頻率給予 26 ~ 1的權重 (從低到高)。把出現次數乘上權重再加總算總分。

2. Balanced Smileys
    要想一下的字串parse題。從s[0]開始一個一個字串作。字元a~z和空白不重要，直接skip。由於左括( 與右括 ) 要匹配，所以要持續紀錄目前還單身的左括號。冒號的話要看緊接在後的是否有) 或 (，有的話要branch成兩重情況，一種是笑/哭臉，另一種是單純的冒號。我很懶就用recursive實作了。

3. Finding the min
    被我莽夫地解了。
    前k (m_0 ~ m_k-1) 個就模擬了，反正頂多10萬個，注意一下10^9 * 10^9要用long long 去接(C/C++)，不然會暴。算完前k個就完成一半了。
    另一半就是算之後的k+1個數(m_k ~ m_2k)。由於要不斷的挑前k個數沒出現過的最小非負整數，用個好的data structure還是有用的，比如說BST。我又懶了所以這裡就bucket count了，非常暴力。聰明的人觀察到 m_k~ m_2k 剛好是 0 ~ k+1的permutation, 所以m_2k+1 之後會從m_k開始重復。所以m_k = m_2k+1 = m_3k+2 = m_4k+3 。總之就是有k+1的週期，如此週而復始屎而復粥。最後小心的把n mapping一下即可。

official website

my code on github

[UVA] 122 Trees on the level

這一題可以直接建 tree, 然後用BFS traverse。不過建tree 的過程需要不斷產生parents，要非常小心。
這一題也可以用sorting來做，因為每個node 的位置編碼後的LLRR.. 可以拿來compare，排序後印出即可。先考慮depth，一樣深的node比較位置編碼( 就像一般的數字比較 但是L < R)。排序完後要驗證是否有重複的position，以即是否每個node的parent都有存在( 比如說，一個LLR的node會要有parent 為LL)。收工。

[UVA] 104 Arbitrage

最短路徑的經典題目。arbitrage是fast trading最基本的套利方式，遙記得當初念書時，層幫一個firm 做利用CUDA 加速找arbitrage的實驗，那時候N好像是500以上...扯遠了。總之，這一題經過拆包裝後，就是在graph中，找出最少邊的negative cycle。

一開始使用Bellman Ford，想利用其detect negative cycle的性質。雖然BF是single source，但是因為graph是 completely connected，所以只需要做一個source即可確定圖中有無負環。BF的確是可以輕鬆判斷有無arbitrage的存在，可是在找出最少邊的負環路徑上很不給力。每個Vertex只記得最短路徑下其前一個vertex，我們可以找到"最賺錢的arbitrage"，但是對"最少邊"無能為力。

上網找了一下，發現這題用Floyd-Warshall更直覺容易懂，連結在這裡。只要稍稍改變relaxing的判斷式，FW可以拿來求任意pair在給定最大hub下，可行的最短路徑。在此題中，即為求最少hub下，是否有cycle是負數即可。


Relaxing 如下：

dist[N][N][N]  // 第三個index是hop 數
prev[N][N][N]

if (dist[i][j][hop] < dist[i][k][hop - 1] + edge[k][j]) {
   dist[i][j][hop] = dist[i][k][hop - 1] + edge[k][j];
   prev[i][j][hop] = k;  
}

[UVA] 106 Fermat vs. Pythagoras

一開始以為要暴力解再優化，沒想到是數學題.
X^2 + Y^2 = Z^2,

where X, Y and Z are relative-prime integers, then

X = R^2 - S^2
Y = 2RS
Z = R^2 + S^2

where R, S are also relative-prime integers, and ONLY one of them is EVEN.

然後我也發現 loop 1,000,000次是非常快的事，這個數值可以記一下。

[UVA] 116 Unidirectional TSP

這是一道DP題。從第0 column 往右update minimum cost即可解。然而有以下幾個 陷阱讓我多吃了三個WA:
第一個是如果有cost相同時，要印出字典順序較小的path。所以中間的每一格都要記住從起點到自己目前的"路徑"，即所有路過的格子。當不同paths有相同的cost時，會需要這些paths來比較字典順序。
第二個陷阱是起點可以為任何一格… 題目要看清楚。
百思不得AC的人可以試試這個test case (from UVA forum):

Input
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3

2 2
9 10 
9 10

5 4 
9 1 9 9 
1 9 9 9 
9 9 9 9 
1 1 1 1 
9 9 1 9

5 6 
-3 -4 -1 -2 -8 -6 
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5 
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4 

4 7 
1 2 -3 4 -2 1 5 
-1 3 5 -2 6 -3 4 
2 1 3 -2 -1 3 1 
3 -3 4 2 -3 4 3 

5 6 
1 1 1 1 1 1 
2 2 2 2 2 2 
3 3 3 3 3 3 
4 4 4 4 4 4 
5 5 5 5 5 5 

3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 

5 5 
1 5 10 6 3 
5 1 8 4 11 
10 12 5 2 9 
7 3 20 5 8 
4 1 5 12 6 

5 10 
11 53 34 73 18 53 99 52 31 54 
4 72 24 6 46 17 63 82 89 25 
67 22 10 97 99 64 33 45 81 76 
24 71 46 62 18 11 54 40 17 51 
99 8 57 76 7 51 90 92 51 21 

5 10 
11 53 1 73 18 53 99 52 31 54 
4 72 54 6 46 17 63 82 89 25 
67 22 80 97 99 64 33 45 81 76 
24 71 46 62 18 11 54 40 17 51 
99 8 57 76 7 51 90 92 51 21 

5 6 
-3 -4 -1 -2 -8 -6 
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5 
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4 

10 100 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

6 8 
9 1 9 9 1 1 1 1 
1 9 9 1 9 9 9 9 
9 9 1 9 9 1 1 1 
1 1 9 9 1 9 9 9 
9 9 9 1 9 9 9 9 
9 9 1 9 9 9 9 9

Output
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
2 1 5 4
4
4 3 2 3 3 4
-49
1 4 1 2 1 2 3
-11
1 1 1 1 1 1
6
1 1 1 1
10
1 2 3 2 1
14
2 3 3 2 1 2 3 4 4 5
188
1 5 1 2 1 2 3 4 4 5
172
4 3 2 3 3 4
-49
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100
2 1 6 5 4 3 3 3
8

[Shell] tips

set
In shell scripts set -e is often used to make them more robust by stopping the script when some of the commands executed from the script exits with non-zero exit code.

if then else

if [ -d $directory ]; then
 echo "Directory exists"
else 
 echo "Directory does not exists"
fi 

Please note the spacing inside the [ and ] brackets! Without the spaces, it won't work!

${PWD##*/}
get leaf directory of pwd. Eg.
 > echo $PWD
/home/wilsonhong
> echo {$PWD##*/}
wilsonhong

-d
if [ -d "$DIRECTORY" ] 
check directory exist or not 

gnome-terminal -e "<cmd>"
run command interminal


find . -iname "*.pyc" -exec rm -f {} \;
delete all .pyc files 

For each result, command {} is executed. All occurences of {} are replaced by the filename. ; is prefixed with a slash to prevent the shell from interpreting it.

[UVA] 147 Dollars

算是DP的經典題目，無奈粗心的我在這題依然賠上兩個WA。Coins組合方法個數，等同Non-repetitive Knapsack題目的變形，並且可以重複利用1D array。可我居然一開始想成Repetitive Knapsack, 真蠢。

特別要注意的是，不要使用double來讀幣值一類的input，一定會有floating error, 就算不發生在你這邊，也一定會發生在online judge上。能用int 讀就用int，不行就硬幹string parsing

另外一點就是DP很容易beyond 32 bit int，DP的array type 事前要仔細思考會不會超出int 的範圍。

[UVA] 107 The Cat in the Hat

簡單來說，就是給定A, B二整數，A = m ^ n, B = (m+1) ^ n，求m 與n (皆整數)。
答案即為m與n的某種組合。
一開始是卡在題目看不懂，後來又卡在沒考慮m = 1的情況，哀...
有用的測資:
-- Input --
1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1048576 59049
483736625 481890304
125 64
64 1
81 64
0 0

-- Output --

0 1
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
29524 4017157
615441 1931252289
21 369
6 127
9 217