rng_58's blog

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

AtCoder Grand Contest 005 will be held on Saturday (time). The writer is yosupo.

Contest Link

Contest Announcement

Let's discuss problems after the contest.

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

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

Never mind. I was wrong.

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

It clashes with the ICPC Preparatory Series contest on Codechef. :(

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

I am really interested why all in top 10 are reds except semiexp whose color is green?Is it a bug?

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

    Actually his color is #92D050. If you reach 3200, you can choose your own color (tourist and Petr haven't decided their colors though).

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

I hate FFT :( the modulo is friendly though

Anyway, nice problems!

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

The best thing about AtCoder is trying to read the Japanese editorial using Google Translate.

Edit: My bad, I see the English version now.

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

    There's English editorial below Japanese editorial.

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

      It would be much better to provide editorials in English and Japanese in separate file. I don't like seeing Japanese editorial at the top. Can something be done in this regards? Anyways, Thanks for great contests and well explained editorials.

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

Can someone explain the solution for D better? I'm lost at the Inclusion-Exclusion part (where did the sum come from)

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

Can someone please explain the editorial of D in a different way? I'm having some difficulty understanding it. How is that formula derived? And how to find M(k) in O(n^2) using DP?

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

Sorry for necroposting, but how to solve D in time?

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

    I think all you do is: notice that the only part of the editorial that needs O(N2) time is computing the Mk. You can compute all Mk for a single path of length l by straightforward combinatorics / dp.

    Let Pl(x) be the polynomial where the coefficient of xk is the number of matchings of size k on a path of size l. Notice that in the graph, all paths are gonna be length l or l + 1 for some l (). To find the overall Mk, this is equivalent to a convolution so you can just compute Pl(x) and Pl + 1(x) for the appropriate l and then raise them to the correct power and multiply. This can all be done by FFT in ,

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

      How do we compute Pl(x) in time?

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

        Say you have a path of length l. You want to pick k of the edges so that you don't pick any two adjacent edges. This is just a binomial coefficient, something like or something.

        → Reply