rng_58's blog

By rng_58, history, 5 months ago, ,

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

Contest Announcement

Contest duration: 130 minutes

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

Let's discuss problems after the contest.

•
• +106
•

 » 5 months ago, # |   +16 5 minutes before the contest start :)
 » 5 months ago, # | ← Rev. 3 →   +30 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.
•  » » 5 months ago, # ^ |   +24 I'm getting WA on just one case and I don't have any clue about it. lol
•  » » » 5 months ago, # ^ |   +21 Same with mehttps://beta.atcoder.jp/contests/agc024/submissions/2536391Getting 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.
•  » » » » 5 months ago, # ^ |   +16 Actually, I got two case wrong initially, and I corrected N=2 case. But one case left...
•  » » 5 months ago, # ^ | ← Rev. 2 →   +49 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 and increase the diameter. Instead we should iterate over all edges incident to the center and consider cases when an edge will become the central one.
•  » » » 5 months ago, # ^ |   +8 Wow, the first method is exactly the same with mine. Now I got why I was wrong.
•  » » 5 months ago, # ^ |   +18
•  » » » 5 months ago, # ^ |   +5 The folder does not exist?
 » 5 months ago, # |   +62 What happened to khsoo01 at AGC024?
 » 5 months ago, # | ← Rev. 2 →   +22 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.
•  » » 5 months ago, # ^ |   +55 Ah it is accepted.
 » 5 months ago, # | ← Rev. 3 →   +28 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?".
•  » » 5 months ago, # ^ |   +8 I thought so too, which is why I asked for clarification.
•  » » 5 months ago, # ^ |   +5 We will construct a new tree T by "repeating" the following operation, but was it unclear?
•  » » » 5 months ago, # ^ |   +26 How many times? N times? 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)".
•  » » 5 months ago, # ^ |   +8 You can check last sample, it's impossible to get 12 leafs, after one operation on tree with 8 leafs.
 » 5 months ago, # |   0 Can someone please explain how to do problem C of the contest? The editorial is in Japanese! Thanks :)
•  » » 5 months ago, # ^ |   0 Sorry, we'll add English A-D later.
•  » » » 5 months ago, # ^ |   +8 Added full editorial. Sorry for the delay.
•  » » 5 months ago, # ^ |   +1 How to solve B? Also, are the test cases visible? Sorry, but I am new to the site
•  » » » 5 months ago, # ^ |   +6 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. Codeconst int N = 2e5+1; int n, p[N], ans = 0, seen[N]; int main() { ios::sync_with_stdio(false); //cout << fixed << setprecision(7); cin >> n; for(int i = 0; i < n; ++i) cin >> p[i]; fill(seen, seen+n+1, 0); for(int i = 0; i < n; ++i) { if(seen[p[i]-1]) seen[p[i]] = seen[p[i]-1]+1; else seen[p[i]] = 1; ans = max(ans, seen[p[i]]); } ans = n-ans; cout << ans << endl; return 0; } 
•  » » 5 months ago, # ^ |   +5 Note that if ai > ai - 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 nonzero ai, ai - 1 needed to be equal to ai - 1. Also, if ai > 0 or generally if ai > 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. Codeconst ll N = 2e5+2; ll n, a[N], ans = 0; int main() { ios::sync_with_stdio(false); //cout << fixed << setprecision(7); cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; a[0] = -1, a[n+1] = 0; for(int i = 1; i <= n; ++i) { if(a[i] > a[i-1]+1 || a[i] > i-1) { cout << -1 << endl; exit(0); } } for(int i = 1; i <= n; ++i) { if(a[i] <= a[i-1]) ans += a[i-1]; } cout << ans << endl; return 0; } 
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +5 Thank you so much for the explanation! Understood it well! :)
 » 5 months ago, # |   +24
 » 5 months ago, # |   +31 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?
•  » » 5 months ago, # ^ |   +23 Updated.
 » 5 months ago, # |   0 What is the expected solution for Problem C?
 » 5 months ago, # |   +108 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.