Please, report me about every grammar mistake, you see. Thank you.

Problem <>

Let's notice that 2n ≤ k ≤ 5n. If k < 3n author has to get 2 on some exams. There are 3n - k such exams and that's the answer). If 3n ≤ k author will pass all exams (answer is 0).

Problem <>

Let the pencil move by the line and put crosses through every (n + 1) point. Lets associate every point on the line with point on square perimeter. Namely, point x on the line will be associated with point on square perimeter that we will reach if we move pencil around square to x clockwise. Then lower left corner will be associated with all points 4np for every non-negative integer p. Crosses will be associated with points k(n + 1) for some non-negative k. Nearest point of overlap of two families of points will be in point LCM(n + 1, 4n). Then we will put crosses.

Problem "Cutting Figure"

Translation by fdoer

Main idea: using the fact that the answer cannot be greater than 2, check answer 1.

Let's proof that the answer is not greater than 2. Let area of the figure be greater than 3. Let's examine the leftmost of all topmost squares. There is no neighbors left or up to it. So, number of its neighbors is not more than 2. Thus, if we delete its neighbors, we shall disconnect the figure. If the area is equal to 3, we always can disconnect the figure by deletion of one square. It can be proofed by considering all two primary cases. If the area is not greater than 2, there is no way to disconnect the figure.

The algorithm: Check answer 1. We can simply brute-force the square to delete, and for each instance start dfs from any existing square. If during the dfs we visited not all of the remaining squares, we have found the square to delete. The answer is 1 if our bruteforce succeeded, and 2 otherwise.

That was necessary to consider the case when there is no answer.

The complexity of the described algorithm is O(n⁴). That was possible to search for articulation points and solve the problem in complexity O(n²), but in my opinion that required more time and effort.

Problem <>

Translation by fdoer

Main idea: bruteforce in complexity O(F_un) where F_u if fibonacci number at position u.

This problem had complex statements. We have an array a, and we can transform it in two ways. The goal was to maximize the sum of all its elements with given multipliers after exactly u operations.

A simple bruteforce of all combinations of operations with subsequent modeling leads to complexity O(2^u * nu), what is not fast enough. That was possible to optimize it by modeling parallel to recursive bruteforce. Now we have complexity O(2^un). Actually, the correct solution is not too far from this algorithm.

There is just one conjecture: every two successive xor operations change nothing, and we can move them to any place of the combination. Thus, it will be enough to bruteforce only combinations in which every pair of successive xor operations is at the end.

It could be done using recoursive bruteforce. We must change in previous solution two things. First, we must n't put xor after xor. Besides that, we should update answer if number u - l is even, where l is current level of recoursion (all remaining operations in the end separates to pairs of xors).

Let's calculate complexity of this algo. There are F_i sequences of length i without two consecutive xors. It's easy to proof, you can calculate some dp to see it. That's why, complexity of our algo is O(F_un).

Problem "Hamming distance"

Main idea: reduction to system of linear equations and solving it using Gauss algorithm.

Let's notice that order of columns in answer doesn't matter. That's why there is only one important thing — quantity of every type of column. There is only 2⁴ = 16 different columns.

Let's represent Hamming distance between every pair of strings as sum of quantities of types of columns. It's possible because every column adds to every distance between pairs 0 or 1.

Now we have system of 6 linear equations with 16 variables. It's not good, let's decrease number of variables. First, some columns adds same values to every Hamming distance. For example strings "abbb" and "baaa". For every column q we can replace all letters "a" by letters "b" and all letters "b" by letters "a" and reach column that adds same values to every distance. We reduced number of variables to 8. We also can notice that columns "aaaa" and "bbbb" is useless and reduce number of variables to 7.

This system can be solved using Gauss algorithm. One variable steel be free. Let's fix it. It's value can't be more than maximum of h(s_i, s_j) because column adds positive value to one or more Hamming distance. For every fixed value we should check if all variables take non-negative integer value and choose the best answer.

We can solve system of equations in integers because coefficients of equation is little.

Complexity of this solution if O(max(h(s_i, s_j))). If we solve it in rational numbers complexity will change to .

Problem "Two segments"

Main idea: inverse the permutation and solve simplified problem (see below), consider function "quantity of segments of permutation that form the given segment of natural series".

In order to solve this problem, we suggest solve another: <<we have a permutation p_n, we have to calculate the count of segments such that their elements form one or two segments of natural series>>.

If we solve the inverse problem for some permutation q_n such that , we shall get the answer for the initial problem and initial permutation p_i.

Straight-forward algo: let's bruteforce the segment of permutation and mark its elements in a boolean array. Check that in that array there is not more than two marked segments. This algo has complexity O(n³).

Let's notice that during the changeover from [l, r] to [l, r + 1] the quantity of segments changes in some predictable way. Let s([a, b]) be quantity of segments that form segment [a, b] of permutation. There are three cases (see picture below):

