First, arrange the problems in order of their difficulties. The authors assume such order: A, D, B, C, E. Now make the tutorial of problems in their order in the contest.
This problem was technical. First, you should erase all occurrences or word WUB in the beginning and in the end of the string. And then parse the remaining string separating tokens by word WUB. Empty tokens should be also erased. Given string was rather small, you can realize the algorithm in any way.
In this problem you could write breadth-first search. The state is the following four elements: number of remaining piles and three strings — three rightmost cards on the top of three rightmost piles. We have two transitions in general case. We can take the rightmost pile and shift it left by 1 or 3 on another pile. If the number of remaining piles become 0 at some moment print YES, else print NO. The number of states is O(N4), the number of transitions 2, so the complexity of solution is O(N4).
In this problem we will find the sought quantity for every vertex and find the maximum value. For this for every vertex v count two values: cnt1[v] and cnt2[v] — number of shortest paths from vertex v to n-th and 1-st vertices respectively. For this you should construct graph of shortest paths and use dynamic programming on the constructed graph (because the new graph will be acyclic). To construct the graph of shortest paths you should leave only useful edges in original graph. It can be done, for example, using breadth-first search launched from vertices 1 and n respectively.
After values cnt1[v] and cnt2[v] are found consider every useful edge (u, v) and add to vertices u and v value (cnt2[u] * cnt1[v]) / (cnt2[n–1]), which is the contribution of this edge in the sought quantity for the vertices u and v. Note that value (cnt2[n–1]) is the number of shortest paths between 1 and n. All said values can be found in time O(N + M). The complexity of solution is O(N + M).
208D - Prizes, Prizes, more Prizes
In this problem every time you get points you should greedily get as much prizes as you can. For this, consider every prize from the most expensive and try to get as much as you can. If we have cnt points and the prize costs p points you can get prizes. So we get simple solution with complexity O(5 * N).
In this problem you have some set of rooted down- oriented trees. First, launch depth-first search from every root of every tree and renumber the vertices. Denote size of subtree of vertex v as cnt[v]. In this way all descendants of vertex v (including v) wiil have numbers [v;v + cnt[v]–1].
Then we wiil handle requests (v, p) in their order. First, go up from vertex v on p steps to the root using binary rise like in LCA algorithm. Denote this vertex u. If u doesn’t exist print 0 else you should count the number of descendants of vertex u on the same height as vertex v.
For this write all numbers of vertices for every height in some array. Then you should determine which of these vertices are descendants of u. You can do it using binary search in corresponding array. Find the segment of appropriate vertices (because we know the numbers of all descendants of u), find the amount of them, subtract one (vertex v), and this is the answer. The complexity of the solution is O(Nlog(N)).