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

Let's discuss problems after the contest.

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

1 | Petr | 3325 |

2 | Um_nik | 3284 |

3 | Syloviaely | 3258 |

4 | tourist | 3206 |

5 | anta | 3106 |

6 | fateice | 3099 |

7 | mnbvmar | 3096 |

8 | OO0OOO00O0OOO0O0…O | 3083 |

9 | Radewoosh | 3076 |

10 | HYPERHYPERHYPERC…R | 3071 |

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

1 | tourist | 183 |

2 | rng_58 | 169 |

3 | csacademy | 162 |

4 | Petr | 158 |

5 | Swistakk | 152 |

5 | lewin | 152 |

7 | matthew99 | 146 |

8 | Errichto | 142 |

9 | Zlobober | 141 |

10 | BledDest | 140 |

10 | adamant | 140 |

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: Mar/22/2018 11:17:03 (d2).

Desktop version, switch to mobile version.

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