Hello everyone,

on Sunday GP of Europe will take place. It's a mirror of CERC contest, hope you like it.

Let's discuss the problems here after the contest!

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

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

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

1 | Errichto | 202 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 185 |

5 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

Hello everyone,

on Sunday GP of Europe will take place. It's a mirror of CERC contest, hope you like it.

Let's discuss the problems here after the contest!

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2020 02:53:56 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How many teams passed to World Final?

I don't have any official information. But seems like at least 4 teams will advance to finals.

where it will take place please :D I mean the mirror

Mirror will be one of the round of Opencup Grand Prix. You need to contact with snarknews. Anyway, usually they upload problemset/solutions/tests and someone will add to Codeforces Gym.

Seems like there is already some official preliminary information: https://icpc.baylor.edu/worldfinals/teams

Huh, second year in a row we thought we did some great job on CERC, but second year in a row Russian teams are making us aware we didn't :'(

What's the problem? One team on-site got 10 and one in opencup got 11, and all 3 difficult problems were kinda solvable :) You did good!

Haha, I am aware our result is far from being very bad, but I didn't expect any team to solve 11 problems, that is kinda amazing. Moreover ITMO got much better time even though we thought we were pretty fast — well deserved win for them :). Looking forward to Petrozavodsk to compete against all Russian squad ;p.

How to solve E?

First, triple

`{0, 1, k}`

is a solution (but we don't output it because of 0).If we have a solution, we can replace

cwithk(a+b) -cand get another solution (similarly foraandb).This way we can run BFS over the triples until we have enough to output. Simple set is enough to check for duplicates.

How to solve B?

Let's consider some

good subsetV, i.e. subset of vertices that can be covered by some matching,LandRare subset of vertices inVfrom left side and right side of graph respectively. Then it can be easily seen thatLandRare alsogood subsets. So let's find allgood subsetsof left side and right side independently.neighbour(S) is the subset of vertices which are neighbours to some of vertex inS. Now just iterate over all 2^{ n}different subsets in left side and check that subset. Using Hall's theorem.After finding two list of

good subsetsjust find number of pairs with sum ≥tusing two pointers or binary search. Overall complexity:O(n* 2^{ n}).P.S: How fast is the solution with iterating over all subsets and then trying Kuhn?

We can copy for each subset matching of its smaller subset and run one iteration of Kuhn. It works in

O(2^{ n}·n^{2}), passed in 921ms.I think you got it wrong way. It should be:

If

LandRare good subsets, from left side and right side of graph respectively, then it can be (although not easily anymore) seen that is also a good subset.Solution sketches (by kalinov): https://dl.dropboxusercontent.com/u/1909330/CERC%202016-%20Presentation%20of%20solutions.pdf

In I thought about a bit easier solution: iterate over bitmask of whether each hist is LTR or RTL, reverse if necessary. Then precalculate for each pair of hints transition cost, and then run your solution for one-sided hints in

O(2^{ n}·n). So overallcomplexity is something likeO(2^{ n}·(n^{2}·digits+n·2^{ n}))Will it also work or I am missing something?

What is a transition cost between hints going left and right? I don't get overall idea of your solution, either description is too concise or you made some oversimplification.

While trying to explain what I mean, I got what the problem is. After reversing left hint doesn't become right hint.

Thanks

I could not believe my eyes when saw D marked as

medium! Also sad we didn't solve B, because I misread it, but I think that was also nothard:(In the meantime, guys, I think that was one of the best rounds this season! Thanks so much for the great problems!

These easy, medium, hard labels are just my own predictions that I made before the contest began based on my hunch, and based on how much trouble the problem gives to other problemsetters in our small team.

Once you get very familiar with a problem, it's sometimes hard to put yourself in competitors' head and imagine that you just read the problem for the first time and have to come up with a solution.

Still, thanks for the kind words! I'm glad you liked our problems.

I solved D the day after the contest and was embarrassed how easy it is.

I had the same feeling about B actually :( Solved in the car on the way home when read the statements correctly.

In D we tried to divide the permutation into increasing/decreasing subsequences and use different routes to transport them. Probably stuck into that idea to much.

How to solve H and K? (div1)

Editorial. K on page 5, H on page 49.

Thanks, added it to the Gym: