Блог пользователя rng_58

Автор rng_58, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +137
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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 !

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

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 :(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +60 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        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.

»
8 лет назад, # |
  Проголосовать: нравится +102 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +136 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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.