A week with a Japanese surprise

The Open Cup held a surprise second round, the Grand Prix of Japan, last Sunday (results, top 5 on the left, overall standings). Past Glory team returned to, well, past glory with a very convincing victory - congratulations!

Problem B, while not very difficult algorithmically, presented a nice implementation challenge: one could write the code in 10 minutes, but could also spend an hour or more. You were given 3000 boosters with integer coordinates up to 10⁹, each pointing in one of four cardinal directions. You can start at any booster, fly in the direction in points to the next booster (if any), then fly in the direction that booster points, and so on. As soon as you leave a booster, it disappears, so you don't change your direction when you pass through its point again. What is the maximum number of boosters you can visit if you choose your starting booster properly?

In my previous post, I've mentioned the medium problem from TCO 2015 Round 3B: you are given 200000 cookies (3 types pictured on the left), with two players taking those cookies in turn one by one. Each cookie has some value for the first player, and some possibly different value for the second player. It is known that the second player always takes the cookie with highest value for him, and when there are several, with the highest value for the first player among those. The first player, on the other hand, is more flexible. He can take any cookie, and his goal is to maximize the total value of the cookies he gets in the end to him minus the total value of the cookies the second player gets in the end to the second player. What is the optimal strategy for the first player?

I won't tell you the full solution, but I will give you a key hint. Let's forget about the goal of the first player, and simply ask ourselves: which subsets of cookies can he achieve? Let's also order the cookies by second player's priorities: first by decreasing value for the second player, then by decreasing value for the first player. It's clear now that the second player will take either the first or the second cookie in this order on the first move, one of the first four cookies on the second move, and so on. In fact, the first player can achieve any subset that has the following properties: at most one cookie from the first two, at most two cookies from the first four, at most three cookies from the first six, and so on.

This is not the full solution yet, but we've effectively removed the game from the problem - now we just have a question about some subsets of our set, and this question is much easier to answer.

Thanks for reading, and check back next week!

Tweet