We will hold AtCoder Grand Contest 036. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc036
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190721T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: maroonrk
- Rated range: All
The point values will be announced later.
We are looking forward to your participation!
Fairly hard problems this time. After one hour none solved, no ideas any more. I wish good luck to all contestants.
Solution for B please?
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
Yeah ,I found it , it's MLE in fact but I don't know why it tell me TLE.
And I got AC now!
And I think mine is faster than the editorial's I complete it only in O(n)!
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.
Not sure what binary lifting is, but your first explanation was clear and made sense. Thanks!
B: got RE at 22:39, AC at 22:41, because of boolean[MAX] vs boolean[MAX+1], so sad.
I got TLE 1:24,TLE 1:34,Sad too. :(
And I become Green in atcoder. (π_π)
How to solve C?
pls will u tell me how to solve A ??
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$$$ .
How do you ensure that you will only get integers for Y3 and X3?
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
Thanks!
I don't understand how you do it on a regular basis. Problem D — the best problem of 2019 yet. My gratitude to maroonrk.
Exactly, it blew my mind when I solved it and I really loved it.
I still couldn't quite understand how to solve D after reading the editorial, could someone pls give an explanation here? Thanks.
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.
its my humble request to those who has solved D, please give some explanation