rng_58's blog

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

AtCoder Grand Contest 011 will be held on Sunday (time). The writer is semiexp.

Contest Link

Contest Announcement

The point values are 300 — 400 — 800 — 900 — 1300 — 1700 (?).

Let's discuss problems after the contest.

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

Comments Comments (21)
| Write comment?
»
8 years ago, # |
  Vote: I like it +68 Vote: I do not like it

Meh, overlaps with Deadline24 quals by just one hour :(

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

    Hmm, I didn't care much about the collision of marathon contest and algorithm contest, but it seems it affected the international participants a lot. We'll avoid the collision in the future.

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

Contest starts in under three hours.

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

Nice contest!

There's no editorial yet, how to solve D?

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

    1. Observe that if the first character of S is A then it becomes B, otherwise everything flip, and we delete the first element, and add a 'A' at the end.

    2. Convince yourself that the sequence becomes more or less static very fast.

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

    Uploaded.

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

      where is the editorial uploaded? can you share the link please?

      Edit: Found the editorial

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

Gonna like atcoder's contests. The problems were non-obvious(at least C and D, didn't read E and F), it was hard for me to find the solution instantly.

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

B reminds Fish from IOI'08 a bit

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

Can someone please explain how to do C ??? The editorial is may be according to me a bit complex ....

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

    The point is that the contribution of each and every two connected component differs by whether it is a bipartite graph. Leave the single point alone, in a single connected component, you can color the graph with black & white (two side of each edge have different colors). If possible, pair (black, white) will attach to a (white, black) with an edge, and it cannot connect with point like pair (white, white) and (black, black).

    Likewise, you can use similar way to calculate the contribution of two distinct connected components.

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

What was the intended difficulty of the problems in terms of top coder point values?

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

    2X points at Atcoder = X points at Topcoder Div1

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

      Thanks, I thought so. However I wondered if D was really 450 on tc.

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

Seams that E is easier than D and F. 500 points F suddenly got to be almost the whole solution. :(

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

    I think if you get (or somehow already know) the reunity number fact it's much easier to proceed, but without that D is definitely easier than E.

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

      could you please tell me what is the fact?!

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

    Yes, I agree that F's partial score is much harder than 500 points, but it's somewhat difficult to give partial points. For example, if we give 1200 points for it, the difference between the full score and the partial score is also much bigger than 500 points.

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

In E, Increasing Numbers, we need to check if r_1,r_2,...r_9k exist. We check it by checking if sum of digits of decimal representation of 9N+9k is "at most" 9k. But how does it guarantee it can be written in exactly 9k powers of 10?

For example: 1 can only be written in just 1 power of 10 i.e. 0 but not 9 powers of 10.

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

    If you can represent n as sum of k powers of 10 then you can do it also using k+9 powers of 10 (if that's not greater than n). Moreover 9n+9k is divisible by 9, so its sum of digits is also divisible by 9.

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

The editorial for C says "there is an edge between (a, b) and (a', b') iff there exists a path of length l between a and a' and a pathbof length l between b and b'". Isn't it supposed to be path between (a, b) and (a', b')?

→ Reply