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

Let's discuss problems after the contest.

Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

# | User | Rating |
---|---|---|

1 | Radewoosh | 3443 |

2 | tourist | 3372 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | ksun48 | 3176 |

5 | scott_wu | 3168 |

6 | CongLingDanPaiSh…5 | 3157 |

7 | Benq | 3154 |

8 | Petr | 3139 |

9 | Um_nik | 3138 |

10 | LHiC | 3118 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 195 |

2 | Errichto | 175 |

3 | rng_58 | 157 |

3 | Ashishgup | 157 |

5 | neal | 156 |

6 | tourist | 154 |

7 | Petr | 151 |

7 | PikMike | 151 |

9 | Um_nik | 149 |

10 | kostka | 147 |

10 | Vovuh | 147 |

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

Let's discuss problems after the contest.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 19:04:29 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Never mind. I was wrong.

Actually it seems like there's a 15 minutes break between the contest.

rng_58 likes your icon, according to this comment.

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

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

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

I hate FFT :( the modulo is friendly though

Anyway, nice problems!

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

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

There's English editorial below Japanese editorial.

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.Can someone explain the solution for D better? I'm lost at the Inclusion-Exclusion part (where did the sum come from)

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?

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

I think all you do is: notice that the only part of the editorial that needs

O(N^{2}) time is computing theM_{k}. You can compute allM_{k}for a single path of lengthlby straightforward combinatorics / dp.Let

P_{l}(x) be the polynomial where the coefficient ofx^{k}is the number of matchings of sizekon a path of sizel. Notice that in the graph, all paths are gonna be lengthlorl+ 1 for somel(). To find the overallM_{k}, this is equivalent to a convolution so you can just computeP_{l}(x) andP_{l + 1}(x) for the appropriateland then raise them to the correct power and multiply. This can all be done by FFT in ,How do we compute

P_{l}(x) in time?Say you have a path of length

l. You want to pickkof the edges so that you don't pick any two adjacent edges. This is just a binomial coefficient, something like or something.Oh, you are right. Thanks :)