I'd like to invite everybody to participate in HourRank 12 on HackerRank. It'll start tomorrow at 19:30 PM MSK.

It's my first HourRank but I've prepared problems for HackerRank several times. I also used to prepare problems for Codeforces long time ago.

There will be three problems and one hour to solve them. Contest will be rated and top-10 contestants on the leaderboard will receive amazing HackerRank T-shirts!

I'd like to thank wanbo for testing the problems, it's always a pleasure to work with him. I hope you will enjoy the problems and some of you will solve everything.

Scoring will be: 20-40-80. Editorials will be published right after the contest.

Good luck!

That's a part of final editorial. I'm sorry for delay. Please, report me about mistakes and unclear moments in solutions and in my english.

A div2

Task was to find the least digit, that is not contained in the given number and compare with given k.

B div2

Good sequence may contain only zeroes or contain some positive number. In the second case such a sequence is not longer than sequence {0, 1, 1, 2, 3, 5, 8, ..., x, y} where y > 10⁹ and x ≤ 10⁹. That's possible to find it using dummy algorithm. In the first case you may use binary search of two pointers.

A div1

Let's notice that sum in the rectangle (x1, y1, x2, y2) is sum(x1, x2)·sum(y1, y2). Where sum(l, r) = s_l + s_l + 1 + ... + s_r. Then, we have to calc sum(l, r) for every pair (l, r) and count how many segments give us sum x for any possible x (0 ≤ x ≤ 9·|s|). In the end we should enumerate sum on segemnt [x1, x2] and find . There is corner case a = 0.

B div1

We may assume that John may exchange any subset of his items x to any other subset y, such as s(x) + d ≥ s(y) (it does not matter if x intersects y). We can find all possible sums in subset of elements of the given set of items using standard dp (knapsack problem). John should always exchange all his current set of items to another, because if he had exchanged some subset of x (current set) z to y, we can say that he had exchanged x to . So, we have to find shortest sequence of sets a, such as s(a_i + 1) - d ≥ s(a_i) for any possible i and a₀ = {}. This subtask could be solved using following greedy algorithm. a_i, i > 0 is maximal correct sum such as a_i ≤ a_i - 1 + d. Consider optimal answer c and our answer a. Let k is the first position where a_k ≠ c_k obiviously a_k > c_k (because a_k selected as maximal as possible). Then consider q such as q_i = c_i for i ≠ k and q_k = a_k. q is either optimal. Applying similar operations we will obtain a. So, a is optimal.

C div1

We expected many unproved, but tested solutions. I think that careful prove of my solution with pen and paper is very difficult. So I will use some statistic-based facts.

1. Consider the set of divisors of number k. One can check that it's beautiful set.
2. If factorisation of k has the form where α_i ≥ 3 and p_i is distinct primes, set of divisors of k which is less than is also beautiful.
3. How to prove item 2? Consider set A of pairs of divisors of k (a_i, b_i) such as a_i·b_i = k and a_i < b_i. Obiviously (if k is not complete square) any divisor will be contained only in one pair. It's easy too see that . Consider some element of factorisation of k p^α such as and it is not true that . Let f(x) is maximal number s such as . f(a_i) + f(b_i) = α. For every q such as numbers q, q·p, ..., q·p^α will be divisors of k. That implies that where d is number of divisors of . So in pairs both numbers are divisible by p. So set {a₀, ..., a|A|} is beautiful.
4. But there are some pairs with f(a_i) = α. is equivalent approval.
5. It's always possible to find such k as number of it's divisors is bigger than 2·w where w is number of elements in required set. You may write following dp to find it.
6. dp[i][j] is minimal k which is constructed of first i primes ans has j divisors.
7. About 10 primes is enough to cover all k.
8. Now we can construct beautiful sets with more than k elements.
9. Using item 4 we will understand that constructed answer is very beautiful (about 60% of elements divisible by every possible p) and we can always delete extra elements.

Last items is not strict, but one can check it with his computer.

D div1

1. Consider random element a_r of a. With probabillity where g is ghd of a.
2. Let x_i = gcd(a_i, a_r). There are no more than d distinct x_i where d is number of divisors of a_r.
3. We can find number of a_i such as for every k in O(d²). (D is set of divisors of a_r)
4. Repeat item 1 x times we will get correct solution with probabillity 1 - 2^- x.

There is the way to solve this problem O(n·plog + d·2^plog) for iteration where plog is the maximal number of distinct primes in factorisation of a_r.

E div1

