### KaiZeR's blog

By KaiZeR, 8 years ago, translation,

## 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

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 ... 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 Cik - cnt ways, where cnt — the number of 1-bits in X, bigger then i, and Cnk — 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(log2(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 v1 = t * d - (a[0] + a[1] + ... + a[d - 1]) — the total maximum amount of the water which can be poured. If v1 < 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 — (v1v) / 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(qlog2(n))
Решение: 6676668

• +77

 » 8 years ago, # |   +1 I clicked the solution link and got "You are not allowed to view the requested page" :P
•  » » 8 years ago, # ^ |   +5 fixed
 » 8 years ago, # |   +14 KaiZeR just made Guinness world records for fastest editorial posting :P .
•  » » 8 years ago, # ^ | ← Rev. 2 →   +12 Thanks. It will have been made when I publish an editorial for E.
 » 8 years ago, # |   0 Is there any better solution for Problem B...?? If the input was big then how do we solve it.?? Any idea please.. :D
 » 8 years ago, # |   +8 How can we prove that function is monotone in problem D?
•  » » 8 years ago, # ^ |   +1 I have written it in editorial. Please, re-read it more attentively.
•  » » » 8 years ago, # ^ | ← Rev. 3 →   +3 Oh, got it, Truly nice observation. ty :)
 » 8 years ago, # |   0 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.
•  » » 6 years ago, # ^ |   0 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...
•  » » 4 years ago, # ^ |   0 Wow I liked your approach it worked, did it easily ;)
•  » » 3 years ago, # ^ |   0 you are genius bro, I understood the solution now. I analyzed your solution then got to know a new concept. You are great
•  » » 2 years ago, # ^ |   0 your idea is similar to that of counting the solution in the renowned "coin change" problem of dp and then subtracting the solutions in which coins>=d doesn't occur. isn't it?
•  » » » 15 months ago, # ^ |   0 yes correct
•  » » 23 months ago, # ^ |   0 great
•  » » 18 months ago, # ^ |   0 thanks man , your idea is amazing
•  » » 15 months ago, # ^ |   0 Thanks a lot it helpedOptimized version of your codehttps://codeforces.com/contest/431/submission/108631970Time: O(n) space: O(2*n)
•  » » 10 months ago, # ^ |   0 Top-down version https://codeforces.com/contest/431/submission/123805240
 » 8 years ago, # |   0 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 : for(int i=1; i<=n; i++) for(int j=i-1; j>= i-k && j>=0; j--) dp[i]+=dp[j]; and then doing the same for k=d-1 for(int i=1; i<=n; i++) { for(int j=i-1; j>= i-d+1 && j>=0; j--) dpp[i]+=dpp[j]; } and the answer will be dp[n]-dpp[n] % 1000000007
•  » » 8 years ago, # ^ |   0 got it it was just about doing % in the right place :|
 » 8 years ago, # |   0 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 :))).
 » 8 years ago, # | ← Rev. 2 →   0 For Problem C, i am getting a Time Out with this implementationunsigned 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; } for (int i = 1; i <= k; i++) { if (c+i <= n) { if (i >= d) foo(c+i,n,k,d,true); else foo(c+i,n,k,d,take); } } }int main (int argc, const char * argv[]) { int n,k,d; ans = 0; cin>>n>>k>>d; for (int i = 1; i <= k; i++) { if (i <= n) { if (i >= d) foo(i,n,k,d,true); else foo(i,n,k,d,false); } else break; } cout<
•  » » 8 years ago, # ^ |   +1 Since you didnt use memo, your program can run up to o(k^n)
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   0 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
•  » » » 8 years ago, # ^ |   0 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..
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +3 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 =(
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ |   0 segment trees?
•  » » » 8 years ago, # ^ |   0 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. :-/
•  » » » » 8 years ago, # ^ |   +11 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.
•  » » » » » 8 years ago, # ^ |   0 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.
•  » » » 8 years ago, # ^ |   +3 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".
•  » » » » 8 years ago, # ^ |   0 With the help of Xellos's comment, I think I get the idea now. Thanks.
•  » » 8 years ago, # ^ |   +7 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 x such that when the smallest x elements are flooded, the water surface would reach above the x-th but not above the x + 1-st element; that can also be done by adding whole groups of numbers to the x flooded numbers and when we can't add a group, then adding its elements. Time complexity: .
•  » » » 8 years ago, # ^ |   0 Thanks a lot. :) That looks like a convincing algorithm for this problem.
•  » » » » 8 years ago, # ^ | ← Rev. 4 →   0 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 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 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.
•  » » » 8 years ago, # ^ |   0 :) I just coded your algorithm, and it's so hard for me to implement. It's my first time though. 6685388
 » 8 years ago, # |   +1 i guess problem E is O((q+n)logn)...
 » 8 years ago, # | ← Rev. 2 →   +2 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 just hi = 1e18. (Making this change passed it in practice).To make it easier to explain, let's call those numbers which have exactly k 1-bits in their binary representation as good numbers.Let's consider the binary representation of N to be xxxx. Now, 2 * N will look like this: xxxx0.Observe that for every good number  <  = 2 * N such that its 0-th bit is set to 0, there exists an identical good number  <  = N (by just doing one right shift).Now, let's say f(X) = Number of good numbers  <  = X.Since we are calculating f(2 * N) - f(N), those good numbers  <  = 2 * N which 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 of good numbers  <  = 2 * N whose 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 has m good numbers less than it.
•  » » 8 years ago, # ^ |   0 I just realized f(2 * N) - f(N) is monotonic. bangs head on the keyboard
•  » » 8 years ago, # ^ |   0 My solution is like your solution: 6678236
 » 8 years ago, # |   0 Why does this solution to E (using treap) give Memory Limit Exceeded? :(
•  » » 8 years ago, # ^ |   +3 don't know, but obvious mistake is #define N 100005
•  » » » 8 years ago, # ^ |   0 Sorry I don't get it; why is that a mistake?
•  » » » » 8 years ago, # ^ |   +3 When you're freeing a node you're not putting it back into the pool, so you need at least 200000.
•  » » » » » 8 years ago, # ^ |   0 Ah! Thanks. Still MLE thoughhttp://codeforces.com/contest/431/submission/6680373
 » 8 years ago, # |   -9 I can't understand the solution of problem D. Could someone explain it clearly?
•  » » 8 years ago, # ^ |   +4 What is not clear, tell more exactly please.
•  » » » 8 years ago, # ^ |   +1 Calculating how many numbers have k 1 bits in the range [1.....x]
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   +4 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 2i. But we need only the numbers with exactly k 1 bits, co we can do this in Cik - cnt ways.(notation the same as in editorial)
•  » » » » » 8 years ago, # ^ |   0 Got it. Thanks.
•  » » » » » 8 years ago, # ^ |   0 Thanks for the explanation...
•  » » » » » 7 years ago, # ^ |   0 Thanks :) . Was having a hard time . Now its completely clear :)
•  » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ |   0 what did u meant by the first(largest) bit, do u mean the most significant bit ?
 » 8 years ago, # |   0 Can someone explain me why this solution 6681438 get WA #4
•  » » 8 years ago, # ^ |   0 I've slightly changed your binary search and removed bit count for initial result and it's worked 6689653;
 » 8 years ago, # |   0 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 ? :(
•  » » 8 years ago, # ^ |   0 As query 1 is H[p] :=v, query 2 asks you to find the minimum height of water surface you can get by pouring v units of water into the tubes in some way.
•  » » » 8 years ago, # ^ |   0 Thanks for the explanation.
•  » » 8 years ago, # ^ |   +3 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.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Got it . Thanks :)
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ |   +1 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)
•  » » » 8 years ago, # ^ |   0 Thx:)
 » 8 years ago, # |   0 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???
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ | ← Rev. 4 →   +1 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 of all possible 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 only one edge. Could someone else explain this part please?)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).
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 "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."May you please explain why? Shouldn't it be Dp[n-m][0] multiplied by Dp[m][0]?
•  » » » » 2 years ago, # ^ |   0 After all those :) years... I'm sorry, I hardly remember what that problem was about. Maybe I will find time to look into it later again (no promises, though).
•  » » » » » 6 months ago, # ^ |   0 Haha, you truly are one champion. And thanks for posting this comment.
•  » » » » » » 6 months ago, # ^ |   0 Adding one more explained code solution : https://codeforces.com/contest/431/submission/135665200
•  » » 8 years ago, # ^ |   +1 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).
 » 8 years ago, # |   +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 minimum liquid level do not exceed d."I think it should be "the maximum liquid level doesn't exceed d".
 » 8 years ago, # | ← Rev. 2 →   0 Someone told that B can be solved in O(N2). Can anyone please explain me about this solution?
