A casino week

Codeforces Round 397 was the highlight of this week (problems, results, top 5 on the left, analysis). Merkurev has created a comfortable margin for himself thanks to fast solutions of the first five problems and two successful challenges - congratulations on the victory!

In my previous summary, I have mentioned two interesting problems. The first was a TopCoder problem about distinguishing optimal strategy and random play: 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.

A quadratic dynamic programming solution is straightforward: given the amount of money we have and the number of rounds remaining, we will compute what's the probability of winning, and what's the probability that a random play will look optimal. In order to compute those probabilities, we will iterate over all possible bets and see what state to we get into if we win and if we lose.

The key insight required to speed it up is: the probability of winning is always a rational number with denominator 2^k (because our play consists of k events each with 50-50 chances). Because of this, it has at most 2^k+1 possible values. On the other hand, it's not hard to see that this probability will not decrease if we increase the amount of money we have. That means that for a fixed k, the probabilities of winning for each a form a set of at most 2^k+1 segments, each with the same value. And that, in turn, allows to speed up the dynamic programming: instead of considering possible bets one by one, we will consider them in groups: a group is determined by which segments on level k-1 we land on if we win, and if we lose. There will be at most 2*(2^k-1+1) such groups, and thus the total running time will be O(b*k*2^k) which is fast enough.

The second problem from the previous summary was a 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?

The solution here is completely magical. It turns out that the number of spanning subsets of edges is odd if and only if the graph is bipartite. A couple of different proofs can be found in this Codeforces thread, but I think they don't fully answer the natural question: what is the intuition behind this fact? How to come up with it without knowing it in advance? I would be grateful if the readers could shed some light here.

Thanks for reading, and check back next week!