rng_58's blog

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

AtCoder Grand Contest 007 will be held on Saturday (time). The writer is dreamoon_love_AA.

Contest Link

Contest Announcement

The point values are 200 — 400 — 1000 — 1200 (600) — 1400 — 1500.

Let's discuss problems after the contest.

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

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

dreamoon? Isn't the writer dreamoon_love_AA on Codeforces?

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

    dreamoon was his old name if i remember correctly. It's quite confusing.

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

      Yes, I also think it's quite confusing. I want to change it back next year....

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

Does it support virtual participation?

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

Just curious, will we have contests start at different time?

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

    It seems this is the only slot that is good for both Japan and Europe, so I think all future AGC/ARC will be in this slot. However, some tournament rounds may be held at different time.

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

Great contest, good problems!

A couple of features for the website I would like to propose though: 1) Make it visible which tasks you solved on the "Tasks" page 2) Maybe a chat or comments system so participants can talk after the contest? Since the editorial is in Japanese and I would like to know how to solve the last 2 tasks..

Well done, though, great job!

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

After receiving a WA on D, debugging for a long time, I found out that using "%I64d" to print a long long will get a WA.:( Isn't there any statements about this?

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

    Please email us your handle. We'll change your result for this contest.

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

Feature request: Add option for viewing country standings.

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

Thank you for requests, we are currently busy with CODE FESTIVAL but we'll implement some of them in the future.

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

Can any one please explain solution of C? The editorial is too short to get the full idea. Thanks.

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

    In the original problem the distances were one (so the input takes only one integer N), but it turned out that this version can be solved with OEIS and thus we had to change it to arithmetic sequences.

    For example, suppose that N = 3 and the distances are (1, 1, 1, 1, 1, 1). Let f(1, 1, 1, 1, 1, 1) be the answer of the problem in this case.

    As there are three balls, there are six possibilities in the first step. In the first step, the chosen ball always move by the distance of 1. After this step, the "state" of the balls and holes will be one of the following: (1, 1, 1, 1), (3, 1, 1, 1), (1, 3, 1, 1), (1, 1, 3, 1), (1, 1, 1, 3), (1, 1, 1, 1). The "average" of theses state is (4 / 3, 4 / 3, 4 / 3, 4 / 3). Thus, we get

    f(1, 1, 1, 1, 1, 1) = 1 + f(4 / 3, 4 / 3, 4 / 3, 4 / 3).

    We can prove that when the state is an arithmetic sequence, the expected state after the next step is also an arithmetic sequence. The remaining part is easy I think.

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

      But, if we call the answer g(N, d1, x), you can show that g(N, d1, x) = g(N, d1 + (N - 1 / 2)x, 0) = (d1 + (N - 1 / 2)x)g(N, 1, 0), so it still translates to the problem with all distances one.

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

        Because of that properties, C was still solvable with OEIS. Not what I've tried, but I know someone who got AC with that.

        With brute force we can notice answer = x * f(n) + d1 * g(n), so we can search for f(n) and g(n), which results in something related to http://oeis.org/A001705

        Still, I loved all rest of problems!

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

      My solution doesn't use arthimetic property. For a segment, I compute expected number of ball rolls over. For example, if there are k balls before this segment. Then expected number of ball before rolls over is: .

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

        I know it's been a long while since you've written this comment, but would you mind explaining how you ended up with that formula? In the contest I've tried computing the same thing but I was unable to do it and I thought a lot about it. I think it would be very useful to me to find out how to do it (as this was the way I tried to think it, so this is the path I would have chosen if I were able to finish the reasoning, rather than changing my whole perspective to solve it the same way as them).

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

          For a ball and a segment, you should calculate the probability of the ball rolls over the segment. It relies on balls between them and other ball at opposite side.

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

really desire the english solution :)

anyway, atcoder is very good to me.

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

    The english editorial is below the Japanese editorial

    → Reply