•  » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   0 Now this may be an overkill but can someone please explain this in 4.."Iterate number of bit will be the first(from biggest to smallest) which have difference in X and our number, which amount we want to calc. Let's first difference wiil be in i-th bit(it's possible, if in X this bit equals to 1, because our number does not exceed X). Then other smallest bits we can choose in any way, but only general number of one bits will equals to k. We can do this in Cik - cnt ways, where cnt — the number of one bits in X, bigger then i, and Cnk — binomailany factor. Finally, you should not forget about X (if it, of course, has k one bits)."A,2014-05-24 not so nerdy guy here. Any explanation for layman please
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » 8 years ago, # ^ |   0 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).
 » 8 years ago, # |   0 in problem E,why the finaly answer is not d and is d — (v1 — v) / t? can someone explain (sorr for poor english)
•  » » 8 years ago, # ^ |   +6 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 ]
•  » » » 8 years ago, # ^ |   0 it is not optimall that find such d that v1=v ?
•  » » » » 8 years ago, # ^ |   +1 May be you can't directly find such d for v1 = v as liquid can be changed at any time.
•  » » » » » 8 years ago, # ^ |   +1 I realized this,thanks for good explain and for image :)
 » 8 years ago, # |   0 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.
 » 8 years ago, # |   0 Can't 431C be solved using partitions? As in, the number of partitions of n-i [d<=i<=k] ?
 » 8 years ago, # |   0 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 zero paths when sum of path(n) is zero and when d is zero. Can you correct me if i am wrong ??
