It will be finised in few hours. If you don't understand something, ask your questions, please.

233A - Perfect Permutation

Idea: Gerald Implementation: tunyash Editorial: fdoer

Consider permutation p such that p_i = i. Actually p is a sequence of numbers from 1 to n. Obviously p_pi = i. Now the only trick is to change the permutation to satisfy the second equation: p_i ≠ i. Let's swap every two consequtive elements. More formally, for each k: 2k ≤ n let's swap p_2k - 1 and p_2k. It's easy to see that the obtained permutation satisfies both equations for every n with the only exception: when n is odd, there is no answer and we should print  - 1.

233B - Non-square Equation

Idea: tunyash Implementation: tunyash, Gerald Editorial: fdoer

Firstly let's find the interval of possible values of s(x). Hence x² ≤ n and n ≤ 10¹⁸, x ≤ 10⁹. In other words, for every considerable solution x the decimal length of x does not extend 10 digits. So s_max ≤ s(9999999999) = 10·9 = 90.

Let's bruteforce the value of s(x) (0 ≤ s(x) ≤ 90). Now we have an ordinary square equation. The deal is to solve it and to check that the current bruteforced value of s(x) is equal to sum of digits of the solution. If the solution exists and the equality holds, we should relax the answer.

It seems that the most error-generating part of this problem is solving the equation.

Knowing arrays is not neccessary to solve these two problems.

232A - Cycles

Idea: tunyash, fdoer Implementation: tunyash Editorial: tunyash

