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!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]:
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!