## 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*^{2}(*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:

- Make the amount of mercury in
*p*- th tube equals to*x*. - 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*_{1} = *t* * *d* - (*a*[0] + *a*[1] + ... + *a*[*d* - 1]) — the total maximum amount of the water which can be poured. If *v*_{1} < *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*_{1} — *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*^{2}(*n*))

**Решение**: 6676668

I clicked the solution link and got "You are not allowed to view the requested page" :P

fixed

KaiZeR just made Guinness world records for fastest editorial posting :P .

Thanks. It will have been made when I publish an editorial for E.

Is there any better solution for Problem B...?? If the input was big then how do we solve it.?? Any idea please.. :D

How can we prove that function is monotone in problem D?

I have written it in editorial. Please, re-read it more attentively.

Oh, got it, Truly nice observation. ty :)

Problem C can also be solved this way. We can calculate total number of n weighted paths using DP. Also calculate number of n weighted paths with no path having edge >= d. Subtract the second value from the first one.

Thank you man. Your solution is easy to understand. I saw your solution. I didn't understand the editorial, but I understood after reading your comment and your solution. Many many thanks...

Wow I liked your approach it worked, did it easily ;)

Can someone explain me why i'm getting WA with this solution : 6676798 using dp to count all the paths using edges with weight k or lower :

and then doing the same for k=d-1

and the answer will be dp[n]-dpp[n] % 1000000007

got it it was just about doing % in the right place :|

I lost a lot of time on problem C. And I didn't manage to finish it in time. Thanks God that you have posted the editorial so quickly. I can't stand to finish solving this problem :))).

For Problem C, i am getting a Time Out with this implementation

unsigned long long ans = 0; const int mod = 1e9 + 7;

void foo( int c, int n, int k, int d, bool take) { if (c == n && take) { ans++; if (ans >= mod) ans %= mod; return; } if (c >= n) { return; }

}

int main (int argc, const char * argv[]) { int n,k,d; ans = 0; cin>>n>>k>>d;

}

Can someone kindly tell me what is the Complexity of this code ?

Since you didnt use memo, your program can run up to o(k^n)

Is it possible to download the test cases somewhere? My solution fails on #28 on one query, and I think there's a bug in my data structure but I can't find it.

It is not possible to download the test cases from codeforces ... but i may suggest u to generate some random cases and run it on any accepted code on ur pc and spot the difference with your code's output on the same cases

I was using a slightly modified version of R-B trees that I've used before. I've done a lot of stress testing on random inputs and it worked correctly. The bug only appears in one test case on one particular query — all queries before and after that are solved correctly, which is very strange.

I guess I could try to submit fake solutions that would print out the first N numbers of the test case in question, then the next N etc, but that would take quite a while..

Ouch it turns out a function called count_less was actually counting elements that are less than or equal, which wasn't an issue in a different problem where elements were unique =\ Good times, failing two problems because of one symbol =(

Can someone explain the solution for Problem E? What sort of structure do I need here to efficiently handle the update and answer the queries at the same time?

segment trees?

Maybe.

What I don't get is, when a query occurs, they need the array h to be sorted to do a binary search for the desired answer.

But the array is changing with every update.

So how are they doing a b.search and dealing with a seg tree at the same time?

I've probably got the idea wrong. :-/

A binary search tree works well for such problems, as you can easily add count/sum to every node. They are a pain to implement, but if you can write them once it can help with future contests. Same goes for other common algorithms such as MCMF, suffix trees.

I haven't yet tried keeping a code library. Hopefully will start working on one soon. :) Although the suffix array code from a previous problem did come in handy in the last two rounds.

Actually, any data structure to find sum and update in a logarithmical time. Some of them, with pre-processing of input, like a "squeeze coordinates".

With the help of Xellos's comment, I think I get the idea now. Thanks.

I don't know about efficient, but you can read all the numbers, split them (in sorted order) into groups of numbers (ignoring duplicates) and remember the sum of numbers present in each group. Removing/adding a number takes time, since just 1 group is updated for either action. Answering query 2 means flooding the array and finding the height of water surface afterwards, so you need to find the

xsuch that when the smallestxelements are flooded, the water surface would reach above thex-th but not above thex+ 1-st element; that can also be done by adding whole groups of numbers to thexflooded numbers and when we can't add a group, then adding its elements. Time complexity: .Thanks a lot. :) That looks like a convincing algorithm for this problem.

The issue of using segment tree is how to avoid resort all the elements.

My idea is instead storing the value of each tube, you store pair<V,Q> which means there are Q(quantity) tubes that has the value V. Since there are up to 100000 tubes and up to 100000 ops, there will be at most 200000 different values, means at most 200000 pairs<V,Q> are needed.

