SRM 597: argh

The other day I accepted to write editorials to the TCO. Unfortunately they never warned me that some of the problems I would read could end up getting used outside of the TCO. I only learned that after the problems were sent to me. Had I know that I could miss SRMs just for helping with these editorials, it would have been a deal breaker. I hate missing SRMs. I really hate missing SRMs.

I had hopes that maybe if one of the problems I read gets used like this in a SRM, I could at least have a chance to write the other problems in the SRM. Nope. Then I tried to maybe get added as a tester to read the other problems so I could at least have progress in the editorial. Nope. So missing this SRM was useless. Week ruined.

Div1 600: ConvexPolygonGame

This is the problem that ruined my week. Two players take turns. It all starts with a convex polygon. In each turn, the player draws a polygon such that:

• The previous polygon contains all the vertices of the new polygon.
• The vertices of the new polygon are lattice points
• No three vertices are colinear.

The player loses when it is impossible to draw such a polygon.

The trick is to notice that as long as a player can make a move, the player can always pick a minimal triangle that will win the game. We know that the game will end with a single triangle. Imagine this triangle came after a sequence of moves. This triangle will then be inside each of the polygons used in the game, including the first one. Then first player can just directly use this triangle and win.

So we just need to check: Is there at least one triangle with non-zero that can be drawn in the first turn? If so, first player draws a terminal one and wins, else the first player loses.

So far it is a cool little problem. The original version planned for TCO had `(-500 <= x,y <= 500)` constraint for the vertices of the first polygon. Which had a couple of cute solutions, for example, you could iterate through all the points inside the polygon and if you ever find a point that is not colinear to the previous two points, the job is done. Unfortunately, when migrating it to SRM format, they changed the problem by making the constraints much larger. So the clever conclusion that you only need to check if one drawable polygon exists becomes just problem obfuscation, because the real issue is to work up the implementation problem of checking for that condition. Apparently the idea is to use only the points that are close to the vertices, within 200000 distance or something like that.

I think this problem was a decent TCO finals easy with the small constraints. With the large constraints though, it becomes a SRM div1 medium with excessive implementation that doesn't make it more interesting.