Find vertex with the lowest degree $$$v$$$. It should be in the first frame. Choose its neighbour $$$u$$$ and try to check wether there is a solution where $$$u$$$ is a copy of $$$v$$$ in the second frame. Degree of $$$v$$$ is $$$O(\sqrt{m})$$$, so it works fast.

Now if we know that $$$v$$$ and $$$u$$$ are the same vertex in the first and second frames, we know that all other neighbours of $$$v$$$ are in the first frame. For each such neighbour $$$w$$$ we know that $$$w$$$ and $$$u$$$ should have exactly 2 common neighbours: $$$v$$$ and copy of $$$w$$$ in the second frame. So we can find all copies of neighbours of $$$v$$$ in the second frame. Using the same ideas and bfs we can find all the vertices in all the frames.

E: You can prove, that one of the optimal paths between two cells either contains a cell which directly shares a side with one of the black holes, or you can just travel along the border of the rectangle bounding the two cells from the query.

So all you need to do is to precompute the distances from all(168 = 4 * 42) free cells next to the black holes to all other cells, and then to answer the query you need to find the minimum length of the path going through one of those cells from the one query cell to the other one.

I solved E with the technique used in this problem. (https://atcoder.jp/contests/apc001/tasks/apc001_i) (It amazed me that so many teams knew this problem, but it seems that there is a simpler solution.)

Segment tree + hashes was enough, I needed no sqrt.

We did segment tree + hashes: to check that two substrings are equal you need to check that:

• Their first character is the same.
• The sequence of value differences between adjacent characters starting from the second one is the same.

First part can be maintained in a segment tree by doing segment updates & point queries. Second part is doable by segment tree over the array of differences: since each update changes differences for only 2 positions, you can do point updates & segment queries.

I don't know what your "sqrt" means, but a usual segment tree is enough. Just add 1 on a segment and also track the maximum value with its position. While the maximum value is $$$65\,536$$$, decrease it by $$$65\,536$$$, and repeat. There will be no more than $$$\lceil \frac{q}{65\,536} \rceil \cdot n$$$ such decreases. To compare the substrings, we maintain hashes.

My code has only 140 lines.

We used just Fenwick tree + hashing for getting range sum and update value of one element (one Fenwick tree for current prefix hashing and one for getting current value of element after increase queries).

Really nice tasks!

For a large prime $$$p = k \cdot 2^{16} + 1$$$ (or several such primes) we can find $$$\omega$$$ of multiplicative order $$$2^{16}$$$, and $$$x$$$ of any large order. Substring hashes $$$h(s_0 \ldots s_{n - 1}) = \sum_{i = 0}^{n - 1} x^i \omega^{s_i}$$$ can be maintained with an RSQ structure with range multiplication updates (add $$$1$$$ to $$$a_i$$$ = multiply hashes by $$$\omega$$$).

Let's assume that there are $$$n$$$ black piles, no white piles, the size of the smallest black pile is $$$x$$$ and there are $$$k$$$ black piles with size $$$x$$$. Then if $$$k = n$$$, the Sprague-Grundy function of this game is $$$x$$$ if $$$k$$$ is odd and $$$x - 1$$$ otherwise. If $$$k < n$$$, it's the other way around: $$$x - 1$$$ if $$$k$$$ is odd and $$$x$$$ if $$$k$$$ is even. You can easily prove this by induction. Now the white piles are just usual nim, so you should xor their sizes with Sprague-Grundy function for black piles and check if it's zero.

Let's fix the smallest black pile $$$x$$$. Also fix the parity of black piles with size $$$x$$$. Now there are 2 cases: if we don't take black piles with size greater than $$$x$$$, then the value of the game is already fixed, and we just need to check wether it's zero. Otherwise, we need to choose among piles with size greater than $$$x$$$ a subset with a fixed xor so that the total xor is zero. So we reduced our problem to a standard one: maintain a set of binary vectors with 2 queries: add a new vector to the set and count number of subsets with fixed xor. This is solved with Gauss. We maintain the basis of vectors in the set and when we need to count number of subsets with xor $$$x$$$, if $$$x$$$ is in subspace generated by our set, the answer is $$$2^{size \, of \, set - size \, of \, basis}$$$, otherwise it's zero. Also don't forget to check the case when all piles are white.

The shared links are not accesible. Please fix it..

Was the name changing a reason of different problem titles in statement vs. right menu of Yandex.Contest?

In "E. So Many Possibilities...", how to find "dp(l, S)" in $$$O(2^n n m)$$$ ?

Not saying it's not broken on YandexContest but 8MiB doesn't sound right. You have 3 int arrays of length of a 1000000, it is 12Mb already