•  » » 8 years ago, # ^ |   0 We have only one way with length equals to 0. This way consists only root.
 » 8 years ago, # |   0 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
•  » » 8 years ago, # ^ |   +6 6 — 110 + 7 — 111 8 — 1000 9 — 1001 + 10 — 1010 +There are three numbers.
•  » » » 8 years ago, # ^ |   0 thanks for help
 » 7 years ago, # |   0 Can anyone please explain me the test cases 1 and 3 for C ? I'm unable to understand.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Only for test case 3 ?
•  » » » 7 years ago, # ^ |   +11 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.
 » 7 years ago, # | ← Rev. 2 →   0 http://www.hastebin.com/qugasuduji.valaI 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
 » 6 years ago, # | ← Rev. 2 →   0 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..100Complexity: O(nk) . Solution: 19061528
 » 6 years ago, # |   0 Can anyone please explain K-tree. I am not able to understand the editorial.
 » 6 years ago, # | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   0 It is TLE. suppose n=100, k = 100, d = 1; First layer: 100 cases next: 99 + 98 + . . . . ~10000 this grows exponentially.
•  » » » 2 years ago, # ^ |   0 btw recursion can be changed a bit to make it dp: Here is my "stylish recursion":74765820
 » 5 years ago, # |   +3 How to solve C in O(N) with partial sum? Appreciate any help.
 » 4 years ago, # | ← Rev. 3 →   0 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?
 » 2 years ago, # |   0 Can anyone please tell me what is wrong in this approach.https://codeforces.com/contest/431/submission/70114588For every node 'i' i'm traversing all its k children and in between the path if n==0 and ndoei>=d was present I'm saving the state in dp dp[nodei][n]=1 and increasing the number of paths.
 » 20 months ago, # | ← Rev. 2 →   0 #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll M = 1000000007; int n, k, d; cin >> n >> k >> d; ll s[10000] = {1}; for (int i = 0; i <= n; i++) { for (int j = 1; j <= k; j++) { s[i + j] = (s[i + j] + s[i]) % M; } } ll S[10000] = {1}; for (int i = 0; i <= n; i++) { for (int j = 1; j < d; j++) { S[i + j] = (S[i + j] + S[i]) % M; } } cout << ((s[n] - S[n]) % M + M) % M; } O(n) solution
 » 5 months ago, # |   0 Here is an Alternate DP solution — 139873483