Let's add edge in order of increasing a and for equal b in order of increasing b (here a and b — the least and the greatest vertices of the edge). If the new edge adds too much 3-cycles, we won't add it. We can count the number of new 3-cycles in O(n) complexity (they all contain the new edge, so it's enough to check all variants of the third vertex). Obviously we will obtain some proper graph, because we can always add a vertex and two edges to make a new triangle. So, there is always an answer. The complexity of this solution is O(n³).

Let's proof that 100 vertices are always enough for the given restrictions on n.

• For some p after first p iterations we will have a complete graph of p vertices.
• Now we have exactly C(p, 3) triangles. Consider p such that C(p, 3) ≤ k and C(p, 3) is maximal.
• For the given restrictions p ≤ 85.
• From this moment, if we add u from some vertex, we increase the total number of 3-cycles on C(u, 2).
• So we have to present a small number that is less than C(85, 3) as sum of C(i, 2).
• The first number we subtruct will differ C(85, 1) on some value not greater than C(85, 1) = 85, because C(n, k) - C(n - 1, k) = C(n - 1, k - 1).
• The second number we subtruct will differ the number we have on some value not greater than C(14, 1) = 14.
• and so on.
• For every k it's enough to use not more that 90 vertices.

232B - Table

Idea: tunyash, Skird Implementation: tunyash Editorial: tunyash

• Let s_i number of points in the column i.

• Two neighboring squares are drawn at this picture, A is the number of point it the left area (it is one column), B is the number of points in the middle area and C is the number of points in the right area (it is one column too). That's why by definition we have:

• Therefore A = C.
• That's why
• Divide all columns by equivalence classes on the basis of . For all a and b from one class s_a = s_b.
• cnt_a is number of columns in class with .
• There are (C_n^k)^cnt_a ways to draw k points in the each of columns in the class a independendently of the other classes.
• dp[i][j] is number of ways to fill all columns in classes 1, ... i in such way that .
• cnt_i take only two values and . Let's calc (C_n^a)^cnt_i for all a and cnt_i and use it to calc our dp. We have O(n²·k) complexity.

232C - Doe Graphs

Idea: Gerald,tunyash Implementation: tunyash, Gerald Editorial: tunyash

Let's reduce the problem to the same problem for graphs with less orders. Vertex |D(n - 1)| + 1 is cutpoint (except cases n ≤ 2 but equations below is true for these cases).

Without loss of generality a < b.

Let dist(a, b, n) — length of the shortest path in graph of order n.

The first case is a ≤ |D(n - 1)| and |D(n - 1)| + 1 ≤ b

Edges is marked in red, paths is marked in blue. This formula means that we can go from the vertex a by the path 1 to the vertex 1. Then we can go to the |D(n - 1)| + 1 by the edge and go to the vertex b by the path 3. Or we can go to the vertex |D(n - 1)| by the path 2 and then go to the vertex |D(n - 1)| + 1 by the path 2 and then go to the vertex b by the path 3.

The second case is |D(n - 1)| + 1 ≤ a, b.

That's easy case.

The third case is a, b ≤ |D(n - 1)|

If shortest path contains cutpoint (|D(n - 1)| + 1) we can go to the vertex 1 or |D(n - 1)+1$ form the both of a and b. After that we can go to the cutpoint. Else we should consider path from a to b in D(n - 1).

Let's notice that for all of n will be no more than 4 distinct runnings of dist(i, j, n).

It can be prooved by the considering many cases of our actions.

In authors colution we cashed all dist(1, i, n) and dist(i, |D(n)|, n) for all achieveable i and n.

We have complexity for one query. (it's log because |D(n)| grows like φⁿ).

232D - Fence

Idea: Gerald, tunyash Implementation: fdoer Editorial: fdoer

Let d and d' be arrays such that d_i = h_i - h_i + 1, d'_i =  - d_i for every 1 ≤ i ≤ (n - 1). With that notation the conditions of matching look somehow like these:

• the pieces do not intersect, that is, there isn't a single plank, such that it occurs in both pieces of the fence;
• the pieces are of the same width;
• for all i i (0 ≤ i ≤ r₁ - l₁ - 1) the following condition holds: d_l1 + i = d'_l2 + i (that is true in case when l = r).

The main idea of our solution is stated in the next sentence. For each query l...r the answer is number of pairs (a, b) such that (a > r or b < l), 1 ≤ a ≤ b ≤ n - 1, b - a = r - l and d_{l...r - 1} exactly matches d'_{a...b - 1}. Let's build a suffix array sa from the concatenation of arrays d and d' with a fictive number between them for separation. Let position of suffix i in sa be pos_i. For each query all pieces of the fence that satisfy both second and third conditions of matching will be placed in sa on some segment bound_left...bound_right such that bound_left ≤ pos_l ≤ bound_right and lcp(bound_left...bound_right) ≥ (r - l). So, it's possible to use binary search to find bound's. Depending on complexity of lcp finding algorithm, we could get them in O(logn) or O(log²n) complexity.

But there is still a problem to count the number of suffixes from sa_{boundleft...boundright} that satisfy the first condition too. Actually it is equal to count the number of i (bound_left ≤ i ≤ bound_right) such that (n + 1 ≤ sa_i ≤ n + l - (r - l) - 1 or sa_i ≥ n + r) (in the concatenation d' starts from n + 1). It is a classic problem to count numbers from the given interval in the given subarray. For each query it could be solved in O(logn) complexity.

For instance, we could solve it offline using sweep line method and any data structure that support queries of sum on an interval and increment of an element. Or we could use some 2D/persistent structure.

So, the summary of the algorithm looks like this:

• build d and d'. Build a suffix array on their concatenation.

For each query:

• find the interval (bound_left...bound_right) with two consecutive binary searches using lcp function.
• query the count of suffixes from that interval that do not intersect with the given piece of the fence.

The best author's solution complexity is O(nlogn + qlogn), but careful written solutions in O(nlog²n) comply with the lime limit too.

232E - Quick Tortoise

Idea: tunyash Implementation: tunyash, KAN Editorial: tunyash

Let's choose central column of the area and for all cells to the left from column calc masks of achieveable cells in the central column and for all cells to the right from column calc masks of cells of which this is achievable. It's easy dp with bitsets. for the right part of board. ( — logical or, here it's bitwise or for masks) for the left part. dp calcs mask of achieveable points in the central column.

For query x₁, y₁, x₂, y₂ (if y₁ ≤ mid ≤ y₂, where mid is chosen central column) answer is yes if ( is bitwise and) is not empty.

Run this algo for left and right part of board we will get answers for all queries. Complexity is .