A code week

Universal Cup started its 3rd season this Saturday with Stage 1: St Petersburg (problems, results, top 5 on the left, analysis). Team 03 Slimes was in the lead for a long time, then paused a bit and gave everyone a chance to catch up, only to solve 3 more problems in the last hour and claim the clear first place. And all that even though our team stole one of their usual team members and they had to participate with just 2. Well done!

Solving problem B was very satisfying, and I think describing its solution next week will help me understand the underlying math better, so here is the problem statement: first, we draw the vertices of a regular n-gon (n<=10000) on the plane. Then we repeat the following process m times (m<=30000): take any 3 already drawn points (either the original n-gon vertices, or ones drawn during the previous steps) A_i, B_i, C_i, and draw the point A_i+B_i-C_i (the fourth vertex of a parallelogram). Finally, we need to handle multiple queries of the form: given k drawn points (the sum of k over all queries <=30000), do they form the vertices of a regular k-gon in some order?

Initially the problem seems quite straightforward as we can just simulate the process and check the required condition using some simple geometric formulas. However, it turns out that we can get points that are really close to a regular k-gon but not exactly one in this problem, and no feasible floating point precision is enough. So how to solve this using only integer computations?

Codeforces Global Round 26 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). One of the highlights of the round was an amazing successful experiment, but there was also a pretty close fight for the first place, to the point that jiangly needed just one successful hack to win, which he unsuccessfully attempted. I wanted to check if he had a chance, in other words if there were any failed system tests in jiangly's room, but I could not find a way to find which of the 646 available rooms is it. Does anybody know how to find the room of another contestant? Apparently this link was staring me in the face, it is shown at the top of the user's submission history, which appears after a double-click in the corresponding standings cell. And it turns out that there were no failed system tests in jiangly's room, which means that his only chance for the required +100 could lie in some anti-hash tech.

In any case, tourist held on to his first place, and increased the gap at the top of the rating list. Interestingly, the top 3 in this round coincided with the top 3 by rating after Benq did find his successful hack. Congratulations to tourist, jiangly and Benq!

Thanks for reading, and check back next week.