Travel: the only problem I do not have a solution.
UPDATE: Apparently it is Bellman-Ford (I don't know why I keep calling this one Boyer-Moore, which is for string matching), the dynamic programming shortest path algorithm. The only tricky point is that you need to pay toll, so let node[i] be the gold you have at i, then the update step from i to j is
node[j] = max(node[j], (node[i]-edge[i][j]+s[j]) /2)
The problem statement is not very clear on this. Here node[i] is the max gold you can have at node i. Also note that you cannot have unbounded gold at any node as max among all node[i], let it be node[k], will not improve once passed its own s[k] so the updating process cannot continue indefinitely.
Arrangement: the problem is about finding hamitonian path and with N=1000 there is no hope to solve it exactly. And that is why the problem says it is an approximate problem. I didn't have time to implement some backtrack solution but it would be interesting to try some heuristics. Given 3 more hours, I could have done better.
Anyway I am happy with my score and interesting enough, why this particular company cares so much about graph algorithms.
Update: I finished a naive dfs backtrack solution to the last problem, Arrangement, which asks for a Hamitonian path given a graph. Surprisingly, it got Accepted.
The score board and my rank
| Rank | Hacker | Country | Score | Submissions | Solved |
|---|---|---|---|---|---|
| 31 | lantimilan | USA | 300.00 | 4 | 3 |
| Name | Points | Status | Statistics  |
|||
|---|---|---|---|---|---|---|
| Super Bomb | 100 | 
|
40/580 | |||
| Matching | 100 |
|
43/630 | |||
| Centre of Mass | 100 |
|
47/297 | |||
| Travel | 100 | 
|
29/63 | |||
| Arrangement | 100 |
|
14/271 |
No comments:
Post a Comment