rng_58's blog

AtCoder Grand Contest 006
By rng_58, history, 8 years ago, In English

AtCoder Grand Contest 006 will be held on Saturday (time). The writer is sugim48.

Note that this time the contest duration is 130 minutes (20 minutes longer than usual).

Contest Link

Contest Announcement

The point values are 200 — 400 — 800 — 1300 — 1500 — 1700.

Let's discuss problems after the contest.

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

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

After the 20 minutes extension, the contest now clashes with Codechef October Lunchtime for 10 minutes.

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

It will be my first time I will take part in an atCoder contest. Can you tell me how difficult is each problem relative to codeforces ? It will be same to div2 or div1 or something between ? Thanks !

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

    It is similar to Div1+Div2 rounds in Codeforces. If you know TopCoder, TC Div1 X points = AtCoder 2X points.

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

It also overlaps for the first 30 minutes with AMPPZ (http://amppz.ii.uni.wroc.pl/harmonogram.html). I guess with so many contests this is inevitable :(

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

    Is this contest popular? Are you interested in participating in this contest?

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

      It's a Polish subregional for ACM ICPC, so all top university students from Poland will be there. However, since it's onsite, I don't think that many of the contestants will be able to compete in AGC even if you decide to shift it.

      It doesn't look like there will be an online mirror, but I might be wrong about that, since there were online mirrors in previous years.

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

        Yes, that's a good point — even if there's no overlap, there are other onsite events that make it hard to compete in AGC.

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

Request "find by name" in standings feature. Friend list even better)
It's really hard to keep track of particular user results now. Or am I missing something?

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

Solution to problem C is really amazing! Thanks for a great contest!

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

Unrelated, but how to change the user id on atcoder?

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

    As far as I know there're no ways to change your used id on AtCoder. (However, you can change your "User name" that is not shown in standings) If it's necessary to change your User ID, you should contact one of AtCoder's admins (e.g. rng_58).

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

I'm really surprised by the solution to problem D which uses binary search. Cool problem.

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

Could you show the number of AC solutions + tags for each task in the contest dashboard. That roughly gives an idea whether I should attempt the problem or not when I am practicing on past contests.

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

    Ya that seems like a good idea. For the time being though, you can achieve this by going to All Submissions -> Filter (Problem = and Verdict = AC) to see how many AC solutions there are.

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

    You can see here: https://agc006.contest.atcoder.jp/statistics

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

      Thanks, but I couldn't see problem tags there. I think it would be helpful if you could filter out problems based on tags on atcoder too because the questions are really great, only this thing is missing.

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

In problem C Rabbit Exercise: what is "exponentiation of a permutation" mentioned in the editorial?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    I haven't seen the editorial, but they're probably talking about composing a permutation with itself multiple times.

    You can read about composition of permutations here.

    Since the operation is associative, you can use binary exponentiation to compose a permutation of length n with itself k times in time. Alternatively, you can look at the disjoint cycle decomposition of the permutation, and then map each element to the element that is its k-successor in its cycle. This will give an O(n) time algorithm.

    If you want to try implementing this separately, you can check out this problem. It's in Icelandic, but the problem basically just asks you to apply that permutation to itself k times. There's also the reverse problem, and a slightly harder variant.

    → Reply