A generating week

TopCoder returned with its SRM 772 during the Dec 9 - Dec 15 week (problems, results, top 5 on the left, my screencast). Once again tourist had to settle for the second place despite great coding and challenge phases because ksun48 could solve the hardest problem. We were discussing during the TopCoder Open onsite that ecnerwal seems to just think in generating functions, and apparently so does ksun48, even though he tried to hide the fact by explaining his combinatorial-ish solution :) Congratulations on the win!

I was comfortably in the top 10 this time, meaning that both me and tourist each got 4 TCO20 qualification points again and I kept my 1-point lead going into the final SRM of the stage.

The medium problem in this round was very nice. You are given 100000 points on the plane and a number k. Given a subset S of the set of given points, and denoting all other given points as its complement T, we define the score of S as the sum of pairwise Manhattan distances between the points in S minus the sum of pairwise Manhattan distances between the points in T. What is the largest (by the number of elements) subset of the set of given points such that its score does not exceed the given number k?

Codeforces then hosted two rounds on the weekend. Round 606 took place on Saturday (problems, results, top 5 on the left, analysis). With a whole 1 accepted solution for both E and F combined, the round was effectively decided on the first four problems. Ainta was the fastest and won the round, well done!

Round 607 followed on Sunday (problems, results, top 5 on the left, analysis). This round got a quite different top 5, with only Radewoosh appearing in both. ksun48 got most of his speed advantage over Um_nik on the easier three problems, and then kept the lead by solving D and E in a comparable amount of time. Congratulations on the win!

Thanks for reading, and check back for more!