### rng_58's blog

By rng_58, history, 4 years ago, ,

AtCoder Grand Contest 001 will start soon (time).

Note that you need to click the blue button here to register.

Let's discuss problems after the contest.

The contest duration is changed to 110 minutes.

The contest has finished. How was the contest?

Congratulations to cgy4ever for winning!

Editorial: https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf (English is at the bottom)

UPD: The rating is updated.

• +118

 » 4 years ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   +13 sorry i can't find the blue button to register!
•  » » 4 years ago, # ^ |   +21
•  » » 4 years ago, # ^ |   +22 I was worried about the same thing. If you are logged in (see your username on the top left) and don't see a button, that means you are already registered! :)
•  » » » 4 years ago, # ^ |   +11 OH MY GOD!!! How stupid am I...! SORRY I had forgotten that I had registered in the contest yesterday !!! Don't be worry , site is working perfect !It will be great if you add "You are registered already! Don't be worry friend!" instead of blue button when you are registered before , for someones like me ;)
 » 4 years ago, # |   +29 It'd be nice if there was a countdown counter for the nearest upcoming contest somewhere on the main page of the contest, then, one shouldn't worry about missing the contest Thank you :D
 » 4 years ago, # |   0 How does the contest difficulty compare to a codeforces div1 or div2 regular round?
 » 4 years ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 4 years ago, # |   +5 Can I view leaderboard without logging in/registering?
 » 4 years ago, # | ← Rev. 2 →   +8 Awesome Contest !! Btw, how to solve C ?EDIT: Super Fast Editorial Thanks!
•  » » 4 years ago, # ^ |   +23 After all there will be a center of a tree. It will be vertex or middle of an edge. Let's try all possibilities and calc distances from center to all vertices (using BFS). We have to delete all vertices with distance greater than k / 2. It is O(n 2).
•  » » » 4 years ago, # ^ |   0 I tried to solve C . But I can't solve it . My approach was :First I tried find out the any Two Farthest Distant node (Let's say U & V ) using BFS. Then I ran a BFS and find the distances of other Nodes from U. If any Node's distance is greater than K count those Nodes.Again I ran a BFS and find the distances of other Nodes from V. If any Node's distance is greater than K count those Nodes.Then I printed the minimum of Both counter . Can you please say where am I getting error ? Here is my Code : http://agc001.contest.atcoder.jp/submissions/809066Thanks in advance .
•  » » » » 4 years ago, # ^ |   0 10 21 21 31 41 51 61 71 82 93 10 The answer is 2 (delete 9 and 10). You will print 7.If I correctly understand your solution.
•  » » 4 years ago, # ^ |   +21 I had an alternative solution for C.Let's root the tree anywhere. Define the height of the leaf as 1 and the height of the empty tree as 0. Also, since the tree has to be connected at the end, we can only remove from leaves upwards. Now calculate the following DP. a[i][j] — the minimum number of nodes that we need to remove from the subtree i, such that the height of the tree is exactly j and the diameter of the resulting subtree will be at most K. Let s denote the son of i. (equals to the amount of nodes in the subtree)The idea is that if we want a height j, then we pick one deepest son, which will give us height j - 1, and then the rest of the children need to be both not deeper and not give a diameter bigger than K in combination with the deepest son. We can precompute the inside minimum as prefix array and do the whole computation efficiently.Finally, we need to accommodate for the fact that we have picked the root randomly. This means that for any subtree we can now decide to remove the rest of the nodes, not belonging to this subtree.
•  » » » 4 years ago, # ^ |   0 My idea is the same just that I forgot about random rooting... Thanks for your explanation,at least now I know what was the problem. :)
•  » » 4 years ago, # ^ |   +31 People already explained the smart way using tree centers.If you're dumb like me, you can also code a DP(v, maxDepth) that tells you how many vertices you can pick in v's subtree such that the height is smaller or equal to maxDepth and diameter is smaller or equal to K. Recurrence relation is: #case 1: biggest child depth is smaller than maxDepth-1 if maxDepth == 0: dp[v][maxDepth]=1 else: dp[v][maxDepth] = dp[v][maxDepth-1] #case 2: biggest child depth is equal to maxDepth-1 maxAllowedDepth = min(maxDepth-1, k - 1 - maxDepth) s = sum (dp[child][maxAllowedDepth]) dp[v][maxDepth] = max (1 + dp[child][maxDepth-1] + s - dp[child][maxAllowedDepth]); 
•  » » » 4 years ago, # ^ |   +9 Oh hey, I was not the only one. :)I like tasks like this. You can make your life easier if you spot one fact, but even if you don't, you can still work your way through.
 » 4 years ago, # |   +13 Nice problems. How to solve D,E?
