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.**

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).sorry i can't find the blue button to register!

Go to http://agc001.contest.atcoder.jp/ and find https://gyazo.com/67c50bea10006acb6303db01a7df413f.

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! :)

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 ;)

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

How does the contest difficulty compare to a codeforces div1 or div2 regular round?

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).Can I view leaderboard without logging in/registering?

Awesome Contest !! Btw, how to solve C ?

EDIT:Super Fast Editorial Thanks!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 isO(n^{2}).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 thanKcount those Nodes.Again I ran a BFS and find the distances of other Nodes from

V. If any Node's distance is greater thanKcount 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/809066

Thanks in advance .

10 2

1 2

1 3

1 4

1 5

1 6

1 7

1 8

2 9

3 10

The answer is 2 (delete 9 and 10). You will print 7.

If I correctly understand your solution.

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 subtreei, such that the height of the tree is exactlyjand the diameter of the resulting subtree will be at mostK. Letsdenote the son ofi.(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 heightj- 1, and then the rest of the children need to be both not deeper and not give a diameter bigger thanKin 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.

Here is my code.

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. :)

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:

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.

Nice problems. How to solve D,E?

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.This FFT would take operations, isn't that too much?

Maybe, hard to say. I've squeezed through worse things.

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.

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.

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).Can the C be done in O(n)?

Yes, instead of checking for every vertex(

xin 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?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.

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.

You can add (or subtract) not just one vertex, but all vertices of the required depth in one whole subtree.

Solved E in

O(NC). Looks like it wasn't intended.Really? My solution had just 2

NCadditions and didn't pass.http://pastebin.com/PfuS8CZY

~1.5 sec

P.S. There is "Custom Test" tab. Maxtest is obvious so you don't need to submit to get TL.

Oh, thanks, I didn't notice this tab.

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!

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).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).

Judge runs on all tests and sorts them in the order of verdict.

Yes, we'll try to implement this in the future.

Thank you snuke, rng_58 (and other who prepared it) for the contest! My thoughts:

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.

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.

Yeah,it will be fine,but not with subtasks like ioi where

O(N) and must have different scores.Initially we were planning to give partial score for

O(n^{2}) in F, but it turned out that the following stupid solution passes:Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).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.:)

No, that should be a bug. We'll look into it.

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.

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.

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.

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 toX. This means that whenXis lower than the initial rating, your rating will gradually decrease. In order to avoid that, in AtCoder's rating system,Rating= (weighted average ofPerformance) —f(# of competitions)where

f(1) = 866 andf(∞) = 0.This means that if you keep getting the performance of

X, your rating starts fromX- 866 and then gradually converges toX.The function

fwas 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.

Wow, this system is fun, I got 3000+ in one day. :P

And I noticed "6 Dan" in my profile? Is that something depends on rating? Seems we have:

Thank you for explanation. It sounds interesting system.

You say

`f(1)=866`

, but after recent "fix", I see`f(1)=1200`

. Which is correct actually?Now 1200 is correct (the old system was indeed too aggressive as ir5 pointed out). We'll publish the rating formula within a week.

If possible, I want to see the rating formula. Where is it?

Why does the following fail in

Cwhenkis 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(sayP). 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.

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.)

Oh I understood now, thanks!