A pseudobubble week

Last week's contests were all concentrated on the weekend. Codeforces Round 758 took place early on Saturday (problems, results, top 5 on the left, analysis). The round seems to have been downvoted into oblivion because of weak pretests, and I think it's quite unfortunate — I think there's definitely place for weak pretests in the Codeforces format, and proving/testing one's solution is a part of the game. Congratulations to maroonrk who was able to solve six problems despite the weak pretests and win the round!

Facebook Hacker Cup 2021 Finals followed a few hours later (problems, results, top 5 on the left, analysis). Once again the points+ICPC penalty system has allowed for many different strategies, and this time A+D+F was the winning choice. Congratulations to ecnerwala and Um_nik for the successful execution!

I was trying to solve the same 3 problems, but my solution for F did not manage to finish in 6 minutes because it used too much memory and started swapping. After the round I've asked Egor to run it on his machine with 64G RAM, and it finished in 3 minutes there, but it turned out it also gave wrong answer on one testcase. It was surprisingly satisfying to learn that I was not so close, and my (relatively) weak laptop was not the only issue :)

My real issue in this round is that I've treated it as a Facebook Hacker Cup round. I've convinced myself that the Hacker Cup always has tedious implementation problems, and therefore I've started implementing the first solution that came to mind instead of thinking further to find a much simpler approach. In problem D, this ended up being segment trees with lazy propagation on a structure with 6 fields, applied on the previsit orders on the components of the centroid decomposition. The reference solution is a relatively simple dynamic programming on a tree after applying the trick from Aliens. In problem F, I've used a persistent segment tree containing persistent treaps in its nodes to build a graph of size O(n*log^2(n)) to find strongly connected components in, and this was already too much — it has taken me ages to implement, used too much memory and also probably had a bug (or was fully incorrect — I still haven't debugged the wrong answer).

Well, I hope this will be a good reminder to look for simpler solutions next time!

Finally, Open Cup 2021-22 Grand Prix of Nanjing wrapped up the week and the 2021 Open Cup rounds on Sunday (problems, results, top 5 on the left, onsite results). Team USA1 was once again in their own league, getting to 12 problems with 1.5 hours remaining, and being the only team to solve everything in the end. Well done!

Problem D was relatively standard, but as part of the story it contained the following algorithm:

for i in 1..n:
  for j in 1..n:
    if a[i] < a[j]:
      swap(a[i], a[j])

At first sight, this looks to be a standard sorting algorithm. At second sight, though, it seems to be buggy. But it turns out that this algorithm does in fact sort the array in increasing order :)

Thanks for reading, and check back next week!