Hi Codeforces!

We would like to invite you to participate in Codeforces Round #266 Div2, which will be held this Friday, September 12th at 19:30 MSK. As usual, Div1 participants can take part out of the competition.

Problems have been prepared by Antoniuk and me. It's the second round prepared by us, and we still hope it won't be the last.

We want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It will be used a standart scoring: 500-1000-1500-2000-2500.

Gl & hf!

UPD. Round has finished. Thanks for participating.
UPD2 Congratulations to top-5 participants:

1) dominator_hza
2) Final_Battle
3) free_pascal
4) vanhanh.pham
5) NUOUN

UPD3. Editorial .

431A - Black Square

To solve this problem, you must only do the process described in statement.

for i = 1 .. s.size()
 if (s[i] = '1') ans += a[1];
 else ...

Complexity: O(N)
Solution: 6676675

431B - Shower Line

In this problem, according to the small limits, we can brute all permutations and choose the best answer of all. The easeast way to do this — use standart C++ function next_permutation, or simply write 5 for. For each permutation we can simulate the process, which was described in a statement, or notice that first with second student, and second with the third will communicate one time, and third with fourth student, and fourth with fifth — will communicate two times. Another pairs of students will never communicate to each other during they stay in queue.

Complexity: O(n!)
Solution: 6676695

431C - k-Tree

This problem can be solved by dinamic programming.
Let's Dp[n][is] — number of ways with length equals to n in k-tree, where if is = 1 — there is exists edge with length at least d, is = 0 — lengths of all edges less then d.
Initial state Dp[0][0] = 1.
Transition — iterate all edges which can be first on the way in k-tree, then problem transform to the same, but with less length of the way (because subtree of vertex son is the k-tree).

Dp[n][0] = Dp[n-1][0] + ... + Dp[n-min(d-1,n)][0] Dp[n][1] = Dp[n-1][1] + ... + Dp[n-min(d-1,n)][1] + (Dp[n-d][0] + Dp[n-d][1]) + ... + (Dp[n-min(n,k)][0] + Dp[n-min(n,k)][1])

See solution for more details.

Complexity: O(nk)
Notice that this solution can be easy midify to O(N) complexity, only precalc partial sums. But it is not neccesary to solve this problem in such way.
Solution: 6676700

431D - Random Task

We will search n by binary search. Such function is monotone, because the amount of numbers with exactly k 1-bits on a segment n + 2 ... 2·(n + 1) more or equal than amount of such numbers on segment n + 1 ... 2·n. Last statement is correct, because of n + 1 and 2·(n + 1) have equals number of 1-bits.
To find the amount of numbers on segment L...R, which have exactly k 1-bits, it is sufficient to can calculate this number for segment 1...L, then the answer will be F(1...R) - F(1..L - 1).
Let's understand how we can calculate F(1...X). Iterate number of bit will be the first(from biggest to smallest) which is different in X and numbers, which amount we want to calculate. Let the first difference will be in i-th bit(it's possible, if in X this bit equals to 1, because we consider all numbers do not exceed X). Then other smallest bits we can choose in any way, but only amount of 1-bits must equals to k. We can do this in C_i^k - cnt ways, where cnt — the number of 1-bits in X, bigger then i, and C_n^k — binomailany factor. Finally, you should not forget about X (if it, of course, has k one bits).

long long F( X )
   Ans = 0 , cnt = 0;
   for i = Max_Bit...0
      if (bit(X,i) == 1) Ans += C[i][K - cnt] , cnt ++;
   if (Bit_Counts(X) == K) Ans ++;   
   return Ans;

Асимптотика: O(log²(Ans))
Решение: 6676713

431E - Chemistry Experiment

First of all let's understand the statement.
We have n tubes. At the beginning of each of them there are a few amount of mercury is poured. We want be able to perform two types of queries:

1. Make the amount of mercury in p- th tube equals to x.
   
2. Given the number v — the amount of water that must be optimally pour these tubes. What does it mean optimally? That mean we pour water in some of the tubes in the way, when maximum volume of liquid for all tubes, where we poured water, will be as small, as possible.
   

Well, actually now turn to the solution.
Use binary search to find an answer, in particular, will sort out the amount of mercury in a tubes(let it equals to d), such that in the tubes with smaller volume of the liquid can be poured all v liters of water and the maximum liquid level does not exceed d. Let the number of tubes, with the amount of mercury less than d is equal t.

Now the problem is reduced to learning how to count the total amount of water that we can to pour into each of t least tubes, such that the level of the liquid in each of them is equal d.

Let a[i] — the total amount of mercury in the tubes which exactly have i liters mercury and b[i] — number of tubes which the volume of mercury is equal i. Then t = b[0] + ... + b[d - 1] and v₁ = t * d - (a[0] + a[1] + ... + a[d - 1]) — the total maximum amount of the water which can be poured. If v₁ < v, then obviously this space is not enough for pour all the water, otherwise quite enough and so the answer will be no more than d.
When we found the smallest d, we can say that the answer is equal d — (v₁ — v) / t.

To quickly find for a[0] + a[1] + ... + a[d - 1] and b[0] + ... + b[d - 1], and perform queries of the first type, you can use the Fenwick tree.
Асимптотика: O(qlog²(n))
Решение: 6676668