ikatanic's blog

Opencup GP of Europe

By ikatanic, history, 8 years ago, In English

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!

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

»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

How many teams passed to World Final?

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

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 :'(

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

    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!

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

      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.

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

How to solve E?

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

    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.

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

How to solve B?

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

    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?

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

      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.

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

      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.

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

Solution sketches (by kalinov): https://dl.dropboxusercontent.com/u/1909330/CERC%202016-%20Presentation%20of%20solutions.pdf

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

    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?

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

      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.

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

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

        Thanks

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

    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!

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

      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.

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

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

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

        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.

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

How to solve H and K? (div1)

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

Thanks, added it to the Gym:

→ Reply