At first, find out all possible values which takes up to O((n+q)log(n+q)) time(using binary search), then build all the pairs and sort them by V. Now you can build a segment tree on it.The tree will track both the sum total value(sum total value of a pair = V*Q) and sum Q.

For every update, you only need to change the Q without resorting the pairs. do binary searches on V to find the pairs where you need to Q+=1 and Q-=1 (of course to you need to track the value of each tube to find out the current value of the specified tube),then modify the segment tree. For every query it's easy to do since we are using segment tree.

:) I just coded your algorithm, and it's so hard for me to implement. It's my first time though. 6685388

i guess problem E is O((q+n)logn)...

I used a different idea for D. Ofcourse, the only reason it didn't pass in contest was because i set upper limit of binary search,

hi= 1e18 / 2 when in fact it should be justhi= 1e18. (Making this change passed it in practice).To make it easier to explain, let's call those numbers which have exactly

k1-bits in their binary representation asgoodnumbers.Let's consider the binary representation of

Nto bexxxx. Now, 2 *Nwill look like this:xxxx0.Observe that for every

goodnumber < = 2 *Nsuch that its 0-th bit is set to 0, there exists an identicalgoodnumber < =N(by just doing one right shift).Now, let's say

f(X) = Number ofgoodnumbers < =X.Since we are calculating

f(2 *N) -f(N), thosegoodnumbers < = 2 *Nwhich have 0-th bit set to 0, will not be counted as there exists an identical counterpart < =N.Therefore,

f(2 *N) -f(N) = number ofgoodnumbers < = 2 *Nwhose 0-th bit is set to 1 =g(N) (say)g(X) is now monotonic and now binary search can be applied to find the number which hasmgoodnumbers less than it.I just realized

f(2 *N) -f(N) is monotonic.bangs head on the keyboardMy solution is like your solution: 6678236

Why does this solution to E (using treap) give Memory Limit Exceeded? :(

don't know, but obvious mistake is

`#define N 100005`

Sorry I don't get it; why is that a mistake?

When you're freeing a node you're not putting it back into the pool, so you need at least 200000.

Ah! Thanks. Still MLE though

http://codeforces.com/contest/431/submission/6680373

I can't understand the solution of problem D. Could someone explain it clearly?

What is not clear, tell more exactly please.

Calculating how many numbers have k 1 bits in the range [1.....x]

Number X we will analyze separately. Other numbers in range 1...

X- 1 smaller then X, so their binary representation have difference with X. We can divide they into groups by the number of first(largest) bit, which is such, that this bit in X is not equal to correspondent bit in all numbers of this group. Its obviously to understand, that any two of this groups do not intersect. To calculate all this numbers we can iterate all this groups, and calculate it only for each group separately. If we know bit with the first difference with X, we can choose another(smallest) bits in any way(so the size of group is 2^{i}. But we need only the numbers with exactly k 1 bits, co we can do this inC_{i}^{k - cnt}ways.(notation the same as in editorial)Got it. Thanks.

Thanks for the explanation...

Thanks :) . Was having a hard time . Now its completely clear :)

431D - Random Task KaiZeR The answer should be F(1..R) - F(1..L) and not F(1..R) - F(1..L - 1) as per the editorial since we have to take segment (n + 1)..2n into consideration.

what did u meant by the

first(largest) bit, do u mean the most significant bit ?Can someone explain me why this solution 6681438 get WA #4

I've slightly changed your binary search and removed bit count for initial result and it's worked 6689653;

I still haven't been able to understand the problem statement of problem E. So please explain what are we supposed to do in case of a query of Type 2 ? :(

As query 1 is

`H[p] :=v`

, query 2 asks you to find the minimum height of water surface you can get by pouringvunits of water into the tubes in some way.Thanks for the explanation.

You will choose a subset of the tubes and distribute a total of v liters of water among them.

Among the chosen subset of tubes ... you need to find the volume of the tube with maximum amount of liquid (mercury + water) (let's name this volume x)

This of course depends on the amount of water added to each tube and the amount of mercury initially at each tube before processing that query ... So You choose the subset of the tubes and distribute the water among them in order to minimize that value x.

The query of type 2 ... asks for the minimum possible value of x.

For Problem E, can we make a BST to get the Kth number in the sequence and then binary search the number K? Then we can know how many we should pour to every tube. Or I didn't understand the meaning of the problem? Will it get TLE?

Yes we can do in such way. It is the similar to the solution described in editorial, but only we searching for the volume in Kth tube, instead of the K. It will get OK)

