Petr's blog

A red maxflow week
By Petr, history, 5 years ago, In English

https://petr-mitrichev.blogspot.com/2020/01/a-red-maxflow-week.html

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

»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

My TOP3 picks for the problem of the year are the following starting from the best:

1) "Parade". Originally from final of Algorithmic Engagements, but used at some Moscow Workshop contest created from tasks from Algorithmic Engagements. Commonly agreed among our Polish Mafia to be a brilliant problem deserving to be problem of the year without a doubt. Authored by Errichto

2) "Split the Attractions" from IOI. For me it's incredible how all the things work out together there and solving it was super satisfying.

3) "Negative Cycle" — D from AGC 36. Authored by maroonrk https://atcoder.jp/contests/agc036/tasks/agc036_d

And a honorable mention for Honorable mention authoured by 300iq https://contest.yandex.com/newyear2020/contest/16507/problems/67/?success=29623559#7/2019_08_19/EhD3ymqhkc and C2, D, E from World Tour Finals, all authored by rng_58 with some help from yosupo (https://atcoder.jp/contests/wtf19-open)

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

    We agreed in the January 2019, but yea, "Parade" is a good one.

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

    Thanks!

    Just to double-check my Polish skills: in Parade, you are given 300000 distinct points on the plane (not necessarily randomly generated), and need to pick any 500 of them and demonstrate the shortest Hamiltonian path on those 500 points with respect to Euclidean distance?

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

      Oh, apparently we need a Hamiltonian cycle, not a Hamiltonian path.

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

      Hmm, how does the checker for this problem work?

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

        Jako program sprawdzający (checkerkę) organizatorzy napisali bardzo dobre rozwiązanie heurystyczne problemu komiwojażera. Program ten nie jest ograniczony przez limity obowiązujące Ciebie, jak na przykład limit czasu.

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

          Yup, we had a good TSP solver that we ran on 8 threads with bigger time limit. If it finds a better solution on a single test, you get WA. Even if your solution was similarly good to our solver, you likely wouldn't get AC because it would be sometimes worse and sometimes better.

          Btw. I won't be surprised if it's possible to smartly choose points to make it easier for your heuristic solution. My idea was to create 22 groups of 22 points that are close to each other, and assume that points within a group should be visited at once. TSP for 20-25 points can be solved optimally (good heuristics or just $$$O(2^n)$$$ dp). Nobody tried it and for sure it's much easier to solve the problem in the intended way.

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

    I'm sorry, why do you like it so much? If I'm not mistaken, the solution is

    Spoiler

    For me it looks like you in Polish Mafia just overly fascinated by 2nd fact (judging by the fact that there are other problems from The Mafia using the same fact).

    Minuses for me (I got AC in the contest):
    1. 2nd step is just guessing. I know, most of the observations are guessing, and my attitude depends on the problem. This time it wasn't fun.
    2. It is interactive-level impossible to debug, but the problem is not fully constructive, there are places to make bugs.

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

      The idea of Parade's problem statement is more fascinating to me than its solution.

      Put in a similar way, the idea of Negative Cycle's problem statement is nice, but the solution is:

      Spoiler

      and I'm definitely not as fascinated by it as you are :)

      In fact, I found these two problems by maroonrk more enjoyable:

      1. Square Constraints, AGC036 F
      2. Prefix Suffix Addition, AGC040 E

      I do agree that Split is awesome.

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

        I agree that Negative Cycle isn't that exceptional. It's a nice problem with a nice solution, but I could say that about quite a lot of problems in current year + 4, and I didn't go "holy shit this works?!".

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

      How is anything here guessing?

      I like this problem for being natural and unusual. It isn't obvious that you should think about a sequence, there can be many ideas. And the solution indeed doesn't involve any difficult steps, there's nothing wrong with that.

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

        How is anything here guessing?

        It isn't obvious that you should think about a sequence, there can be many ideas

        I'm not saying that problem is bad, I just don't understand why it is "deserving to be problem of the year without a doubt". I have doubts so to say.

        Also I didn't mean that all steps are easy, I just wanted to say something about particular steps, but needed to use spoiler for solutions.

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

          I'm not saying that problem is bad, I just don't understand why it is "deserving to be problem of the year without a doubt". I have doubts so to say.

          Oh, I didn't mean it in an authoritative way, just my/our opinion :)

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

      Well, if you do not like this problem now I don't think I may be able to make you like it, but I will try to explain why somebody may enjoy it and reply to some of your points.

      1) I always appreciate originality and you have to admit that this problem is very original and in a not tedious way like for example Machines on the moon.

      2) As much as I like the original statement I love the solution even more. We are given complete freedom in choosing the set of points and need to wonder "what kind of configurations could help us in solving this problem?". Probably first idea is taking convex sets, but we are not likely to find convex sets of that size (afair happy end theorem gives something like log n?). One of the next possible ideas is monotone sequences (it may come as well with a bit of reverse-engineering bounds since 500 is a bit less than sqrt n) and they play out perfectly with a nice dp. Moreover we do quadratic dp on a sequence of square root size :D. Erdos-Szekeres pops in an a priori unrelated plane TSP problem and I really like that connection. It's kind of guessing but an educated guessing as well and seeing how the pieces fit together was super satisfying to me.

      I don't think we are overly fascinated by Erdos-Szekeres theorem. It's true that it was second problem taking advantage of it, but they were independently developed. First one was E from Hello 2019 by Radewoosh. On one side it was nice from the mathematical point of view, but got no surprise factor. And I and Marcin_smu were definitely on your side in the argument "Fuck you and your limitations Radewoosh" xD. In the parade the connection was a priori completely unexpected. However it is true that we got headstart during PA/AE finals thanks to Hello problem reminding us of that fact just two weeks earlier.

      → Reply