Endagorion's blog

Codeforces Round #397 Editorial
By Endagorion, history, 8 years ago, translation, In English

Sorry for the wait! We'll be glad to answer your questions in the commens.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +151
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

For problem F. Why it's x >= y' < y?

I think it should be x <= y' < y.

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

the solution of e part says that if solution exists then the root node will be the center of the diameter.

can someone please give an intuitive or rigorous proof of this statement.

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

    From my understanding: Lets start with simple path. Now all the nodes between left unfolding and right unfolding are "contenders" for root. i.e., all the nodes which are not included in unfolding(outside of unfolding).

    Lets denote midpoint of current path be "m". Now if we perform a "left unfolding":

    1. with "m" being replicated: Midpoint of new diameter would be vertex on which unfolding is performed.

    2. else: New midpoint could be same vertex "m" or vertex on which unfolding is performed.

    Similarly for "right unfolding".

    In any case midpoint of diameter will be "outside" the unfolding. Now, It can be seen that further steps doesn't affect the midpoint. So, midpoint will always be outside the unfolding and thus can always be root.

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

Beautiful F with a great idea!

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

Can you please explain why Test case 15 in 765C will result in -1? shouldn't it be 10?

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

    Test case 15:666666 6666666 666665.The first person seems to win 10 times.However,there is 6 scores left,when the second person must win one time,but him can't.So the answer is -1.

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

“Obviously, now the answer for all left endpoints in range [j, i - 1) is y - x” The segment containing both Ai and Aj should has a left endpoint L <= j , And why the answer for the segments with left endpoint in range [j , i-1) also is y — x?

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

    You're perfectly right, intervals in the editorial are incorrect and we are already fixing it. It was much harder explaining it in words than in code :)

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

      Thanks for clarifying that, I have the same confusion when reading the explanation.

      I think it's acceptable to put some pseudocode in editorial if you think it's easier :)

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

Hi fellows!

For problem G (didn't get to it during the contest), I would have the following approach which I believe is simpler and takes running time complexity:

  1. Let t0 be the index of the first 0 in the string. Then we have k+t0 = 0 (mod N). However, for all subsequent ti > t0 (up to 40) where we have 0 in the string we must have k+ti = 0 (mod N). Substracting the first (for t0) equation we have k+ti-(k+t0) = 0 (mod N) which means ti — t0 == 0 (mod N). Notice that this does not involve k at all! Thus, for all relationtions with 0 in the string, except the first one we can just check if ti — t[i-1] is divisible by one of the primes in N. If one does not satisfy, then there is no solution.

  2. For the first relation with 0 in the string, we iterate over all primes in N (n in total) and try to make k + t0 mod pi == 0 [mod pi], which means k == pi-t0 [mod pi] AND k + t0 != 0 [mod p0, mod p1, .., mod pi-1].

  3. For all positions z0,z1,.. in the string where we have 1, we must have k+zj != 0 [mod p1], k+zj != 0 [mod p2] and so on. Thus we must have for each zj that k != pi-zj [mod pi].

  4. This means that for each pi we have several posibilities which satisfy: all which are not pi-zj AND which are not pi-tj (for the "lower" primes determined in step 2 above) AND for the particular prime P chosen in step 2 the reminder must be -t0. Thus, we have for all primes p1, p2, .., pn, a "list" of some posibilities for the reminder of k mod pi. By the chinese reminder theorem THERE WILL BE A SINGE SOLUTION to these modulo p1*p2*..*pn = B. Thus, there will be a total of |List1|*|List2|*..*|ListN| solutions for a particular prime P chosen at step 2 modulo B. Each List_i will be reduced in size (from pi-1) by at most 2*|s| or will hold a single element, so determining the sizes of the lists is easy. The solutions for different P's (chosen at step 2) are guranteed to be distinct since the same k cannot satisfy the conditions of step 2 for two distinct P's.

  5. We compute in O(n) the total number of solutions mod B by doing step 4 for each P chosen in step 2. Let this number be T.

  6. Let p1*p2*..*pn = B. We know that for each solution S in [0..B] we also have as solution S+B. Thus, if we are lucky and N%B == 0, the total number of solution will be (N/B)*T.

  7. If we are unlucky and N%B != 0, some of the solutions mod B will not be available for "the final step" between floor(N/T) and N. I haven't yet figured what to do in this case, but i think the approach might have some merit even up to here so I decided to share it.

What do you think about this approach? Are there any obvious flaws in it? Do you think it could be made to work?

Best, Mircea

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

    Sorry guys, there is a problem with the first observation. k+t0 = 0 (mod pj) for some j, not mod N.

    Will post if I can tweak it somehow.

    Best, Mircea

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

For problem E, I don't quite understand the definition of y' (or how's the array to be segment tree be defined?), as the array is decreasing shouldn't y be the perfect candidate that's been included in [l, r]?

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

For problem F,"We find the first element to the left of i which is not less than x." How can I do it within the complexity of O(logn)?

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

    We can compress the array elements into {1, ..., n}. Let us store the latest positions of all processed elements in a segment tree, now your question is a range maximum query. Alternatively, a treap without compression can be used.

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

Hah, I thought my approach to G had to be the wrong one, given how much time I needed to spend during the contest to get the "5 7 ..." case to perform reasonably. For comparison: http://codeforces.net/contest/765/submission/24667492

My solution has one optimization I don't see in either of KAN's or Endagorion's solutions: it checks if S is a palindrome, and in that case cuts the search space in half by treating masks as equivalent to their bit reversals. This sounds silly, but it actually deals nicely with the all-zero case, and the other cases are a factor 1.5 — 2 faster by virtue of having a forced one somewhere.

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

For problem F, i am still confused about the complexity. The step where we find some aj' = y' such that x ≤ y' < y and j' < j and then repeat it can end up in linear time. In the worst case, the complexity can go up to O(N * M).

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

    We need only such y', that

    y'  -  x  <  y  -  y'

    So, y' < (x + y) / 2

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

      Therefore, the next y' is the rightmost element on the prefix [0; j - 1] such that x <= y' < (x + y) / 2. Can you explain, how we can find all such y' in the complexity O(logN * log10^9)? I.e. we need to find every y' in O(logN). The only approach that can answer such queries I know is the segment tree with fractional cascading, but it seems like authors implemented something easier.
      Thanks

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

        We can compress the array elements into {1, ..., n}. Let us store the latest positions of all processed elements in a segment tree, now your question is a range maximum query. Alternatively, a treap without compression can be used.

        Didn't you read Endagorion's comment above?

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

        You can see my submission for further understanding, I tried to write more understable code.

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

      wow, such a brillant idea! Thank for clarifying it for me.

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

Can someone explain in another way what we have to do in D? Condition is a bit difficult to understand..

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

What is the two-way Tree DP being talked about in the editorial of E Problem?

→ Reply