### ikatanic's blog

By ikatanic, history, 4 years ago,

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!

• +72

 » 4 years ago, # |   +25 How many teams passed to World Final?
•  » » 4 years ago, # ^ |   0 I don't have any official information. But seems like at least 4 teams will advance to finals.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 where it will take place please :D I mean the mirror
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   +10 Seems like there is already some official preliminary information: https://icpc.baylor.edu/worldfinals/teams
 » 4 years ago, # |   +64 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 :'(
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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!
•  » » » 4 years ago, # ^ |   +41 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.
 » 4 years ago, # |   +10 How to solve E?
•  » » 4 years ago, # ^ |   +30 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 c with k(a + b) - c and get another solution (similarly for a and b). This way we can run BFS over the triples until we have enough to output. Simple set is enough to check for duplicates.
 » 4 years ago, # |   +28 How to solve B?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Let's consider some good subset V, i.e. subset of vertices that can be covered by some matching, L and R are subset of vertices in V from left side and right side of graph respectively. Then it can be easily seen that L and R are also good subsets. So let's find all good subsets of left side and right side independently. neighbour(S) is the subset of vertices which are neighbours to some of vertex in S. Now just iterate over all 2n different subsets in left side and check that subset. Using Hall's theorem.After finding two list of good subsets just find number of pairs with sum  ≥ t using two pointers or binary search. Overall complexity: O(n * 2n).P.S: How fast is the solution with iterating over all subsets and then trying Kuhn?
•  » » » 4 years ago, # ^ |   +18 We can copy for each subset matching of its smaller subset and run one iteration of Kuhn. It works in O(2n·n2), passed in 921ms.
•  » » » 4 years ago, # ^ |   0 I think you got it wrong way. It should be:If L and R are 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.
 » 4 years ago, # |   +45
•  » » 4 years ago, # ^ |   0 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(2n·n). So overallcomplexity is something like O(2n·(n2·digits + n·2n))Will it also work or I am missing something?
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   0 While trying to explain what I mean, I got what the problem is. After reversing left hint doesn't become right hint. Thanks
•  » » 4 years ago, # ^ |   +30 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 not hard :(In the meantime, guys, I think that was one of the best rounds this season! Thanks so much for the great problems!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +29 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.
•  » » » 4 years ago, # ^ |   0 I solved D the day after the contest and was embarrassed how easy it is.
•  » » » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # | ← Rev. 2 →   0 How to solve H and K? (div1)
•  » » 4 years ago, # ^ |   +13 Editorial. K on page 5, H on page 49.
 » 4 years ago, # |   +5 Thanks, added it to the Gym: 2016-2017 ACM-ICPC, Central Europe Regional Contest (CERC 16) (currently with opencup parsed ranklist, because can't parse the official)