ICPC 2019-2020 was a weird season. During a covid pandemic, with finals in 2021, in Moscow, with PCR tests, visa problems, and ubiquitous scheduling mess. But finally, on the 5th October 2021, the Grand Finale was about to begin.

We started the 15-problem contest with David reading from A, Maja reading from O backwards, and me typing the template (in order to speed up the quickest accept, the hashing tool and .bashrc in which we had the compile command and the testing script. We didn't see any trivial problems.

Meanwhile, Maja invented M and David A, and they started coding them. First blood appeared on C, D, E, G.

C was a geometrical task which seemed nontrivial, and I couldn't figure out how to solve D or G. Initially I thought G was trivial, but I did not see that one thing is not given in the input and I switched back to some other task.

After some team accepted E it became obvious to me that this problem with many different kinds of queries in the statement is actually not too hard. So I started working on it.

Meanwhile, David got an accept on A in [27] minute of the contest. That also happened to be a 'first to solve' on this problem, for which we won 1500$. Though it wasn't particularly impressive, MIT needed 26 minutes to solve four tasks...

Maja got some WA on M and proceeded to write a checker for it. It was a good idea, because it helped to discover some flaw in the solution. After a couple minutes, the stresstests were passing, and... she got another WA.

My quest to solve E finally ended in [55] minute with zero wrong attempts. It involved some formulas and by the time I managed to get all the details correctly, some time has passed and the top teams were wiping the floor with us.

David managed to conquer D in [65] minute as well, despite not being sure about how to solve it for a while, too. He overcomplicated the solution a little bit, because he didn't know that our library contained a snippet of great usefulness in this task.

Around [70] minute, Maja realized that she should have stresstested on larger cases, and discovered a bug. She forgot some corner case in her solution. This definitely shouldn't have been the first problem attempted... But it finally got through in [85] minute after [3] bombs.

Problem O had some geometrical statement, so I was reluctant to take a look at it despite a couple of teams solving it. Though it posed no problem to David at all. We parallelized the implementation of this task — he was getting the details while I was typing some part of the library. Synchronizing our staff worked quickly and after roughly 15 minutes... we got a WA. We were quite clueless about this, because there was not much that could be wrong in this task. The edit distance from the correct solution turned out to be several characters — some float rounding was incorrect, I am not even sure why. Two minutes after Maja's accept on M, at [87], we got a 'correct' verdict after one wrong try. Solving 2 problems in a short timeframe allowed us to jump quickly into the medal zone. We were still behind top teams, but at least not that much.

However, because all teammates were involved in solving those two problems, we now had to start the new wave of problems with 0 insights. G, C seemed doable because quite a few teams got it, and first blood happened in the first 20 minutes of the contest. Those two were of completely different flavour. C was a rather pleasant geometry problem where Jury tried to be nice by allowing poor precision and giving slightly low constraints. We had the important components for it in the library, but it would still take us some time. A while before I also read F and noticed it was some past ONTAK problem which Maja solved onsite. However, it was a kind of problem in which solving the thing in the past didn't particularly help in getting another AC, so we decided not to solve it immediately.

G took a team effort to solve, we didn't know initially how to do it. David and Maja suggested using a 2D-segment tree to compute maximums, but I strongly objected and said there must be a simpler solution. Plus, we also didn't have it in the library so it would take us some time, and we wouldn't even know if it would fit in time... Telling a rather unhappy 2900-rated guy that his idea is bad definitely takes some courage... Later we found out that Petr and tourist also thought of a 2D segtree.

Finally, Maja exclaimed in awe after a while of thinking that she knows how to do it. 15 minutes later we were happy with an accept. This was our 6th problem solved in [124] minute.

In the meantime I took a look at problem J which featured some tree and paths. I had some outlines for a bogus solution, but wanted David to look at it before coding stupid shit, so I interrupted his coding of C. He said my solution is wrong, but we quickly came up with another solution together. I confidently said I can implement it quickly, because I remembered a very nice trick to simplify implementation which I last used in like 2017. David said I'm likely to spend some time on it, but approved my solution (and the simplification trick as well).

My coding of 120 lines finished around 20 minutes later. Passed samples quickly after compilation. I recalled that coding a similar thing in highschool took me like 2 hours and I was very proud of myself... and of that bomb we just got. We went through my code and thought it contained no bugs... but we found out one overlooked case for the optimal solution. Well.. not one but two; however the powerful trick could handle the implementation of the new cases easily as well, and after adding 30 more lines in [173] minute we got J, our 7th problem solved.

After doing G, Maja had some fun on the geometrical problem F. (actually, C, F and J were being coded at the same time). She would eventually finish coding just to get a bomb... and then another bomb... David got a bomb and another bomb on C as well. Despite the fact that we still were in the medal zone, things were not looking particularly promising, as there wasn't even a good way to write a bruteforce checker for those problems.

Despite being a geomertical potato, I tried to help them once I finished J, because I knew that their problem-solving skills are absolutely crucial at the final stage of the contest. We would really benefit from solving more problems, because our penalty was not particularly good. I also tried to solve B, but couldn't figure out a good way to do it, and all my ideas were very complicated.

As I couldn't see a way to progress in B, I asked Maja to explain her F solution to me. I was a very useful rubber duck, because while explaining, Maja immediately realized that she should've used the arcsin function rather than arctan in some place. I didn't know how I helped, but it helped. I was wondering why it even passed samples... Our 8th accept in [202] minute after [5] bombs finally arrived.

Once our powerful mind was free from the burden of debugging, I decided to continue maximizing our chances to get problems accepted. I tried to help David somehow, but asking some stupid questions didn't work out this time. At that time 5+ teams solved B already, and I was very confident that Maja will be able to get this. My processor went into a branch-prediction state and I decided Maja will need a bruteforce checker at some point. Once she was reading the task, I started writing the testing script, the test generator and an exponential solution. This was another problem in which stresstesting was not trivial, so I had to think for a while about how to actually do this nicely. Good test generation was not so simple either, and I was afraid that random testcases may not catch all possible bugs in the solution. My work was finished roughly 5-7 minutes before Maja's code successfully passed the samples. Alas, it did not pass the stresstest!

In the meantime, David got an accept on C after realizing that our library actually had a bug in one of the codes he used. Well, not exactly a bug, just an awful thing. One of the functions was templated on arbitrary type , but actually worked correctly only for integer T, whereas for long doubles it only seemed to work — was comparing floating-point values without a proper epsilon. And there wasn't even any comment about this!!! After the contest one team which forked our fork of kactl came to us and told us they also suffered from the same issue. Anyway, with 9th problem solved in [221] minute after [2] bombs we were now confident that we were capable of getting a medal-winning performance.

ITMO solved problem I roughly 3 hours into the contest, and it was the only other (than B) task solved by any team at that time. H, K, L, N remained unsolved and in some cases even unattempted. David asked us if we need help with B, but Maja expressed high confidence in her solution, and we were already equipped with a bruteforce checker, so David took a look at I. He put his 2900-hat on and went to the toilet. After around 10 minutes, he came back and said he knows how to do it.

Maja got RunTimeError on B in the meantime, despite her stresstests passing. I thought of possible corner cases, looked at the 'return *min_element(all(vec))' snippet, and asked if vec could possibly be empty. It turned out to be the case on some small graphs. Maja fixed it quickly, but this did not remove the RTE verdict. Bomb number two! Was she playing a game of bomberman today? In the meantime I pointed out several things which would not manifest on stresstests, like incorrect (too small) initialization variable (later David pointed out too large initialization variable as well xD), or an overflow possibility. It was provable that max possible answer was 2*10^9, but I was afraid that some intermediate computation would overflow, and insisted on changing to long longs. Initially we thought that RTE might be caused by changing int main() to int32_t main() and some weird behaviour on the judge, but this didn't really do anything bad.

When there was an hour remaining, the scoreboard was frozen. We were ranked 7th and our position on the scoreboard wouldn't change until the head of judges starts the revealer at the closing ceremony. The penalty wasn't great, but other teams did have some troubles too. By consistently solving harder problems we caught up with the medal zone teams. Though at that time some quicker teams like Uni of Bucharest were still wiping the floor wtih us.

David came back from the toilet, coded the solution to I quickly and realized it doesn't actually pass sample 1. After the contest he told me that he had almost given up at that point... but fortunately he realized that modifying a very tiny detail in his existing approach made the solution provably correct. He submitted it, and gained a precious 10th accept in [251] minute. We suspected this was a medal-winning performance, even though we wouldn't know how other teams are doing because of the frozen scoreboard. Later we learned that problem I alone wouldn't have been sufficient to win a silver medal, but even without both B,I we would still be in top12.

Other problems looked unsolvable, but we still had one more accept to get. RTE on B refused to turn into an AC verdict. And then David pointed out the hard truth roughly 20-25 minutes before the end of the contest: this might be a stack overflow problem. All problems had 2GB memory limit so we didn't expect memory issues. However, it turned out Maja's solution initialized vectors in a way which for an unlucky case had O(N^2) memory complexity. N^2. Long longs. N=20.000. This is not a good combo. The crucial battle with time began. David copied the code for B and tried to optimize LL vectors into globally allocated int arrays, in hope that this will be sufficient. Maja instead once again proved her 300iq-ness. She maintained composure and quickly reorganized a part of her code to compute some helper functions earlier, which could allow moving allocations to a different place, which reduced our algorithm's working set size. Submit 10 minutes before the end of the contest... another RTE! But this time it was actually an incorrect fix, and the RTE manifested even on samples. Though it was not a problem to our hero. In the calmest way possible, she announced 'I know', and changed some thing we could not understand. And finally, the 11th problem solved by us arrived in [295] minute, a few minutes before the end of the contest. It took an intense team effort to solve it. Had I not convinced Maja than N^2 will for sure be quick enough and implemented a bruteforce checker, we wouldn't probably manage to fix the correctness bugs quickly (plus, I contributed on the first RTE bug, too). Had David not pointed out memory issues despite 2GB memory, we would have been too slow in resolving them. Had Maja not been such a cold-blooded hero, we wouldn't get this problem either.

Despite a poor start we had no regrets, only the feeling of pride arising from the best result for Cambridge ever, and the best result of participants from NorthWestern Europe in like 20 years or so.

Funny we barely advanced at the NWERC qualifiers in November 2019 because David did some impressive carry in the last hour...