### Petr's blog

By Petr, history, 10 months ago,

• +63

 » 10 months ago, # |   +51 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 Errichto2) "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_dAnd 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)
•  » » 10 months ago, # ^ |   +24 We agreed in the January 2019, but yea, "Parade" is a good one.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +19 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?
•  » » » 10 months ago, # ^ |   +20 Oh, apparently we need a Hamiltonian cycle, not a Hamiltonian path.
•  » » » 10 months ago, # ^ |   +18 Hmm, how does the checker for this problem work?
•  » » » » 10 months ago, # ^ |   +38 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.
•  » » » » » 10 months ago, # ^ |   +21 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.
•  » » 10 months ago, # ^ |   +43 I'm sorry, why do you like it so much? If I'm not mistaken, the solution is Spoiler $500^{2} < 300000$ there is increasing or decreasing subsequence of size $\sqrt{n}$ we can solve Hamiltonian cycle on monotone sequence 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.
•  » » » 10 months ago, # ^ |   +49 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 no negative cycles $\Leftrightarrow$ a potential function exists edge weights are very small potentials are non-increasing $\Rightarrow$ use DP to allocate them and I'm definitely not as fascinated by it as you are :) In fact, I found these two problems by maroonrk more enjoyable: Square Constraints, AGC036 F Prefix Suffix Addition, AGC040 E I do agree that Split is awesome.
•  » » » » 10 months ago, # ^ |   0 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?!".
•  » » » 10 months ago, # ^ |   +2 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.
•  » » » » 10 months ago, # ^ |   0 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.
•  » » » » » 10 months ago, # ^ |   +1 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 :)