YerzhanU's blog

OpenCup 2015: GP of East and West
By YerzhanU, 10 years ago, In English

Let's discuss solutions! How to solve D, G and J?

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

J. Sort the edges. Binary search for the answer. Sliding window over the edges gives us a sequence of queries to add and remove edges; need to check if the graph ever becomes connected when executing the queries. This can be done using divide and conquer that uses DSU with rollbacks.

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

    Could you please elaborate on "divide and conquer that uses DSU with rollbacks". I have never heard of this technique before, so could you please point me to some source or provide a short explanation. Thanks a lot.

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

      Something like this: dynamic connectivity problem offline

      "DSU with rollbacks" — it's partially persistent DSU. You can save all changes in stack and "rollback" to previous state when you want.

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

        Yep, it's a part of Burunduk1's thesis.

        Suppose we have a sequence of queries that add and remove edges, or get the number of connectivity components; for simplicity, each edge is added exactly once, then removed exactly once. The recursive procedure will take a segment of queries [a,b) and a global DSU that already contains all edges that are present in the graph for the whole segment [a,b) (i.e. edges that were added with queries [0,a) and removed with queries [b,n)). The procedure will answer all these queries and roll back all the changes that it makes to the DSU. To do that:

        1. c=(a+b)/2,
        2. add all edges that were removed with queries [c,b) and added with queries [0,a)
        3. recursively solve for [a,c)
        4. roll back the changes made with 2.
        5. add all edges that were added with queries [a,c) and removed with queries [b,n)
        6. recursively solve for [c,b)
        7. roll back the changes made with 5.

        When we get to a segment [a,a+1), and query a asks for the number of connectivity components, we can just answer this query by looking at current state of the DSU.

        (Actually I believe this can be implemented a little shorter if we pass the list of edges to the recursive procedure by value, but in this problem I was too paranoid about the TL to do that)

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

          Thanks a lot. That is a very nice idea.

          Just one clarification, in point 5 shouldn't it be removed with queries [b,n) instead of [c,n).

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

    What is DSU with "rollback"?

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

G: Final order of numbers will be equivalent to sorting an array of pair(digit_sum(i), i). Now instead if you iterate through sum of digits, you can find number of numbers  ≤  N and with given sum of digits using dp. For any given sum of digits at most one number can be in its correct place, which you can find by binary search.

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

where can i see the problems??

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

Here is a solution of problem D.

If k = 2^x, the answer is always yes (Obviously). Else if k = 2x-1 or k = 2x, then f(k), the minimal n for which the answer is yes, equals to 2x+1.

f(2*x-1) >= 2x+1. |> Lets consider the last step, on which number k was obtained. (a, b) -> (a-b, 2b). 2b can't be equal to 2x-1. Then a-b = 2x-1; a >= 2x; b >= 1; n >= a+b >= 2x+1 <|

f(2*x) >= 2x+1, x is not a power of 2. |> Let p be an odd prime divisor of x. Initially all numbers equal to 1, thus are not divisible by p. The following invariant takes place: there is always a number which is not divisible by p. Indeed, if (a, b) -> (a-b, 2b) and a-b and 2b are divisible by p, then a and b are divisible by p. That means, we can not obtain a situation where one number is equal to 2x, and all other numbers equal to 0. Therefore n >= 2x+1 <|

Now if n = 2x+1, how to obtain 2x and 2x-1? The trick is to divide all the substance in two parts of volumes a and b, one of which is a power of 2. Then repeat the action on the two tubes until we are done. Why this works? Let's concider an action (a, b) -> (a-b, 2b). Since a+b = n, (a-b, 2b) = (2a%n, 2b%n). Therefore after t steps (a, b) will turn into (2^t*a%n, 2^t*b%n). Since n is odd and one of (a, b) is a power of 2, after some steps, this number will turn into 1, and on the next step it will turn into 2. Then the other number will be n-1 and n-2.

The only thing left is to divide in two parts. Let 2^x be the biggest power of 2 which does not exceed n. First unite 2^x tubes into one. Then after y steps you have (n-2^x)/(2^y) rounded up pieces of volume 2^y and one piece containing all the remaining volume. On y-th step you divide pieces of volume 2^(y-1) into pairs and unite them. If one piece was left without pair, you append it with the remaining piece. After x steps you have one piece of volume 2^y and one more piece containing all the remaining substance.

→ Reply