Please write here if you had written some comments about any suggestions or questions on the announcement. There are a bunch of notification emails but I couldn't read most of them :(

Here are the final top 100 : Div1, Div2. Congrats to the winners!

(These links are all from google search cache, so it may be disappear)

First of all, we are sorry to make this round unrated. This is an unexpected incident, and I believe that everyone in Codeforces would understand that. And second, we're sorry for estimating the difficulties of the problems wrong.

• Actually, I thought that somebody would get Accepted on 398A - Карточки within 5 minutes. But there wasn't any submissions during the first 4 minutes, and many people got wrong answer on pretests! I think almost everybody who solved this got at least one wrong answer.. I'm really sorry for measuring A easy. I think what cgy4ever said is right — it would be better not asking to print the sequence.

• At first, I purposed 398C - Дерево и массив as B(!!) because ainta solved it very easily than I expected. (I could hardly solve this, and thought it must be at least D, before I heard ainta's solution.) We're sorry for giving this problem the same score with 398B - Красим стену, which was much easier than 398C - Дерево и массив. Next time I'll remember that ainta is really a genius :)

• Congrats to four people who solved 398C - Дерево и массив during the contest! : cgy4ever, Shef, SillyHook06, and Qwaz.

• We are surprised that Petr solved 398E - Сортируем перестановки during the contest! Even though he implemented by Java, his solution is faster than ours :p Congratulations to him!

• Actually, we purposed an another problem for Div1-E, but the same problem popped out at OpenCup last Sunday, so we couldn't use that. Thanks to Gerald, who helped us preparing a new problem in such a short time. By the way, can you guess what problem was that? :D

• ...

399A - Страницы — Author : .o.

You can solve this problem by just following the statement. First, print << if p - k > 1. Next, iterate all the integers from p - k to p + k, and print if the integer is in [1..n]. Finally, print >> if p + k < n.

• Time complexity: O(n).
• Code : 5926588

399B - Красные и синие шарики — Author : xtalclr

Change the blue balls to bit 1, and blue balls to bit 0. Interpret the stack as an integer represented in binary digits. Now, one may see that a single operation decreases the integer by 1, and will be unavailable iff the integer becomes zero. So the answer will be 2^a₁ + 2^a₂ + ... + 2^a_k where the (a_i + 1)-th (1 ≤ i ≤ k) ball is blue in the beginning.

• Time complexity: O(n)
• Code : 5926598

398A - Карточки — Author : .o.

Let the number of o blocks p, and the number of x blocks q. It is obvious that |p - q| ≤ 1 and p, q ≤ n. So we can just iterate all p and q, and solve these two problems independently, and merge the answer.

1. Maximize the value of x₁² + x₂² + ... + x_p² where x₁ + x₂ + ... + x_p = a and x_i ≥ 1.

• Assign a - p + 1 to x₁, and assign 1 to x₂, x₃, ..., x_p.
• The value is (a - p + 1)² + (p - 1).

2. Minimize the value of y₁² + y₂² + ... + y_q² where y₁ + y₂ + ... + y_q = b and y_i ≥ 1.

• For all , assign to y_i.
• For all , assign to y_j.
• The value is .

The proof is easy, so I won't do it. With this, we can solve the problem. We can print y₁ xs, and then x₁ os, ...

• Time complexity: O(n).
• Code : 5926607
• Bonus: Is there any solution faster than O(n)? We tried to use ternary search, but we couldn't prove that was correct.

398B - Красим стену — Author : ainta

This can be solved by dynamic programming. Let T[i, j] the expected time when i rows and j columns doesn't have any painted cells inside.

Let's see all the cases. If we carefully rearrange the order of rows and columns, we can divide the wall into 4 pieces.

1. Choose a cell in rectangle 1. The size of this rectangle is i × j. The expectation value is T[i - 1, j - 1].
2. Choose a cell in rectangle 2. The size of this rectangle is i × (n - j). The expectation value is T[i - 1, j].
3. Choose a cell in rectangle 3. The size of this rectangle is (n - i) × j. The expectation value is T[i, j - 1].
4. Choose a cell in rectangle 4. The size of this rectangle is (n - i) × (n - j). The expectation value is T[i, j].

Merging these four cases, we can get:

T[i, j] = 1 + {T[i - 1, j - 1] × i × j + T[i - 1, j] × i × (n - j) + T[i, j - 1] × (n - i) × j + T[i, j] × (n - i) × (n - j)} / n²

Moving the T[i, j] on the right to the left, we can get the formula which can be used to calculate the value T[i, j]. There are some corner cases, like i = 0 or j = 0, but it can be simply handled.

• Time complexity: O(n²)
• Code : 5926617

398C - Дерево и массив — Author : .o.

There are two intended solutions. One is easy, and the other is quite tricky.

Easy Solution

Make a tree by the following method.

• For all , make an edge between vertex i and with weight 1.
• For all , make an edge between vertex i and i + 1 with weight .

You can see that are all good pairs. In addition, (1, 3) is also a good pair. So we can print the answer.

But, if n = 5, this method doesn't work because (1, 3) is not a good pair. In this case, one may solve by hand or using random algorithm.

• Time complexity: O(n)
• Code: 5926624
• Bonus I: Is there any method to make more than good pairs?
• Bonus II: Is there any method that the maximum weight is relatively small and make at least good pairs?

Tricky Solution

If you got stuck with the problem, one can run any random algorithm that solves small cases, and merge these cases. With this approach, we can even limit the weight to a very small constant!

But I think this is not a good solution, so I won't mention about unless anybody wants to know the details. I came up with this solution, and tried to purpose this as D. It seems all the 6 people who passed pretests during the contest didn't use this solution :)

