Блог пользователя ikatanic

Автор ikatanic, история, 8 лет назад, По-английски

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
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

How many teams passed to World Final?

»
8 лет назад, # |
  Проголосовать: нравится +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 :'(

  • »
    »
    8 лет назад, # ^ |
    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!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve E?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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.

»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

How to solve B?

  • »
    »
    8 лет назад, # ^ |
    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?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 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.

»
8 лет назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 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?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        Thanks

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +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!

    • »
      »
      »
      8 лет назад, # ^ |
      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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve H and K? (div1)

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Thanks, added it to the Gym: