Solution of Codeforces Round #148

Link: http://codeforces.com/blog/entry/5765

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 10⁵ multiples of k in range 1 to n. So you can iterate on multiples of kand 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 a₁, ..., a_n be a not-wool-sequence. We define another sequence called b in which b_i is xor of the first i elements of a,  and b₀ = 0.

Now xor of elements of a consecutive subsequence like a_i, ..., a_j 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 + 1starting with 0 made of numbers 0 to 2^m - 1. The number of such sequences is  and this is the answer to problem.

Boring Partition

Coming soon...

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(n²).

Tape Programming

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 s_l, ..., s_r. While running the original programs₁, ..., s_n 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 s_l, ..., s_r independently. The termination of execution of s_l, ..., s_r 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 (l_i, r_i) its enough to find the first time CP visited s_li and the first time CP visited s_ri + 1 or s_li - 1 after that.

The described approach can be implemented in O(nlog(n) + qlog(n)).

Meeting her

Consider a bus passing a shortest path from s_i to t_i. 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(n³) 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 s_i to t_i. 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 v₁, v₂, ..., v_w be the list of junctions the bus might go on its shortest path from s_y to t_y. And let c₁, c₂, ..., c_l 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 (v₁, y), (v₂, y), ... and (v_w, 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, c₁), (x, c₂), ... or (x, c_l) 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(n⁴). :)