Endagorion's blog

By Endagorion, history, 5 months 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  

»
5 months 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.

»
5 months 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.

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

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

Beautiful F with a great idea!

»
5 months 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?

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

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

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

      • »
        »
        »
        »
        5 months 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

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

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hint 1: Please read the below line again -
            Determine the maximum number of (completed) sets they could have played (without any uncompleted sets), or that the situation is impossible.

            Hint 2:
            Let Misha win A times, and Vanya win B times.
            Case 1: A < K and B < K
            This is easy to understand. I will get no complete set (because neither of them have won atleast K games). Therefore the answer is -1.

            Case 2: A >= K and B<K
            There can be multiple versions/ways to simulate the game, but simulating it in one such way can help us get the idea. So let's simulate -
            Set 1 -> A1, A2, A3, ... A(K-1), B1, A(K)
            Set 2 -> A1, A2, A3, ... A(K-1), B2, A(K)
            Set 3 -> A1, A2, A3, ... A(K-1), B3, A(K)
            .
            .
            .
            Set A/K — 1 -> 1 — A1, A2, A3, ... A(K-1), B(K-1), A(K)
            Set A/K -> A1, A2, A3, ... A(K-1), A(K)

            Quick observations -
            1) It is necessary for A to be divisible by K. (Why? — If A was not divisible K, then I would have been left with some K's which would never be able to give me a complete set. Keep in mind that B's are less than K) 2) Keep in mind that the total completed sets = A/K. Combining the results of all the sets, B can appear in not more than K-1 sets. (Why? — If it did then it would have been possible to create a completed set with B, K times.) So mathematically, A>=K AND B<K AND A%K == 0 then result = A/K

            Case 3: B >= K and A < K
            Similar to Case 2, therefore result = B/K

            Case 4: A >= K AND B >= K Set type 1) There will be A/K sets in which A wins.
            Set type 2) There will be B/K sets in which B wins.
            But what about A%K left A's ? And what about B%K left B's ?
            A%K is less than K, therefore we will place them with Set type 2 without affecting the result.
            B%K is less than K, therefore we will place them with Set type 1 without affecting the result.
            Result = A/K + B/K (obviously I am talking about floor operation)

            Example 1 -
            Test case 15: 666666 6666666 666665
            K = 666666
            A = 6666666
            B = 666665

            This would have fallen into Case 2, but notice that A is not divisible by K, therefore I will be left with A%K to do nothing, even after arranging all the B's in A/K sets. (Remember? I want to find only completed sets ?)
            Result = -1

»
5 months 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?

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

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

»
5 months 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

  • »
    »
    5 months 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

»
5 months ago, # |
  Vote: I like it -43 Vote: I do not like it

Just want bigger contribution

»
5 months 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 months 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 months 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 months 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?

  • »
    »
    5 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      By the logic you solved case 14, case 15 can be solved like 6666666/666666 + 666665/666666 = 10 + 0 = 10. You can distribute the remaining points as you like .. I am really not able to get the difference in both the cases.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        According to your calculation for case 15, player A has win 10 times (the 1st set until 10th set), hence total score for player A is 666666*10 = 6666660. The remaining score for A is 6666666-6666660 = 6 points. Now, please try to answer the following question "What is the possible score for players A and B in the 11th set?". Remember that in each set, one of the player must have exactly 666666 points.

»
5 months 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.

»
5 months 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).

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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?

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 months 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..

»
4 months 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?