228A - Is your horseshoe on the other hoof?

In this problem you should count different numbers from input cnt and print 4–cnt. You could do it in different ways. For example, you could use set.

228B - Two Tables

In this problem you should carefully consider every shift  - N <  = x, y <  = N, count the answer and find the maximum value. The complexity of solution is O(N⁴).

228C - Fractal Detector

This problem could be solved using dynamic programming. State z[x][y][st][mask] means if the square with upper left corner (x, y) is fractal with nesting level st and colors mask. The value z[x][y][st][mask] is 0 or 1. There are O(N²·Log(N)·2⁴) states in this dynamic programming.

The transitions from state to state are rather simple. If st = 1 you should fairly check that the square 2*2 with upper left corner (x, y) matches colors of mask. If st > 1 you should divide the square into four parts and check them separately. If the value in mask in one quarter means black color, you should check that the whole quarter is black. It could be done using partial sums on rectangles using O(1) of time. If the quarter is white, you should check that it is a fractal with nesting level st - 1 with the same mask. So, there are less than 4 transitions from every state.

To get the answer to the problem you should consider every upper left corner of squares, every mask and every nesting level of fractal and check this square. It is done using your dynamic.

228D - Zigzag

In this problem we will use that sequence s is cyclic because of its structure. Also, it is important that 2 <  = z <  = 6. For every z we will write the sequence s and note that its period is 2 * (z–1).

So, for every z and modulo 0 <  = mod < 2 * (z–1) we will build separate segment tree or Fenwick tree. You should be careful with memory, it needs O(Z·(2·Z)·N) of memory. So, if the query is to update some value, we should update z values of trees with correct modules. If the query is to find sum, we should consider every 2·(z–1) modules, count the sum and multiply by correct coefficient from sequence s. The complexity is O(Z·N·Log(N)).

228E - The Road to Berland is Paved With Good Intentions

This problem can be solved in different ways. It was expected the solution that solved the system of modular equations using Gauss algorithm. Here is another simple solution.

The vertices from the result call switched-on. Firstly, note that every vertex should be switched-on no more than once. Then, consider every edge (x, y) of color c. We want to make its color 1. So, if c = 1 we should switch on vertices x and y or don’t switch them on simultaneously. If c = 0 we should switch on x or y. So, consider some vertex v and try to switch it on or not. Thus, we can uniquely determine the state of every vertex of the same connected component as v. If we face some collision, we can’t get the solution, you should print Impossible. The solution can be realized using bfs with complexity O(N + M).