A spanning week

TopCoder SRM 708 took place in the middle of last week (problems, results, top 5 on the left, my screencast, analysis). rng_58 returned to winning ways in his second SRM after the November TCO victory - congratulations!

The victory is mostly thanks to the high score on the hard problem (moreover, as you can see from the top 5 this problem decided all five places, not just the winner). It went like this: you are playing a betting game in a casino. You start with a dollars, and your goal is to reach b dollars. You can play at most k rounds. In each round, you bet some integer (possibly zero) amount of dollars not exceeding the amount you have now, then with probability 50% you lose that amount, and with probability 50% you gain that amount. As soon as you reach your goal (have at least b dollars), you leave the casino.

There are of course many strategies to place your bets. In this problem we're concerned with two of them: one is an optimal strategy, where you place each bet to maximize the probability that you will reach your goal by the end of the k-th round or earlier. Note that there might still be several choices for each bet in an optimal strategy that all lead to the same probability of achieving the goal. One of the optimal strategies can be somewhat easily googled. The other strategy we're concerned with is the fully random one: for each bet, we choose the number of dollars between 0 and our amount of money uniformly at random.

Now, you've chosen to use the fully random strategy, and played it to completion (end of k-th round, or getting at least b dollars). An outside observer (who knows the values of a, b and k), however, was assuming that you're actually following an optimal strategy - and did not find evidence otherwise observing your fully random play (in other words, each time you randomly chose a bet that leads to the maximum probability of achieving the goal). What is the probability of such situation?

a and b are up to 100000, and k is at most 5. Can you solve it as fast as Makoto?

Open Cup 2016-17 Grand Prix of China on the weekend provided another set of tough problems (results, top 5 on the left). The reigning ICPC world champions from SPb SU continued their winning streak - well done!

Problem B in this round was a cute purely mathematical puzzle. You are given an undirected graph with at most 200000 vertices and at most 200000 edges. Consider its spanning subsets of edges: such subsets of its edges that connect all its vertices. Is the number of such subsets odd or even?

In my last summary, I have mentioned two nice problems. The first one came from AtCoder: two players are playing a game on a tree where each node has some amount of stones. There's also a chip in one of the vertices of the tree. They make moves in turn, and each move consists of removing one stone from the vertex where the chip is, and then moving the chip to an adjacent vertex. When there's no more stones in the vertex where the chip is, the player that needs to make the next move is unable to do so, and thus loses the game. How to determine who will win with optimal play?

The key idea needed to solve this problem is: if the vertex a the chip is currently on has less or the same amount of stones as its adjacent vertex b, then the second player can force the game to never go beyond b in the tree. If the first player moves the chip to b, the second player can return it to a, and after repeating this a few times a will run out of stones earlier than b, so if the first player doesn't want to lose, he will have to pick a vertex other than b to move to.

Because of this, we can see that the outcome of the game does not change if we only ever allow to move from a vertex to a vertex with strictly fewer stones. The latter game is acyclic, and thus it's very easy to determine the winner in just a few lines of code.

Another problem I mentioned was from Gennady's contest: n<=400 people have participated in a programming contest, and will receive x<=10⁹ roubles of prize money in total. You do not know what is the prize for each place, you only know that each prize is an integer amount of roubles, that they add up to x, and that the prize amounts are in non-increasing order as we go through the ranking list. Given a subset of places in the ranking list (for example the 1st place, the 5th place and the 8th place), what is the smallest possible total prize for those places?

The main idea here is to realize that the prizes essentially form a Young diagram, and as it is often the case, reading the diagram column-by-column after writing it row-by-row proves super useful. Without abstract mathematical terms, one could just say that we can view the distribution of the prize money as the following process: we repeatedly pick a number m_i<=n, and give 1 dollar to the top m_i finishers. All m_i must add up to x.

Now, giving 1 dollar to the top m_i finishers gives some concrete amount f(m_i) dollars to the finishers in our chosen subset of places. Now we can see that we have a classical knapsack problem instance where the weight of each item is relatively small (m_i<=400), each item has a cost f(m_i), and we want to pick a multiset of items with the given total weight x and the smallest possible cost. This problem is solved by noticing that we must use the item with the smallest cost-to-weight ratio for most of the total weight - more precisely, we can keep using that item until the remaining total weight is below 400²=160000. And for such small total weight we can then solve the knapsack problem using the standard dynamic programming.

The proof of the fact that we only need to run the dynamic programming up to 400² is based on the following lemma: in a set of n numbers, there's always a non-empty subset with sum divisible by n.

Thanks for reading, and check back soon for this week's summary!