A WTF week

AtCoder World Tour Finals 2019 in Tokyo headlined the last week (problems, results on the left, open round results, my screencast, analysis). The last three problems turned out too difficult to solve during the contest, so it all came down to speed on the first three. yutaka1999 was the fastest, but his five incorrect attempts gave the competitors 25 minutes to overtake him, and apiad did just that and won the first ever AtCoder World Tour. Congratulations!

I was pretty quick with solving A and C1, but then tried to solve B, C2 and E in parallel, switching often from one to another, instead of focusing on just one of them as it was not clear at that point that solving just one more would be enough for a good result. By the time I managed to come up with a solution for B, it was already too late to catch apiad and yutaka1999.

I found the problems C1 and C2 the most exciting. Consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers x and y, and invert the color of three cells: (x, y), (x+1, y) and (x, y+1). You are given the set of black cells in the final state of the grid. There are at most 10⁵ black cells in C1 and at most 10⁴ in C2, and each black cell has coordinates not exceeding 10¹⁷ by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its y-coordinate was 0, and in C2 there are no further constraints. Can you see a way to solve at least C1?

TopCoder SRM 751 followed on Friday (problems, results, top 5 on the left, analysis). Only rng_58 and pashka submitted all three problems, but the challenge phase did not leave them unscathed, and IH19980412 emerged in the first place thanks to three successful challenges, including one on rng_58 himself. Well done!

Open Cup 2018-19 Grand Prix of Bytedance presented problems from the team Moscow SU: Red Panda on Sunday (results, top 5 on the left, analysis). There were several nice problems in this contest, and problem C was the one I've enjoyed solving the most.

You have some amount x of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount y, and with probability p (p<0.5) your amount of money becomes x+y, and with probability 1-p it becomes x-y. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both x and p are given as fractions with numerator and denominator not exceeding 10⁶, and you need to return the answer using division modulo 998244353.

Finally, Codeforces Round 542 wrapped up the week on Sunday evening (problems, results, top 5 on the left, analysis). Three contestants solved all problems correctly, and there wasn't much challenge activity, so everything was decided by the problem solving order and speed. mnbvmar was the fastest to solve everything, and did (the slightly faster to solve) problem E before problem D unlike the others. Congratulations on the victory!

Last week I have mentioned another Open Cup problem: there's a hidden not necessarily convex polygon with n vertices (n<=200). Your goal is to find its area, but the only thing you can do is to pick a subset of its vertices by their numbers (the vertices are numbered in the order they appear along the polygon), and the system will tell you the area of the convex hull of the chosen points. You can retrieve the convex hull areas for at most n*(n-1)/2 subsets before you need to give back the area of the hidden polygon.

During the contest we tried to invent a solution based on representing the area of the polygon as the sum of signed areas of triangles using one of its vertices as the base point. We could not figure out a way to deal with "signed" part: we need to determine the orientation of each triangle, and while in most cases we can determine orientation of triangle ACD given the orientation of triangle ABC and ability to ask convex hull area queries, we could not see a way to make it work in all cases. Is there one?

The approach that works involves a completely different idea: first, let's find the area of the convex hull of all vertices. Since our polygon is not necessarily convex, then we need to subtract something from it.

For each particular vertex, we can find whether it lies on the boundary of the convex hull or not by checking if the area of the convex hull of all vertices except this one is smaller. Now we know which vertices do not lie on the convex hull of everything.

Now let's take segments of consecutive vertices that do not lie on the convex hull, together with one vertex of convex hull before and after such segment. We claim that those are precisely the polygons whose areas we need to subtract from the area of the big convex hull to find the answer.

The only remaining step is to recursively apply the same algorithm to find the areas of those smaller polygons.

Thanks for reading, and check back next week!