• Time complexity: ???
• Code : 5926632

398D - Мгновенные сообщения — Author : .o.

Let x_i an integer representing the state of the i-th user. If user i is online, x_i  =  1, otherwise, x_i  =  0. Also, let S_i the set consisting of i-th friends.

One can see that the queries become like this:

• Online/Offline: change the value of x_i to 1  -  x_i.
• Add: add u to set S_v, and v to set S_u.
• Delete: delete u from set S_v, v from set S_u.
• Count: calculate .

Let's use sqrt-decomposition to perform these queries. Let user u heavy if |S_u| ≥ C, or light otherwise. Also, we will define some arrays and sets:

• H_u is a set that stores friends with user u who are heavy users.
• O[u] stores the sum of .

If the Online/Offline(u) query is given,

• If u is a light user: for all , change the value of O[v]. It takes O(|S_u|) time.
• Otherwise: just update the state of itself.

If the Add(u, v) query is given,

• If vertex u becomes heavy if we add this edge, for all , add v into H_w and update the value of O[w]. This can be done in O(C).
• If vertex u is still light even if we add the edge, update O[v]. This can be done in constant time.
• If vertex u is heavy (after the operations above), update H_v.
• Add u to set S_v, and v to set S_u.

If the Delete(u, v) query is given,

• Delete u from set S_v, and v from set S_u.
• Update the value of O[*], H_u and H_v. Because for all |H_w| ≤  E| /  C, this can be done in O(|E| / C).

If the counting query is given, will be the answer. Because |H_u| ≤ |E| / C, it will take O(|E| / C) time.

So for each query, O(|E| / C) or O(C) time is required. To minimize the time, .

• Time complexity:
• Code : 5926635

We can also solve this by dividing the queries into parts. For each block, use O(n + m + q) time to build the online & offline state and the answer table for each vertices. For each query, you can use time to get the answer. If you want more details, please ask in the comments.

• Time complexity:
• Code : 5926640

398E - Сортируем перестановки — Author : xtalclr, eyTns, and great help of Gerald

The author is writing the solution, and it will come soon.

Feel free to ask of or discuss about the solutions! Unfortunately, I don't know how to read or write Russian, so if you ask me in Russian, I can't response to it. (also, I think the Russian editorial won't be available..) Sorry for that.