•  » » 4 years ago, # ^ |   +31 E: Since a i, b i are small, you can find all pairs (a i + a j, b i + b j) using a 2D FFT. Maybe also 2D Karatsuba. Then, you just need the sum of binomial coefficients over all pairs.
•  » » » 4 years ago, # ^ |   +21 This FFT would take operations, isn't that too much?
•  » » » » 4 years ago, # ^ |   +15 Maybe, hard to say. I've squeezed through worse things.
•  » » » 4 years ago, # ^ |   +5 Did this approach pass? I had thought of this solution but didn't bother trying to code it because I was worried about precision (maybe 2 NTT's could have helped here) and time issues. Btw official solution has a much nicer way of computing the same value.
•  » » » » 4 years ago, # ^ |   +5 Did this approach pass? Considering my computer has been lagging like crazy for the past few weeks, I had no chance of writing something worth submitting. (I was writing a fast Karatsuba.) So I can't answer your question — yet.
 » 4 years ago, # |   +10 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 4 years ago, # |   +8 Can the C be done in O(n)?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -8 Yes, instead of checking for every vertex( x in editorial) we only take the center of the tree and remove the nodes which has distance more than K/2(for even). Is It Wrong?
•  » » » 4 years ago, # ^ |   0 Sure, it is wrong, because the optimal center of the reduced tree does not necessarily coincide with the center of the original tree.Imagine a long bamboo and a full binary tree on one of its ends. When you cut just two vertices from the other end, the diameter is decreased by 2, and the center shifts by one vertex.
 » 4 years ago, # | ← Rev. 3 →   0 Could anyone please tell why the following fails when k is odd in problem C : (i)Proceed as when k is even. (ii)if there is at least one vertex with distance greater than k/2 subtract 1 from the final answer for this centre.
•  » » 4 years ago, # ^ |   +3 You can add (or subtract) not just one vertex, but all vertices of the required depth in one whole subtree.
 » 4 years ago, # |   +21 Solved E in O(NC). Looks like it wasn't intended.
•  » » 4 years ago, # ^ |   +8 Really? My solution had just 2NC additions and didn't pass.
•  » » » 4 years ago, # ^ |   +8 http://pastebin.com/PfuS8CZY~1.5 secP.S. There is "Custom Test" tab. Maxtest is obvious so you don't need to submit to get TL.
•  » » » » 4 years ago, # ^ |   +8 Oh, thanks, I didn't notice this tab.
 » 4 years ago, # | ← Rev. 2 →   +8 E: We should count the ways to go from (-a_i,-b_i) to (a_j,b_j) and sum them up. It can be done in simple (2000*2)^2 DP and easy modification in the case of i != j.By the way, it is my first time to get such a good place and I'm very excited!
 » 4 years ago, # |   +33 After judging for ~15min about problem F, I got MLE on all the testcases. So can we see the status of each testcase during the judging? And I don't know why the judge is so slow for a MLE code.And after debuging for ~30min, I found I output the position of each elements in the permutation, and all the three samples are involution( p(p(i)) = i).
•  » » 4 years ago, # ^ |   0 I believe the judger runs the code on all tests and only then reports the first failure. This is either a flaw in the system or a deliberate attempt to completely hide any information about the test number the failure was on (even if they hide the progress bar of testing, one can still say something based on the timing of the verdict).
•  » » » 4 years ago, # ^ |   0 Judge runs on all tests and sorts them in the order of verdict.
•  » » 4 years ago, # ^ |   0 Yes, we'll try to implement this in the future.
 » 4 years ago, # |   +45 Thank you snuke, rng_58 (and other who prepared it) for the contest! My thoughts: B: It is interesting. You need to draw a good picture to get the right formula. C: If you know what is the center of a tree, then it will be easy. (so for me it is easier than B) D: A good constructive task. For me the key is to compute the sum of degree: if there are more than 3 odd numbers, then the number of edges can't be enough. A bit complicated but that is fine since you can try many times. E: Very interesting, the solution is quite simple and you just need the right idea. I love this one. F: It is not hard to guess the O(n^2) solution, and you can submit it to know that is correct. I don't have time left to think about how to speed up it. I think it may be good to give some points for O(n^2) solution for F.Overall the contest was nice and the difficulty is good (It is too short for me to solve F during the contest, but someone who is good at data struct may have a chance).Btw, I've experienced some delay (like need 1~2 minutes to load the problem, after hit submit I got 403 error). Maybe it is just because my internet is bad.
