Here is the editorial for round #148. I just tried to explain the ideas rather than detailed implementation explanation. I'm sorry for my bad English, so please tell me if something is not clear in the descriptions.
Two Bags of Potatoes
The author of this problem is Gerald. The total number of potatoes is a multiple of k and constraint there will be at most 105 multiples of k in range 1 to n. So you can iterate on multiples of k and print the ones that satisfy the problem.
Easy Tape Programming
In this problem you just need to simulate every thing which is written in the statement step by step. You can see a simple implementation of this here: http://www.codeforces.com/contest/239/submission/2512422
Not Wool Sequences
Let a1, ..., an be a not-wool-sequence. We define another sequence called b in which bi is xor of the first i elements of a, and b0 = 0.
Now xor of elements of a consecutive subsequence like ai, ..., aj will be equal to . So we know that all elements of b should be different. Therefore b is a sequence of distinct integers of length n + 1 starting with 0 made of numbers 0 to 2m - 1. The number of such sequences is and this is the answer to problem.
World Eater Brothers
Consider we only want to change direction of minimum number of roads so that all other countries are reachable from a specific country x. This problem can be solved in O(n) and it's exactly what 219D - Choosing Capital for Treeland asks for. If you don't know how to solve it you can read the editorial of that contest.
Consider two countries A and B which can be chosen by world eater brothers to achieve the minimum number of road direction changes. After changing the direction of roads, there exists a country on the undirected path between A and B which is reachable from both A and B using roads. We call such country a middle-country.
We want to iterate on middle-countries and find the best two countries for ruling for each middle-country. For each neighbor of the current middle-country calculate the minimum number of road changes in the subtree rooted at that neighbor so that all countries will be reachable from some country in that subtree. Then from two of these subtrees we need to pick A and B and all other subtrees will have edges pointing to the root of subtree. This can be computed in O(n) for each middle-city. So the overall complexity will be O(n2).
This problem was my favorite in the problemset. The primary point is that at any moment during the interpretation of a program only a prefix of the program is modified and used by IP.
Consider we want to calculate the output of subsequence sl, ..., sr. While running the original program s1, ..., sn if at any moment CP enters the interval [l, r] it should be pointing to position l and the direction of DP should be right. So it's like we have started interpreting sl, ..., sr independently. The termination of execution of sl, ..., sr is the first time CP points to somewhere outside interval [l, r].
Therefore what we need to solve the problem is to run the original program. And after each termination if the program is nonempty then run it again until program is empty. Then we should keep a log of positions we have visited and the time of each visit and the number of printed digits of each type until then. After this preprocessing the to calculate the answer of query (li, ri) its enough to find the first time CP visited sli and the first time CP visited sri + 1 or sli - 1 after that.
The described approach can be implemented in O(nlog(n) + qlog(n)).
Consider a bus passing a shortest path from si to ti. There are some points that are necessary to pass in order to obtain a shortest path. Firstly we compute them. This can be done in O(n3) with Floyd-Warshall and some processing after that. Urpal is sure that a bus from i-th company always passes such vertices on his path from si to ti. So he can get on a bus from i-th company only at vertices the bus surely passes.
At any moment Urpal's status can be uniquely determined by his position on the map and the bus he's traveling with. So we have nk states (position, bus).
Our goal is to reach some (b, ...) state from a (a, v) state which bus v surely passes a (source states). So let's find all states that can reach a goal state. We call such states good states.
Consider Urpal is at junction x and he's traveling with a bus of type y. Let v1, v2, ..., vw be the list of junctions the bus might go on its shortest path from sy to ty. And let c1, c2, ..., cl be the list of companies that their bus surely passes junction x, excluding y-th company. For state (x, y) we know we can reach junction b (it's a good state) if one of the following is true:
- x = b, the minimum cost of solving the problem will be 0.
- All states (v1, y), (v2, y), ... and (vw, y) are good states, the minimum cost of solving the problem will be the maximum of all these states.
- At least one of states (x, c1), (x, c2), ... or (x, cl) is a good state, the minimum cost of solving the problem will be the minimum the good ones plus one.
At first the only good states we know are states with junction b, (b, ...). Now some new states might have become good states. So we add those states to the list of known good states. We do this until no state becomes good anymore.
At the end we print the minimum cost of source states which are good, and if they don't exist we print -1.
The process thing can be implemented in O(n4). :)