• If the new element p_r + 1 is between two marked elements (that is, both elements with values p_r + 1 - 1 and p_r + 1 + 1 belong to segment [l, r]), then s([l, r + 1]) = s([l, r]) - 1. The new element will <> the segments near it.
• If the new element p_r + 1 has only one neighbor with value belonging to [l, r], then s([l, r + 1]) = s([l, r]). The new element will lengthen one of existing segments.
• If there are no marked elements near p_r + 1 the new element forms a new segment, s([l, r + 1]) = s([l, r]) + 1.

The new element is red, elements that are marked to this moment are black.

Improved algo: Let's bruteforce position of the left border and for each instance move the right border from left to right. During each move we shall recount the actual quantity of segments forming the current segment of permutation (s([l, r])). Now we have a solution in complexity O(n²). It works fast enough even when n = 20000. Obviously, that is not enough to get AC.

Move on full solution. It is based on previous. Now we can calc s([l, r]) using s([l, r - 1]). Now we should look at way of changing s([l - 1, r]) as compared with s([l, r]). Let's move left border of segment from the right to left and support some data structure with s([l, i]) for every i satisfying l < i ≤ n and current l. This structure should answer queries "count numbers 1 and 2 in structure", that is count segments [l, i] that generates one or two segments in the original permutaton.

Let Δ_i be s([l - 1, i]) - s([l, i]). Δ_l will be equal to 1 because one element form one segment in permutation (notice that in final answer we must not consider 1-element segments, that's why we must subtract n from answer in the end of solution).

Δ_i determined by the number of neighbors of element l - 1 in the segment [l - 1, i]. Neighbors of l - 1 is elements p_l - 1 + 1 and p_l - 1 - 1 if they're exist.

• If l - 1 hasn't neighbors in this segment, Δ_i = 1, because l - 1 froms new 1-element segment.
• If l - 1 has one neighbor in this segment Δ_i = 0, because l - 1 join to existing segment of its neighbor.
• If l - 1 has two neighbors in this segment Δ_i =  - 1, because l - 1 connect segments of its neighbors.

Number of neighbors in segment [l - 1, i] non-decreasing with increasing i. That's why Δ_i non-decreasing with increasing i. That means that there are only three segments of equivalence of Δ_i. We are interested only in neighbors of l - 1 which positions are right than l - 1. Let a is position of first neighbor, b is position of second neighbor, without loss of generality a < b. Then , , . (elements of permutation are numbered from 0). If a and b aren't exist, for all Δ_i = 1. If only b isn't exist for , for .

Look at example to clear your understanding. (Δ_i is in top right corners, l = 3, p_l = 5)

Using this facts we can code data structure support following operations:

• Add +1 or -1 on segment
• Calc number of 1 and 2 in the structure.

Sum of answers of structure in every iteration (for every l) is answer to problem.

Let's notice that all numbers in structure will be positive. That's why elements 1 and 2 will be minimal of pre-minimal in the structure. Using this fact we can code segment tree, supports these operations.

Complexity of this solution is .

We also can code sqrt-decomposition and obtain complexity .

Problem <>

Translation by fdoer

Main idea: baby-step-giant-step.

In this problem we had some Fibonacci number modulo 10¹³ f, and we had to determine the position of its first occurence in Fibonacci sequence modulo 10¹³.

• Let a and b be two different coprime modula — divisors of 10¹³.
• Let F be the actual Fibonacci number such that . Then and .
• Find all occurences of number in Fibonacci sequence modulo a period.
• Find all occurences of number in Fibonacci sequence modulo b period.
• Let's fix a pair of such occurences. Let the occurence modulo a be in position i, and the occurence modulo b be in position j.
• Let t(m) be Fibonacci sequence modulo m period.
• From the Chinese Remainder Theorem, it follows that t(ab) = LCM(t(a), t(b)) (remember that a and b are coprime).
• Then from fixed occurences of f in periods of sequences modulo a and b we can recover the position of occurence of f in period of sequence modulo ab. It could be done by solving the following Diophantine equation: i + t(a) * x = j + t(b) * y. We can solve it using a simple bruteforce of one of the roots.
• If the occurence in sequence modulo ab period ( we have just found it) is u, then every occurence f in Fibonacci sequence modulo 10¹³ period can be represented as t(ab) * k + u. Then let's bruteforce k and find all occurences in sequence modulo 10¹³ period. To determine Fibonacci number on position α + t(ab) from known Fibonacci number on position α, we need to multiply the vector (F_α, F_α + 1) and some matrix.
• Let's choose a = 5⁹ and b = 2¹³. Note that there is no number that occur Fibonacci sequence modulo a or b period more than 8 times. That means that total count of pairs will never be greater than 64. For each occurence we'll bruteforce not more than numbers. That was the author's solution.

Also that was possible to use the fact that for any number the count of its occurences in period of sequence modulo 10^p (for any natural p) is not big more efficiently. From occurences in sequence modulo 10ⁱ period we could get occurences in sequence modulo 10^i + 1 period using the method we use to jump from modulus ab to modulus 10¹³.