Endagorion's blog

By Endagorion, history, 8 days 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  
  • +146
  • Vote: I do not like it  

»
8 days 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.

»
8 days 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.

  • »
    »
    8 days 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.

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Beautiful F with a great idea!

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

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      so basically you cant start a new set when the opponent haven't even won at-least a set? ..but that does not explain what the tutorial is explaining because he said if a is dividable by k independent of b print out the solution moreover that wasn't mentioned in the question .. and im pretty curious why he said the score resets when he gives us the total points so i think im missing something here >,< .

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay. I get it now. I believe this is mentioned in "Note that the game consisted of several complete sets."

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if it's really complete sets then the 123 456 789 should be -1 you see 456+789 is not divisible by 123

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Correct. I didn't see the other cases before. Should be clarified by the prob setter.

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

  • »
    »
    7 days 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 :)

    • »
      »
      »
      7 days 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 :)

»
7 days 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

  • »
    »
    7 days 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

»
7 days ago, # |
  Vote: I like it -43 Vote: I do not like it

Just want bigger contribution

»
6 days 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]?

»
5 days 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)?

  • »
    »
    5 days 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.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In 765C why does case 14 produce output 9 while -1 in case 15?

  • »
    »
    4 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    case 15 : 666666 6666666 666665 --> Notice that b<k, Thus player B has never win any set --> player A wins all sets --> a mod k must be zero, Why? because all sets must be complete ( exactly one of the player must have k points in each set). Let's say that player A has win 10 times previously, thus his total score so far is 6666660 --> there are still 6 points being left that can't be a part of a complete set given that b is also can't (6<k and b<k thus violates the constraint of "all sets must be complete").

    case 14 : 123 456 789 --> The answer is the integer calculation of --> 456/123 + 789/123 = 3+6 = 9. This means that player A win 3 sets, while player B wins 6 sets. You can distribute the remainder of the points randomly as long as the points of each set doesn't exceed k.

»
5 days 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.com/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.

»
3 days 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).

  • »
    »
    3 days 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

    • »
      »
      »
      3 days ago, # ^ |
      Rev. 2   Vote: I like it 0 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

      • »
        »
        »
        »
        2 days 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?

      • »
        »
        »
        »
        2 days 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.

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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