← All solutions

Writeup by Onufry

Shortest judge solution: 538 bytes. Shortest team solution (during contest): 1635 bytes.

This was one of my favorite problems in this contest — non-trivial, but with surprisingly little code once you got it, and additionally having “implicit” limits (in the sense that the precision with which x and p are the constraints, but the time complexity isn’t really easy to express in terms of the big-O notation).

The first key to solving this problem is noticing that your next move should not depend on the history, but just the amount of money you currently have, as history gives you no extra information. Thus, the strategy can be described simply by defining two numbers — how much do you have to lose to quit, and how much do you have to win to quit. Let’s denote the first number L and the second W. This means that at the end of the game you will always have either won W or lost (1 − x ) L dollars, and the only question left is what is the probability of the first event (depending on the choice of W and L).

Denote the chance of winning in the end if at the moment you have D dollars by P( D ). Obviously, P(W ) = 1 and P( L) = 0 (well, except for the very special case of W = L = 0, which means we don’t play at all, and the expected win is obviously zero; we ignore this case from now on). For any D between L and W we have P( D ) = p · P( D + 1) + (1 − p) · P( D − 1). This can be easily transformed to P( D + 1) = (1/p) P( D ) − (1−p)/p P( D − 1) — a recursive sequence definition. Solving such recursive equations is a well-known problem, and in this case we get

P( D ) = α + β ((1−p)/p)^D.

We now have to choose α and β to fit the boundary conditions of P( L) = 0 and P(W ) = 1. This is just a system of two linear equations, and after solving them we get:

β = 1/(r^W − r^L); α = −r^L/(r^W − r^L),

where r = (1−p)/p. We are interested in P(0), which is α + β = (1 − r^L)/(r^W − r^L).

So, for a given L and W we are able to determine the probability of winning, and thus — the expected value of the gain. Thus, we can check all reasonable values of L and W and choose the best pair. The last question remaining is “so what are the reasonable values of L and W, anyway”? The programmer’s approach to this problem is to simply take the worst case (it both seems obvious and is true that the larger p and the larger x, the larger this range is going to be, so the worst case is p = 0.4999, x = 0.9999), incrementally increase the range, and check at what point does it stop increasing the expected value. The range we get this way is L = 20528 and W = 2498 (which means it’s OK to just check all the possibilities). Formally, one also needs to prove that the expected value will not go up after a period of decreasing — an argument involving the convexity of the expected value in this problem which we’ll leave as an exercise.