AtCoder Grand Contest 024 will be held on Sunday (time). The writer is DEGwer. This contest counts for GP30 scores.

Contest duration: 130 minutes

The point values will be 300 — 500 — 700 — 1100 — 1200 — 2300.

Let's discuss problems after the contest.

5 minutes before the contest start :)

I'm getting WA on 3 tests out of 107 in D. Seriously?

UPD: tests 17, 19, 49. What are they? And my answer for N=2 is "1 2", which should be correct.

UPD2: It wasn't a corner case. I was editing the representation of the original graph instead of its copy — now I'm surprised that passed 104 tests instead of ~50 out of 107.

I'm getting WA on just one case and I don't have any clue about it. lol

Same with me

https://beta.atcoder.jp/contests/agc024/submissions/2536391

Getting a WA in just one testcase hinted me that it is either a boundary case or a tricky case. Turns out I did not manage to handle the case N = 2 correctly.

Actually, I got two case wrong initially, and I corrected N=2 case. But one case left...

Yeah yeah I was getting WA on a single test (~53rd). When the diameter is even, I tried to add one vertex to each of the existing and in case if the diameter has grown recalculate the answer. It's incorrect since it may turn out that it's impossible to add one vertex for the tree to become one step closer to an optimal

andincrease the diameter. Instead we should iterate over all edges incident to the center and consider cases when an edge will become the central one.Wow, the first method is exactly the same with mine. Now I got why I was wrong.

Uploaded tests: https://www.dropbox.com/home/atcoder/atcoder_contests/atcoder_testcases/atcoder_testcases

The folder does not exist?

What happened to khsoo01 at AGC024?

Now this is interesting.

jcvb's only submission in the contest, https://beta.atcoder.jp/contests/agc024/submissions/2540895, submitted 9 seconds before the end of the contest, has been WJ for more than 7 minutes now.

This will determine whether he will get 0 points or 2300 points.

Ah it is accepted.

English translation of editorial for D isn't finished yet.

Also, statement for D should be more clear. I thought that I can only add one vertex to the tree and was like "How could such a pointless problem appear in Grand Contest?".

I thought so too, which is why I asked for clarification.

We will construct a new tree T by "repeating" the following operation, but was it unclear?

How many times?

Ntimes?N- 1 times? An infinite number of times? Once? Is zero times allowed? Yeah, it's unclear; that's why the standard way to write it is "repeating the operation an arbitrary number of times (including zero)".You can check last sample, it's impossible to get 12 leafs, after one operation on tree with 8 leafs.

Can someone please explain how to do problem C of the contest? The editorial is in Japanese! Thanks :)

Sorry, we'll add English A-D later.

Added full editorial. Sorry for the delay.

How to solve B? Also, are the test cases visible? Sorry, but I am new to the site

You have to find the longest subsequence of consecutive values (values are consecutive, not their location in the array). When you move all the elements that are not in this subsequence to either the beginning or end, they will "bubble" together. For example, say the array was 2 5 3 1 4. Then, 2 _ 3 _ 4 is the longest such sequence. If we move 1 to the beginning and 5 to the end, then the sequence will come together and we will have 1 2 3 4 5.

We simply find the length of this sequence and subtract the length from

n.CodeNote that if

a_{i}>a_{i - 1}+ 1, then it is impossible (this follows from the fact that after any operation on an element, that element can never decrease, and at some point for nonzeroa_{i},a_{i - 1}needed to be equal toa_{i}- 1. Also, ifa_{i}> 0 or generally ifa_{i}>i- 1, it is impossible, since those are the maximum values those elements can achieve.Then, we see that for any contiguous segment of increasing numbers, the minimum number of operations needed to get that segment is equal to the highest value in the segment (i.e. if your segment is 0 1 2 3, you need 3 operations to get to that. If your segment is 3 4 5, you will have needed 5 operations, regardless of what the values before 3 are). Thus, for each contiguous segment with increasing values, we can add the highest value of the segment to our answer.

CodeThank you so much for the explanation! Understood it well! :)

Very sad :(

https://beta.atcoder.jp/contests/agc024/submissions?f.Task=agc024_f&f.Language=&f.Status=&f.User=Benq

Thanks for another great contest!

Could you also update https://docs.google.com/spreadsheets/d/1T-hKu_vIh8l4EiW6XTWOvP0evzsWj0f45JNNgou21Cc/edit#gid=695896678 with AGC 023 and AGC 024?

Updated.

What is the expected solution for Problem C?

Just want to say that AtCoder is quickly becoming one of my favorite platforms because you all manage to make really good problems without a reliance on advanced data structure/algorithm knowledge, but rather with a reliance on thinking cleverly. This contest was obviously quite difficult (as all AGC's are), but I think from reading the editorial that the most advanced algorithm concepts were DP and finding the diameter of a tree, which are covered in like basic algorithm/data structure classes. That is very impressive.