197A - Plate Game

If first player can't make first move (table is too small and plate doesn't fit it, i.e. 2r > min(a, b)), second player wins. Else first player wins. Winning strategy for first player: place first plate to the center of table. After that he symmetrically reflects moves of second player with respect to center of table. If second player has move, first player has symmetrical move, too. If not, first player won.

197B - Limit

From math lessons we know, that only higher degrees of polinomials matter in this problem.

1. If denominator degree is larger than numenator degree, answer is "0/1".
2. If numenator degree is larger, answer is infinity. But what is sign of this infinity? To get it consider signs of highest degree factors of polinomials. If they are same, answer is positive infinity, else — negative infinity.
3. If degrees of numenator and denominator are equal, answer is . To get irreducible fraction, you should divide this numbers by gcd(a₀, b₀). And don't forget that denominator of answer must be positive.

196A - Lexicographically Maximum Subsequence

Solution is greedy. First, write all 'z' letters (if there is any) — answer must contain them all for sure. Now it's time for 'y' letters. We can use only those of them which are on the right of last used 'z' letter. Then write 'x' letters — they must be on the right of the last used 'y' and 'z' letters. And so on.

196B - Infinite Maze

Answer is "Yes" iff there are two distinct, reachable from start position cells, which correspond to same cell in initial labyrinth.

Proof: If these cells exist, move to first of them, and infinitely repeat moves leading from first to second. On the contrary, if infinite far path exist, on this path we obviously can find such cells.

How to find out if they exist? Start DFS from initial cell. For each cell visited, let visit[x%n][y%m] = (x, y). Now, if DFS tries to go to cell (x, y), visit[x%n][y%m] contains something, and (x, y) ≠ visit[x%n][y%m], we found these cells: they are (x, y) and visit[x%n][y%m]. Notice that DFS will visit no more than nm + 1 cells (Dirichlet's principle). So the asymptotic is O(nm).

196C - Paint Tree

No three points are in the same line, so the solution always exists.

First, choose any one vertex as the root of tree. Find size of each subtree using dfs.

Then, we can build the answer recursively.

Put the root of tree to the most lower left point.

Sort all other points by angle relative to this lower left point.

Let us name the sizes of subtrees of the root as s₁, s₂, ..., s_k.

Run the algorithm recursively, giving first s₁ points (in sorted order) for the first subtree of root, next s₂ points for the second subtree and so on.

Obviously, no two edges from different subtrees can intersect now.

At each step of recursion we are to put the root of current subtree to the first point in sorted-by-angle order, and then sort other points by angle relative to it.

So, no two subtrees will have any intersecting edges.

The asymptotic of solution is .

196D - The Next Good String

Notice, that only palindromes with length d and d + 1 matter. Any palindrome with greater length contains one of them. Let's call these palindromes bad.

First, find leftmost position pos, in which we surely should increase value of symbol. If there are no bad subpalindromes, pos = |s| - 1, else pos is leftmost position amongst all ends of bad palindromes.

Increase s[pos]. Increase it more, while s[pos] is end of bad subpalindrome. If you try increase 'z' symbol, you should proceed to increasing previous symbol. If this way you reached situation when you need to increase first symbol, and it is 'z', answer is "Impossible".

Now, let pos be position of leftmost changed symbol. We know, that prefix s[0..pos] doesn't contain bad palindromes. Now we can greedily fill suffix s[pos + 1..length(s) - 1]: go over positions i in ascending order, assign s[i] = 'a', and increase it, while s[i] is end of bad palindrome. Obviously, any of suffix symbols will be 'a', 'b' or 'c'.

So we got algorithm, which requires fast implementation of next operations — assigning single symbol, and query: is given substring palindrome? You can perform this operations using hashes and Fenwick tree.

Let's learn, how to get hash of substring in dynamically changing string. If we can it, we will keep string s and it's reversed copy. For query of second type we just need to compare hashes of substring in s and hash of corresponding substring in reversed copy.

Let Fenwick tree store values h[i] = s[i]Pⁱ, where P is the prime number used for hashing. Then hash of substring s[L..R] equals to (h[L] + h[L + 1] + ...h[R])P^- L. For assigning s[i] = c, add value (c - s[i])Pⁱ to h[i]. Both these operations Fenwick tree does in .

Also we have faster solution without hashes and data structures, it will be published soon.

196E - Opening Portals

First of all, we can note that if each graph vertex is portal, the answer will be a sum of all edges' weights in MST (minimal spanning tree). We can find MST by using Kruskal's algo.

In this problem, not an every vertex is portal. Let's fix this.

Start with a precalculation. Run Dijkstra's algo from all the portals, simultaneously. We will get d[i] — a distance between vertex i and p[i] — the nearest portal to vertex i.

Let's trace Kruskal's algo on a graph of portals. On the first iteration, it will choose the edge with the minimal cost, i.e. a shortest path between all the portals in the original graph.

Let the path leads from portal x to portal y. Note that there exists a path with the same length such as p[i] changes only once through it. Indeed, p[x] = x, p[y] = y, i.e. p[i] changed on the path. If it happens on edge , p[i] = x, a path will not be longer than the path from x to y.

As p[i] = x and p[i] = y, we can see that the length of this path will be d[i] + w(i, j) + d[j], where w(i, j) is the weight of edge (i, j). Kruskal's algo will add this value to the answer and merge portals x and y. The shortest-path trees of vertexes x and y will also be merged.

Note, that almost nothing changed. The next edge for Kruskal's algo can be find in a similar way — . If this edge connects x and y again, DSU makes us not to count this edge, otherwise this edge connects a different pair of edges and will be counted in an answer.

We can easily implement this. Just create a new graph of portals, with an edge (p[i], p[j]) of weight d[i] + w(i, j) + d[j] for every edge (i, j) of weight w(i, j) from original graph and run Kruskal's algo.

Finally, note that if the starting vertex is not a portal, we shall add d[1] to the answer.