AtCoder Grand Contest 030 will be held on Saturday (time). The writers are semiexp, sugim48, and DEGwer.
Contest duration: 110 minutes
The point values will be 200 — 800 (300) — 1000 — 1000 — 1400 — 1600.
Let's discuss problems after the contest.
By the way, this is the last contest of the year, and after this match, top 8 people by GP30 scores will qualify for tour finals. Four people (tourist, V--o_o--V, Petr, LHiC) have already qualified, but there are four more slots. Good luck!
Did you make beta version main one?
Yes. Now beta.atcoder.jp will be redirected to atcoder.jp. Please use this.
how to solve B — Tree Burning ? [Editorial available, i gonna read from that]
(I assumed that the distance from the Takahashi's residence is measured clockwise, since I'm more familiar with that metric).
Let bi the distance between i-th and (i+1)-th tree (b0 = a[0], and bn = L — a[n]). Then the answer is sum of xi * bi for some set of xi.
By toying around with a hand-written simulator, one can figured out that the most optimal solution has a form of either "RRR..RRLRLRLRL.." or "LLL..LLRLRLRL.." ("R" mean clockwise, "L" mean counter-clockwise. For the sake of simplicity, one only have to handle with the later case (the former can be handled by reversing the coordinate).
Again, with the above simulator, one can figure out the pattern for the set x.
For example, when n = 8, the pattern of x looked like following:
The array on the i-th line is the set x for the pattern with i letter "R" at the beginning of the move sequence.
I solved Problem B during the contest. My strategy is that the turning are always at the last trees, and we just check every possible number of turning. However, I do not quite get what the editorial means by
Here, we can assume that b − a = 0 − b = e − d = d − c = 1 (otherwise we can get a longer path in an obvious way).. Would anyone like to explain this?For example, if d - c = 1 doesn't hold, we can extend the path as in the picture above, so it never becomes the optimal path.
Oh.... For anyone else who was confused in a dumb way like me, d-c=1 means that d-c is one index off, not that d-c are actually one distance away.
Thank you two so much! I was also confused in that way!
if b = -1 doesn't hold，how can I get a longer path?
Attach 0 -> b+1 -> 0 at the beginning (this is a special case, the initial direction changes)
How did you get to the conclusion that turning always happens at the last trees, I personally think, I should have done something like xuanquang1999 did with the brute force solution, but I was too busy finding a DP solution, I was not able to come up with a solid greedy approach like yours so I would like to know the intuition!
When you get D accepted 49 seconds after the contest end...
I feel you, though in my case I got F accepted 2.5 minutes after contest and the difference between it and the one I submitted in the last minute of contest was that I removed one dimension of dp which was completely useless in the problem but I only realized it 1 or 2 minutes after contest ends T.T
My case is exactly the same as yours. I didn't solve it in time simply because I hadn't dealt with the case a[2i] != -1 && a[2i-1] != -1 properly QAQ Something even more annoying: I didn't solve any other problem, either. (Yet I've got rejected submissions) Sad...
I only had 11min for C, and somehow got the correct solution. I coded it very quick, but while doing it I thought it was wrong, so I just stopped in last 1 minute :(
I feel your pain.
258D - Little Elephant and Broken Sorting
Sorry, it seems I even participated in the contest and solved it. My memory is not good.
Ffs, stop using a meme in a wrong way. Do you really think the problem was stolen? Do you know how often it happens to invent an already existing problem?
This overused meme/question makes sense only if several problems are from other contests, or if the statement looks very similar, including the sample test.
Sorry, I didn't know the exact meaning of the meme. I just thought it's a coincidence.
Though it's hard to come up with a non-existent idea/problem, it's a little sad to find a problem in AGC you already solved somewhere before anyway.
My approach for problem B. Suppose that tree
is the last one that we burn, and assume that we arrive at it in the counter-clockwise direction. Let there be k trees within 
at which we change direction. It means that there may be either k or k + 1 trees in 
at which we change direction. For example:
The total distance travelled is given by the travel distance from 0 to
plus twice the travel distance from 0 to each of trees at which we change direction. If we fix 
, there is no reason not to change directions at as many trees as possible; k should be the minimum between the number of trees in 
and the number of trees in 
, and we should use the "k+1" pattern if possible. So, for any particular 
we can calculate the greatest possible travel distance in O(1) if we precompute prefix sums of xi. Trying all possible 
gives an O(N) solution.
It is easy to apply the same approach for the case that we arrive at
in the clockwise direction.
Your solution is very clear and clean! Thank u so much for sharing!