rng_58's blog

By rng_58, history, 8 years ago, In English

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.

  • Vote: I like it
  • +118
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
8 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

sorry i can't find the blue button to register!

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can I view leaderboard without logging in/registering?

»
8 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Awesome Contest !! Btw, how to solve C ?

EDIT: Super Fast Editorial Thanks!

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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/809066

      Thanks in advance .

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    Here is my code.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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]);
    
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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.

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Nice problems. How to solve D,E?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    E: Since ai, bi are small, you can find all pairs (ai + aj, bi + bj) using a 2D FFT. Maybe also 2D Karatsuba. Then, you just need the sum of binomial coefficients over all pairs.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      This FFT would take operations, isn't that too much?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can the C be done in O(n)?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    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?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Solved E in O(NC). Looks like it wasn't intended.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Really? My solution had just 2NC additions and didn't pass.

»
8 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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!

»
8 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah,it will be fine,but not with subtasks like ioi where O(N) and must have different scores.

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +48 Vote: I do not like it

    Initially we were planning to give partial score for O(n2) in F, but it turned out that the following stupid solution passes:

    while(1){
        updated = false;
        for(i=0;i<N;i++) for(j=0;j<N;j++){
            if(j minus i >= K && P[i] minus P[j] == 1){
                swap(P[i], P[j]);
                updated = true;
            }
        }
        if(!updated) break;
    }
    
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +31 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

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

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +33 Vote: I do not like 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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +57 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        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:

        • 26xx ~ 27xx 4d
        • 28xx ~ 29xx 5d
        • 30xx ~ 31xx 6d
        • 32xx ~ 33xx 7d?
        • 34xx ~ 35xx 8d?
        • 36xx ~ 37xx 9d?
        • 38xx ~ 39xx what will this be?
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Thank you for explanation. It sounds interesting system.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        You say f(1)=866, but after recent "fix", I see f(1)=1200. Which is correct actually?

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    We can take at most one node from all such values

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