Thx:)

431E — Chemistry Experiment: In order to be able to use Fenwik tree — you had to re-map large mercury volume values to the smaller range — why not just limit all volumes in the input to 100K or so???

Can someone explain the solution of problem C in a little bit more detail. I am unable to understand the DP part mentioned in the editorial.

The DP part refers to dynamic programming method of solving the task.

The method proposed in the editorial suggests to regard a subproblem

`Dp[n][is]`

where:`n`

has same meaning (total weight of a path) as in the problem description except for its range (`0 <= n <= 100`

).`Dp[n][0]`

is the number of paths of total weight`n`

if we revert the`d`

-condition (here we can use only those edges which weight is strictly less than`d`

).`Dp[n][1]`

is exactly what is asked for in the problem description (considered paths are all possible ones such that each of them has one or more edges with weight`d`

or larger).Note that the sum of both (

`Dp[n][0] + Dp[n][1]`

) is the number ofallpossible paths of total weight`n`

(i.e. without the`d`

-restriction).`Dp[0][0] = 1`

`Dp[0][1] = 0`

I believe that according to the solution (6676700), more exact formulas could be expressed as:

`Dp[n][0] = Dp[n-1][0] + Dp[n-2][0] + ... + Dp[n-DL][0]`

where`DL = min(d-1,n)`

.`Dp[n][1] = Dp[n-1][1] + Dp[n-2][1] + ... + Dp[n-K][1] +`

`+ Dp[n-d][0] + Dp[n-(d+1)][0] + ... + Dp[n-K][0]`

where`K = min(k,n)`

.I'm not sure I can clearly explain in English the reasoning which lies behind the formulas. Below is my best try.

Assume we have already calculated (somehow) the

`Dp[i][0]`

for all values of`i`

lesser than`n`

. Now we want to calculate`Dp[n][0]`

. We can think of`n`

as a number with the following possible decompositions:`(n-1) + 1`

,`(n-2) + 2`

,`(n-3) + 3`

, ...,`(n-m) + m`

. Now let's think of`m`

as a weight of one single edge. (Honestly, it is not yet clear to me why it is sufficient to regard only the case when we add onlyoneedge.Could someone else explain this partplease?)So, we can state that we have

`m`

different values of weight of an edge. Given any specific value of`m`

we can add`Dp[n-m][0]`

different paths (to the edge of weigth`m`

) to get the total weight of exactly`n`

. Now it is obvious that by adding together`Dp[n-m][0]`

taken for each possible different values of`m`

we will get the`Dp[n][0]`

value. This is exactly what formula for`Dp[n][0]`

is about.Now all we have to do is to determine the range for values of

`m`

. According to the possible values of the first index of`Dp[][]`

, this restriction should apply:`n-m >= 0`

. Thus,`m <= n`

. According to the definition of`Dp[][0]`

,`m`

must be less than`d`

, i.e.`m <= d-1`

. Minimum value for`m`

is obviously`1`

. Resulting range is:`1 <= m <= min(d-1,n)`

(see`DL`

above). Alternatively, we could define`Dp[n][0]`

as zero for all negative values of`n`

and consider`1 <= m <= d-1`

.Explanation of the formula for

`Dp[n][1]`

is a bit more complicated but the logic behind it is similar. I believe that if one understood the explanation for`Dp[n][0]`

then it would not be hard to extend similar approach to`Dp[n][1]`