•  » » 4 years ago, # ^ |   0 Yeah I think subtasks could be an interesting distinguishing feature for @coder compared to cf and tc. Having done IOI with subtasks in high school, it feels very different in a lot of open competitions where there is only AC or nothing. Of course we don't know how much they will use it in future contests but I think it has potential to make for some interesting contests.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yeah,it will be fine,but not with subtasks like ioi where O(N) and must have different scores.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +48 Initially we were planning to give partial score for O(n 2) in F, but it turned out that the following stupid solution passes: while(1){ updated = false; for(i=0;i= K && P[i] minus P[j] == 1){ swap(P[i], P[j]); updated = true; } } if(!updated) break; } 
 » 4 years ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
•  » » 4 years ago, # ^ | ← Rev. 3 →   +31 So you guys take wrong submissions as a factor of rating calculation? I found myself was 81th in the AGC001's standing but 87th in the whole rank. It's a little weird to find myself have a better rank in the standing than someone but gain less rating.Anyway thanks for the interesting problems.:)
•  » » » 4 years ago, # ^ |   +36 No, that should be a bug. We'll look into it.
•  » » » » 4 years ago, # ^ |   +33 The rating updater ignored the rule 'When Status of Judging is CE (compile error,) you will not be penalized.'. Now this bug was fixed and ratings were re-updated.
•  » » 4 years ago, # ^ |   +31 Well, isn't this update too aggressive? I mean, you calculated the ratings based on only one competition, but the range of rating looks quite wide. Highest is 3154 and lowest is 9. If you incrementally update this rating from now on, I'm afraid that top coders easily get strange ratings such as 6000 and you may set the ratings of many lower coders to 1.
•  » » » 4 years ago, # ^ |   +20 Judging from users' competition history page, I guess the cut-line of so-called target or LGM (I hope there's such a highest grade in AtCoder too!) will be 3900 or 4000. I think just the scale of AtCoder's rating is much larger than TC or CF. Even for the first time my rating is larger than my TC/CF's highest rating.
•  » » » 4 years ago, # ^ |   +57 The rating system is significantly different from TC or CF's rating.If you click "Competition History" under the rating graph, you can see the history of performances. For example, from here you can see that his performance was 4020. It represents how well you performed in previous competitions. This value won't explode, and if you take the first place in AGC this value will be always around 4000.In TC or CF, if you keep getting the performance of X, your rating starts around the initial rating (1200 or 1500) and gradually converges to X. This means that when X is lower than the initial rating, your rating will gradually decrease. In order to avoid that, in AtCoder's rating system, Rating = (weighted average of Performance) — f(# of competitions)where f(1) = 866 and f(∞) = 0.This means that if you keep getting the performance of X, your rating starts from X - 866 and then gradually converges to X.The function f was chosen such that you can't get too high rating just because you get lucky in a few first matches, while the rating converges as fast as possible.I omitted some details of rating formula here, it will be published later.
•  » » » » 4 years ago, # ^ |   +29 Wow, this system is fun, I got 3000+ in one day. :PAnd I noticed "6 Dan" in my profile? Is that something depends on rating? Seems we have: 26xx ~ 27xx 4d 28xx ~ 29xx 5d 30xx ~ 31xx 6d 32xx ~ 33xx 7d? 34xx ~ 35xx 8d? 36xx ~ 37xx 9d? 38xx ~ 39xx what will this be?
•  » » » » 4 years ago, # ^ |   +10 Thank you for explanation. It sounds interesting system.
•  » » » » 4 years ago, # ^ |   +5 You say f(1)=866, but after recent "fix", I see f(1)=1200. Which is correct actually?
•  » » » » » 4 years ago, # ^ |   +13 Now 1200 is correct (the old system was indeed too aggressive as ir5 pointed out). We'll publish the rating formula within a week.
•  » » » » » » 4 years ago, # ^ |   0 If possible, I want to see the rating formula. Where is it?
 » 4 years ago, # |   0 Why does the following fail in C when k is odd?For every vertex, consider it as center. Now find all nodes at distance greater than (k / 2) + 1 (integer division) and add them to a temporary variable. Now find all nodes that are at a distance exactly equal to k / 2 + 1(say P). We can take at most one node from all such values and therefore add ( P - 1) to our temporary variable. Answer is the minimum of temporary variables value over all vertices.
•  » » 4 years ago, # ^ |   +10 We can take at most one node from all such valuesNo, we can take all nodes in any single subtree of the root. So, you can calculate the maximum of that value. (It's what I did in the contest.)
•  » » » 4 years ago, # ^ |   0 Oh I understood now, thanks!