An overall week

Codeforces Global Rounds series of 2019 has concluded during the Dec 16 - Dec 22 week with the Round 6 (problems, results, top 5 on the left, analysis). With problem F being tricky to implement but quite standard, problem G requiring to notice a complex pattern after implementing an ineffective solution, and problem H relying on some cool maths coming almost out of nowhere, there was plenty of ways for top contestants to pick their poison. Only 1919810 and sunset could solve two of those three, and 1919810 got all easier problems correct as well thus securing a confident victory. Well done!

The choice of counting the 4 best performances out of 6 for the overall standings (top 5 on the right) seemed to turn out quite nicely, allowing contestants to skip some rounds and/or to enjoy a really bad day sometimes, although maybe Radewoosh would prefer 2 out of 6 :) Thanks to Codeforces and to XTX Markets for organizing the series!

TopCoder Open 2020 points-based qualification stage 1 also concluded that week, with the SRM 773 (problems, results, top 5 on the left, my screencast, TCO20 qualification standings). There was no stopping tourist this time, with yet another dominating coding phase performance and another 175 challenge points he was simply out of reach and thus finally earned the 5 qualification points he needed to qualify for TCO20. I do not have my TopCoder stats scripts working anymore to support this claim with data, but it feels like he has really stepped up the challenge game a lot recently. Huge congratulations!

Open Cup 2019-20 Grand Prix of Xi'An on Sunday sent two problems to the New Year Prime contest (results, top 5 on the left). Having penalty time almost twice as big as that of the second-placed NNSU Almost Retired, team USA1 had no other way to victory except solving more problems, which they delivered by becoming the only team to solve L in the last hour, and then finally getting F from the 24-th attempt. Congratulations!

With this win, team USA1 has almost caught up with team Past Glory in the overall standings after 2019 (top 5 on the right), promising us an exciting second half of the season in 2020!

In my previous summary, I have mentioned a TopCoder problem: 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?

The key insight in this problem is to consider how does the score of a set change when we add one more point to it. The distances from this point to the points already in S are added to the score; the distances from this point to the points not in S are also added to the score as they used to be subtracted from it and now they are not! Therefore adding a point to S simply increases the score of S by the sum of distances from this point to all other points.

Now it is clear that we should just start with empty S and add points in order by this sum of distances until we exceed k.

Thank for reading, and check back for more!