. (Or, maybe, I'm just too lazy to explain it in full -- SMILE).I hope this will be useful for someone.

My related comment (in Russian)

Update: wrong value for Dp[0][0] was fixed (misprint).Do you know how to solve the simpler problem, without the d restriction, using simple O(nk) dynamics? Once you got that, assuming f(n,k) is the number of ways to break n into a sum of integers from 1 to k, the answer is simply f(n,k)-f(n,d-1).

I think there is a typo in the English version of editorial of problem E.

"such that in the tubes with smaller volume of the liquid can be poured all v liters of water and the

minimumliquid level do not exceed d."I think it should be "the

maximumliquid level doesn't exceed d".Someone told that B can be solved in

O(N^{2}). Can anyone please explain me about this solution?I don't think that's possible. If you consider the permutation as a path in a graph (where each student is a vertex), you need to find the path that contains each student exactly once, and the weight of the first two edges, plus two times the weight of the next two edges, plus three times the next two, etc, is the highest. This is very similar to Travelling salesman problem, which is NP-complete.

Now this may be an overkill but can someone please explain this in 4..

not so nerdy guy here. Any explanation for layman please

Let me try to explain by giving an example say

21(10101).I'll be using 0 based index for bits. 0th bit represents first bit from the right. We start from the most significant bit(the first one from the left).Now we consider all numbers first where this bit is 0(all those numbers will lie in our range as can be easily seen).So from the remaining bits(to the right of the present bit) we add to the ans number of ways in which we can select k of them.(in this case it will be 4Ck). Now we have to add those numbers in which the 4th bit is 1. This is the same as finding number of ways of selecting k-1 bits from the remaining bits(as we have already selected one). So we decrease k and move forward. Now we encounter a 0(3rd bit). We have already counted all solutions where this bit can be 1 (when we assumed 4th bit to be 0 and both of them cannot be 1 simultaneously as it will exceed the given number) . So this does not contribute(for the lack of a better word) anything more and we can move on. By same logic it can be seen that 0s will not be contributing to the answer. Now the problem is just a simplified version of the original. For this number (101 i.e 5) we have to answer for k-1 as we have already encountered a 1.

What does it mean when you say Y is less than X? It means that for some i, the i-th bit in X is 1, and i-th bit in Y is 0, while all higher bits are equal. That means we can choose all values of i such that i-th bit in X is 1, and calculate the number of ways to set the lower bits of Y to satisfy our condition (of having exactly k one bits).

in problem E,why the finaly answer is not d and is d — (v1 — v) / t? can someone explain (sorr for poor english)

First it finds a level d which is not the actual level. Then the empty space under d is v1. Fill it with v. If total number of tube is t then the actual level'll be at d-x where x = (v1-v)/t;

In the picture as there are 2 bars under d level the actual level is at d-x [ x = (v1-v)/2 ]

it is not optimall that find such d that v1=v ?

May be you can't directly find such d for v1 = v as liquid can be changed at any time.

I realized this,thanks for good explain and for image :)

Please improve your english. I don't understand anything in Problem D editorial.

PS: Is this editorial Google translated from Russian or something? Please stop doing that.

Can't 431C be solved using partitions? As in, the number of partitions of n-i [d<=i<=k] ?

Hi KaiZeR, In your editorial solution to this problem. I do not get the reason for (DP[0][0] = 1). According to me, it should be (DP[0][0] = 0) as we will always have

zeropaths when sum of path(n) is zero and when d is zero. Can you correct me if i am wrong ??We have only one way with length equals to 0. This way consists only root.

Can anyone explain me the problem D Example 2 as With N=5 The Range Is{6,7,8,9,10} among these- Only 6 and 10 are having exactly 2 digits 1 but we want 3 numbers than how the answer is 5

6 — 110 +

7 — 111

8 — 1000

9 — 1001 +

10 — 1010 +

There are three numbers.

thanks for help

Can anyone please explain me the test cases 1 and 3 for C ? I'm unable to understand.

Only for test case 3 ?

For the third test case:

1 -> 1 -> 2

1 -> 2 -> 1

1 -> 3

2 -> 1 -> 1

2 -> 2

3 -> 1

Only this ways satisfy the statement.

http://www.hastebin.com/qugasuduji.vala

I am unable to figure out why the above code (same logic as editorial) is leading to WA in test case 7. Could someone please help me identify where I am going wrong?

EDIT: Got it, I used int instead of long long which led to overflow

I suggest another solution for problem C.

Imagine the tree has k "floors" indexed downward. We can easily find out that k <= 100 because the deepest path that has weight n ends at n-th floor and n <= 100.

Next, we will calculate the number of paths of total weight n that only contain edges with weight 1..x, case1 with x = k and case2 with x = d-1. So the result = case1 — case2

Let dp[i][j] = number of paths of total weight j when we reach i-th floor. Then: dp[i][j] = sum(dp[i-1][j-t]) where t = 1..x => Number of paths = sum(dp[i][n]) where i = 1..100

Complexity:O(nk).Solution: 19061528Can anyone please

explain K-tree. I amnot ableto understand the editorial.431C — k-Tree:I have not yet exposed to dynamic programming, so I solved it recursively and got TLE in test case

#7. I'm having the hard time(nearly impossible) to trace the bug. Could anybody take a look at the code ? I doubt whether TLE is caused by my poor recursive method or my misunderstanding about the logic of mod 10^9 + 7.How to solve C in O(N) with partial sum? Appreciate any help.

My solution to problem C:

Apply dfs on the the tree and store the result in a dp table where dp[i][j] denotes the answer to the tree with sum = i at root and j = 0 or 1 based on whether while reaching the present node I have satisfied the property to have at least one edge having weight>=d.

Solution

P.S. Can anybody tell me how do I implement the same code iteratively?