KaiZeR's blog

Editorial Codeforces Round #247 (Div. 2)
By KaiZeR, 11 years ago, translation, In English

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 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 — (v1 — 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(qlog2(n))
Решение: 6676668

  • Vote: I like it
  • +77
  • Vote: I do not like it

Comments Comments (84)
| Write comment?
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    great

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :))).

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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; }

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<<ans<<endl;
return 0;

}

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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 =(

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    segment trees?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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. :-/

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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".

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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: .

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot. :) That looks like a convincing algorithm for this problem.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just realized f(2 * N) - f(N) is monotonic. bangs head on the keyboard

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution is like your solution: 6678236

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    What is not clear, tell more exactly please.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it +4 Vote: I do not like it

        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)

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me why this solution 6681438 get WA #4

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ? :(

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    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).

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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).

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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".

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Someone told that B can be solved in O(N2). Can anyone please explain me about this solution?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 ]

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We have only one way with length equals to 0. This way consists only root.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    6 — 110 +
    7 — 111
    8 — 1000
    9 — 1001 +
    10 — 1010 +

    There are three numbers.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Only for test case 3 ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C in O(N) with partial sum? Appreciate any help.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is an Alternate DP solution — 139873483

→ Reply