1. Let's find number of rectangles whick consist k ones and intersect in cartesian coordinate system.
2. It's possible to do it in n²·k. We need to find closest k ones on the top and on the bottom of the and enumareate all segments [l, r] such as 1 ≤ l ≤ r ≤ n and find closest k ones on the top and on the bottom of the segments merging results for rows.
3. If we have k closest ones on the top and on the bottom of the segment we will find number of rectangles consists k ones and cross on [l, r] in O(k).
4. Then we should find number of rectangles, which don't cross . Let's rotate table by 90 degrees, solve similar problem for two halfs of the table and so on.
5. for square-shaped tables.

At the picture 1 two closest ones on the top (black cells) lying on the 4'th and 2'nd horizontals. Closest ones on the bottom lying on the 5'th and 7'th. Then if k = 2 there are zero correct rectangles with two "ones" on the tom. There are four rectangles which consist one "one" on the top and one "one" on the bottom. You can see how segment grows up at the pictures 2, 3 and 4. Every time you should merge closest k ones of the added row with closest k ones of the current segment.

Hi all! This round is prepared by me, caustique, el_sanchez, KAN, malcolm. I thank Gerald, who has organised our work and helped us with tricky situations, MikeMirzayanov for the system of organasing contest Delinur for the translation.

I hope that all problems will be OK and everyone will find intersesting problem for him/her.

Winners:

div1:

1. lovelymoon
2. niyaznigmatul
3. cerealguy
4. ainu7
5. cgy4ever

div2:

1. dotato
2. netman
3. kybconnor_4

I apologise for the mistakes in statements. I will be more careful in the next time.

Hi all! This round was prepared by me and KAN. I hope, you will enjoy our problems.

I want to thank PavelKunyavskiy, who tested our problems, readed statements and so on. Moreover, alger95, Skird, fdoer, sand-martin tested round too, I thank them for it.

And of course, I thank Gerald for organising our work, MikeMirzayanov for the great system and Delinur for translation of the statements.

I hope, result will be better than results of our previous round. Good luck!

Pay attention, round will be held at unusual time.

Scoring:

div1: 500-1500-1500-2000-2500

div2 : 500-1500-1500-2500-2500

My congrutulations for leaders.

div1:

1. al13n
2. tomek
3. niyaznigmatul
4. voover
5. Egor
6. Zlobober
7. White_Bear
8. seanwu
9. wjmsbmr
10. peter50216

div2:

1. fotiIe96
2. zfmdhy786
3. wzc1995
4. gjh
5. mynameisverylong

Full english editorial: here

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 .

Hi all!

Codeforces round #144 is going to be today.

Round is prepared by: KAN, fdoer, Skird, tunyash. Special thanks to Gerald for coordinating round preparing, many awesome ideas and making statements easy-understandable. Also I thank MikeMirzayanov for enjoyable problem-preparing system, Delinur for statements translation.

I hope, that all will be well and you will enjoy solving problems.

Good luck!

UPD: Score distribution will be announced a few minutes before the start of the contest.

UPD2: score distribution is 500-1000-1500-2000-2500 in both divisions

UPD3:

Congrats to winners.

div1:

1. tourist
2. rng_58
3. Mimino
4. Dmitry_Egorov, Egor

div2:

1. debug22
2. ryz
3. dvdreddy
4. vinodreddy
5. rdivyanshu

UPD: editoral for all problems, except div1.D is ready

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¹³.

The upcoming contest is brought to you by me. My name is Arthur, I'm a student of Chelyabinsk lyceum 31.

I am glad to thank Gerald for contest preparation management, Delinur for translation of statements, MikeMirzayanov for a really excellent system, dolphinigle for test-solving, proof-reading and much valuable advice, fdoer, grey_wind, Skird and alger95 for help in problem development.

There is nothing more to say yet. As you can see, contest will be held in two divisions separately. The scoring system will be standard (not dynamic), but scores for tasks may be unusual (see update of this post).

There won't be volume stories. I hope you will like the contest and its problemset and everything will be OK.

UPD: Scores for tasks:

Division 1: 500-1000-2000-2000-2500

Division 2: 500-1000-1500-2000-3000

UPD2:

Congrats to winners =)

Div1:

1. Petr
2. tourist
3. yeputons
4. peter50216
5. aram90

Div2:

1. lucien
2. tomasz.kociumaka
3. sjynoi

UPD3 some part of English editoral posted. You will find the remaining part of the editorial later

UPD4 English editoral was completed.

http://www.ioi-jp.org/apio2012/ — asian pacific informatics olympiad. People, who participated in it, let's discuss problems, after the second open contest. You still have a chance to take a part in the second contest by the way.