After quite a pause, I participated in recent Codeforces Global Round 27. After solving A–E in some admissible time but unfortunately struggling for some time with 2035F - Tree Operations, I chose to take the risk and solve the last problem, 2035H - Peak Productivity Forces for which fortunately there was quite much time to sit and figure everything out. Soon it became obvious that it was just a constructive problem without any horrible data structures; one just needs to carefully sort out all cases and not bug a lot. I was very happy to perform it — in these latter days I pretty often feel frustrated that I solve all easy problems (gentleman's set, so to say) but stop at one which is a bit harder, and I seldom am able to solve this one problem (which is usually enough to get a very cool place). Well, today is a nice day!
I explained the problems that I solved right after the screencast itself, you are welcome to watch it: https://youtu.be/WdkTDjb1knw.
UPD: the sound was too quiet, I tried amplifying it: https://youtu.be/jRKJbNO-3kg
unbelievable solving H orz orzorzorzorz
ORZ
do hard problems usually require horrible data structures?
If we talking about the hardest problems, I believe rainboy can answer better, he just starts solving each contest from the hardest problem. From my perspective, not necessarily horrible data structures — but I do believe that in each Div. 1 round the hardest problem require one to have some tricks up their sleeve. These tricks differ from time to time, not always it is an ability to write an awful data structure with some hyper-optimized range queries, Fenwick trees in each point, transfusion from lesser to bigger, etc. (I think the nearest problem to this category that I solved is 1844H - Multiple of Three Cycles where there were not any extremely hard ideas, after some algebraic manipulations one is asked to calculate some function of some sequence of states, and one needs to perform all jumps in $$$n^{2 - |\Omega(1)|}$$$, and it just felt like a disaster to properly organize my code to manage that.) Sometimes it is some knowledge and experience in a topic which is quite rare in contests (as cyclotomic polynomial and its associated vector space — 859G - Circle of Numbers was my first hardest problem of contest that I solved back then when I was blue; afterwards I problemset Universal Cup Season 3 Stage 1 problem onto the same topic which was beautifully described here and here) — actually sometimes the sufficient acquaintance with the topic, ability to speak some mathematical language is enough to solve such a problem fast. Sometimes there is just an idea to a problem which is hard to think of. And, finally, the hardest problem can be just a complex scenario where you have to spend some time to just submerge and start understanding something.
2035H - Peak Productivity Forces is a constructive combinatorial problem about permutations. There were two main ideas — that I needed to apply a $$$(2, 3, \ldots, n, 1)$$$ cycle after each operation so that overall in the permutation $$$\mathcal{O}(1)$$$ elements changed; and that basically every permutation could be decomposed into a product of $$$\mathcal O(n)$$$ transpositions with element $$$n$$$, so probably when this fixed element was rather travelling $$$n \to n - 1 \to n - 2 \to \ldots$$$ instead of staying still, something like this should still have been possible, and when sometimes you had to apply a 3-cycle instead of a transposition, it was still possible. But these two ideas are not very hard, and they were not the main reason why this problem was put onto the hardest place. The main reason was the submersion, commitment part. The contest time is insufficient for practically anybody to just solve all the problems, so when you decide in the middle of the contest to go for the last problem, you practically make a commitment "I will either solve only this last problem or I get nothing". In other scenarios, when you, for instance, continue solving problem F, you don't have to make such a commitment — first of all, it should take so much time, and even if it takes some time and you're still unable to solve it, you can safely switch to problem G and have good chances to solve it. In H, when you spend enough time to understand what is going on in this problem, this is already too late to go back to F, so you just continue down this path — till the end of the problem or till the end of the contest.
Hi, I'm the author of the problem. I was curious if you read the intended solution because from my limited understanding of your solution I think you did something different. I think the intended solution doesn't have any casework and the code was quite easy to write.
In addition, I was wondering if you liked solving it? :)
Hi, at the moment of writing that comment I had just skimmed through the editorial, my impression was that the solution is almost the same. I also do two traverses through the array, one makes the array almost sorted (each element is either at its correct position or at an adjacent position), the second traverse makes it completely sorted.
After a bit more thorough reading, I think the same, but I do think that the devil is in the details. For instance, in your definition of almost sortedness $$$n$$$ should be on the correct position after $$$n + 1$$$ moves. I wasn't able to come up with it, so instead I have the length of the first traverse equal to $$$n$$$ or $$$n - 1$$$ (in the former case, it can be that $$$n$$$ is at $$$(n - 1)^{\text{st}}$$$ position or at $$$n^\text{th}$$$ position; in the latter case, the second traverse starts with element $$$1$$$ and ends also with element $$$1$$$, but the $$$1^\text{st}$$$ element is definitely at its correct position). You can agree that our definitions are very similar, but your one makes it easier to perform the second traverse. For instance, in my solution it was important at the beginning of the second traverse whether the number of pairs out of order had the same parity as the length of the second traverse or the different one — sorry, I can't understand why your solution does not depend much on it, in my paradigm I had to spend extra time to consider that, but in your solution you somehow get that automatically with this cycle:
Also in terms of implementations our solutions differ a little bit in the following way: in your solution you apply the $$$\text{current time} - \text{position}$$$ trick, but this trick is encapsulated in your data structure, outside of it you still use the real indices from the problem. For example, if I wanted to implement the aforementioned
forcycle, the indices would be something like $$$(2n - 2 - i) \bmod n$$$ and $$$n - 1 - i$$$ instead of $$$n - 2$$$ and $$$n - 1$$$. This is because in my case the index shift is not hidden in data structure but is explicitly done, therefore what was an element $$$n - 1$$$ is an element $$$n - 2$$$ after an operation. It is possible that because of that it is harder to implement my solution, I don't know.I liked solving your problem, at the end of the contest I felt nervous (because I got a spontaneous RE 2 and was afraid that I won't get it accepted), but when I finally did it, my first impression was "It was quite nice! I am really surprised that nobody else tried it, why it happened?!" In particular, I probably like constructive problems more than a median person on Codeforces, and also I am keen on combinatorics. So you came up with and prepared a lovely problem, at least for me it is such.
lmao I love your description of such horrendous data structures. To be honest, I'm not exactly sure what most of that is, but I see what you're saying. It is surprising to me that the hardest problems are oftentimes so knowledge-heavy. I would've guessed that they had more to do with IQ / creative insights.
Lol, I am also not exactly sure what most of that is. I think I even have not written a single Mo algorithm in my life. Well, it is always possible that my impression about the distuibution of what can and what cannot be at the last place of a Div. 1 contest is uncalibrated — after all, I haven't seen very lot of these problems. Maybe creative insights are ofter required, but it depends much on what can be called a creative insight (for example, if you have never heard about a treap and invented it during a contest, is it a creative insight?). Also it depends on the style of the contest — if the round is based on some high school student competition or it is Chinese, I expect it more to have an implementation-heavy last problem.
I would even go further and say that the hardness of this problem is induced by the contest format. Unfortunately, there is an incentive to not go for time-consuming problems because they, well, consume a lot of time and therefore are quite dangerous and risky — one basically has to gamble their contest result on a success in one problem. This is quite high-grained — if you solve the problem before the 3h mark, you win, but if you solve it at 3:01, you get absolutely nothing.
Imagine that after three hours the contest does not end, the problems continue to become cheaper until the awards for them vanish completely (in about a couple hours or so). In this case trying the last problem is not such a huge commitment and not such a risk — even if you solve it in 3 hours 10 minutes, you still get some points (and not very few of them!).
So I believe that what makes this problem hard, apart from its own properties, is the other problems that are put along with it in the contest, and the contest format that makes it quite dangerous to try this problem (when there are safer options which still allow you to get even more points).
legend!
a Russian legend*