### rng_58's blog

By rng_58, history, 5 years ago,

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!

• +198

| Write comment?
 » 5 years ago, # |   +30 Fairly hard problems this time. After one hour none solved, no ideas any more. I wish good luck to all contestants.
 » 5 years ago, # |   0 Solution for B please?
•  » » 5 years ago, # ^ |   -13 I found it will repeat no more than n,so simulate every time.It's O(n) But I got TLE what's wronghttps://atcoder.jp/contests/agc036/submissions/6497678
•  » » » 5 years ago, # ^ |   0 Yeah ,I found it , it's MLE in fact but I don't know why it tell me TLE.And I got AC now!
•  » » » » 5 years ago, # ^ |   0 And I think mine is faster than the editorial's I complete it only in O(n)!
•  » » 5 years ago, # ^ |   +7 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.
•  » » » 5 years ago, # ^ |   0 Not sure what binary lifting is, but your first explanation was clear and made sense. Thanks!
 » 5 years ago, # | ← Rev. 2 →   0 B: got RE at 22:39, AC at 22:41, because of boolean[MAX] vs boolean[MAX+1], so sad.
•  » » 5 years ago, # ^ |   0 I got TLE 1:24,TLE 1:34,Sad too. :(And I become Green in atcoder. (π_π)
 » 5 years ago, # |   0 How to solve C?
•  » » 5 years ago, # ^ |   0 pls will u tell me how to solve A ??
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +7 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$ .
•  » » » » 5 years ago, # ^ |   0 How do you ensure that you will only get integers for Y3 and X3?
•  » » » » » 5 years ago, # ^ |   0 Consider it as similar to the Euclid division lemmaa=bq+rIn 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
•  » » » » » » 5 years ago, # ^ |   0 Thanks!
 » 5 years ago, # |   +214 I don't understand how you do it on a regular basis. Problem D — the best problem of 2019 yet. My gratitude to maroonrk.
•  » » 5 years ago, # ^ |   +3 Exactly, it blew my mind when I solved it and I really loved it.
 » 5 years ago, # |   +8 I still couldn't quite understand how to solve D after reading the editorial, could someone pls give an explanation here? Thanks.
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   0 its my humble request to those who has solved D, please give some explanation