rng_58's blog

AtCoder Grand Contest 036 Announcement
By rng_58, history, 5 years ago, In English

We will hold AtCoder Grand Contest 036. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

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

Comments Comments (20)
| Write comment?
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Fairly hard problems this time. After one hour none solved, no ideas any more. I wish good luck to all contestants.

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

Solution for B please?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    I found it will repeat no more than n,so simulate every time.

    It's O(n) But I got TLE what's wrong

    https://atcoder.jp/contests/agc036/submissions/6497678

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

      Yeah ,I found it , it's MLE in fact but I don't know why it tell me TLE.

      And I got AC now!

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

        And I think mine is faster than the editorial's I complete it only in O(n)!

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

    The editorial is out. The key idea is that each time we run through all of the elements of $$$A$$$, the only thing that matters about the sequence from before those operations is its first element. That's because if $$$v$$$ is the first element, the entire sequence will be deleted upon encountering the first occurence of $$$v$$$ in $$$A$$$, and we then process the remaining suffix of $$$A$$$ starting with an empty sequence.

    We can compute some dps: $$$f(i) = $$$ first remaining element if we start with an empty sequence and process the suffix of $$$A$$$ starting at index $$$i$$$. $$$g(v) = $$$ first element if we start with a sequence with initial element $$$v$$$ and process all of $$$A$$$. Use $$$v = -1$$$ to denote the first element of the empty sequence.

    By inspecting $$$g$$$ for the cycle starting from $$$v = -1$$$, we can determine which element will be present at the start of the sequence after $$$K-1$$$ applications of $$$A$$$. The final application of $$$A$$$ can be simulated naively.

    Alternative approach in the editorial finds $$$g^{K-1}(-1)$$$ using binary lifting instead of inspecting its cycle structure.

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

      Not sure what binary lifting is, but your first explanation was clear and made sense. Thanks!

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

B: got RE at 22:39, AC at 22:41, because of boolean[MAX] vs boolean[MAX+1], so sad.

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

    I got TLE 1:24,TLE 1:34,Sad too. :(

    And I become Green in atcoder. (π_π)

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

How to solve C?

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

    pls will u tell me how to solve A ??

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

      Editorial solution is very easy to understand: Let us fix (X1, Y1) to (0, 0). Then, the area of the triangle will be |X2 × Y3 − Y2 × X3|/2. Thus, we can solve the problem if we find X2, Y2, X3, Y3 such that X2 × Y3 − Y2 × X3 = S. Here, let us also fix (X2, Y2) to ($$$10^9 , 1)$$$. Now we just need to find X3, Y3 such that $$$10^9 × Y3 − X3 = S$$$, which can be found from the quotient and remainder when dividing S by $$$10^9$$$ .

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

        How do you ensure that you will only get integers for Y3 and X3?

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

          Consider it as similar to the Euclid division lemma

          a=bq+r

          In this case it is just a = b*(q+1)-(q-r). We added subtracted q. So b is $$$10^9$$$ and $$$x_3$$$ is q+1 and $$$y_3$$$ is q-r

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

I don't understand how you do it on a regular basis. Problem D — the best problem of 2019 yet. My gratitude to maroonrk.

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

    Exactly, it blew my mind when I solved it and I really loved it.

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

I still couldn't quite understand how to solve D after reading the editorial, could someone pls give an explanation here? Thanks.

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

    Idea: No matter where you start, if there are no negative cycles, and while you are walking you increase your current sum by the edge you just passed through, then whenever you return to the same vertex the sum can never be smaller. This motivates the construction of {p_i} as described in the editorial. After that, we can see that {p_i} can always be chosen so that it's a few stretches of integers decreasing by 1 each stretch, and given this labelling we know what are the edges we must delete (and conversely deleting these give a valid solution, so an optimal solution must be of this form). The rest is just simple dp to construct the {p_i} sequence.

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

its my humble request to those who has solved D, please give some explanation

→ Reply