Aladdin and the Magical Sticks

Problem Name: Aladdin and the Magical Sticks
LightOJ ID: 1342
Keywords: math, probability, expected value, memoization, harmonic number

I’ve always had a keen interest in problems related to numbers, counting, probability and so on. It is only recently, however, that I’ve started to grow aware of the reasons why this might be so. Let’s take this problem as an example. After I read its description for the first time, I knew I would not rest until I found a satisfactory solution, and going into it I recognised that right then I still had some gaps in my knowledge, but still, it was thrilling to know that I was about to tackle something that would lead me to learn new things. It is a little hard to put into words, but there’s just something deeply enjoyable when you encounter a problem that you know you can’t yet solve, but your intuition tells you that you’re close; in other words, even if it’s a little beyond your current knowledge or skill, it’s within your reach. This is something that I’ve personally experienced with many math–related problems, and that’s probably the main reason why I find them fascinating.

Anyway, back to the subject at hand, this problem tells us the story of Aladdin, who is presented with a group of sticks, each one with a certain weight. He is asked to pick up the sticks, one by one, and every time he picks a stick, it is returned to the group and he has to continue picking sticks until all of them have been chosen. There’s a couple of extra details of importance: initially, the probability of picking any one stick is the same for all sticks, but, there’s also two types of sticks. One type is easily recognisable by Aladdin, so every time he picks a stick of this type, he doesn’t pick that same stick again. The other type of stick is normal and there is no way to recognise it, so sticks of this type could be picked many times. The question is: what is the expected weight of all the sticks Aladdin has to pick until all sticks have been chosen?

You may have noticed that this problem has a similar “flavour” to the Dangerous Maze problems —and they are, after all, from the same problem setter :). We could even rewrite the problem statement and use doors instead of sticks, and distances instead of weights, and the problems would look pretty similar. However, there is one crucial difference; in this problem you don’t “get out” until you have picked all sticks (or doors).

This difference turns this into an entirely different kind of problem. To give you some idea about the nature of the problems I’m talking about, think about how to calculate the expected number of throws of a single die until it shows a certain number, and how it differs from calculating the expected number of times you have to throw a die until you have seen all of its sides. Another way to look at it is to think about sticker albums or collectible card games. Let’s say that you can buy one card at a time, which comes completely at random (all cards with equal probability). How many cards do you need to buy until you complete your collection?

Not surprisingly, this is a classic conundrum known as the Coupon collector’s problem, and the math behind it is actually fairly accessible once you’re familiar with the basics of probability and expected value. Quoting from Wikipedia:

The key to solving the problem is understanding that it takes very little time to collect the first few coupons. On the other hand, it takes a long time to collect the last few coupons.

Let’s go back to the example with dice. Let’s say you want to know the expected amount of tosses until you have seen all sides from a standard die. You can split this problem into six sub–problems: how many tosses until you see the first “new” (previously unseen) side? How many tosses after that until you see the second “new” side? And so on until the sixth and final “new” side.

It’s easy to see that the first sides come up pretty quickly —you are guaranteed to see a new side on your first toss, and it’s very likely that you’ll see a new side on your second toss because the chance of repeating your previous toss is only \(1/6\). It’s the last unseen sides that take longer to come up. This leads to a very elegant formula for the expected value in the coupon collector’s problem. Using the terminology of this problem, if all sticks were of the second type (the type that is unrecognisable), then the expected amount of times that Aladdin would have to choose a stick until all of them were picked would be:

Where \(H_n\) is the \(n\)th harmonic number. At this point, I’d like to say that it’s very possible that you have now enough elements at your disposal to solve this problem. If you haven’t done so already, I suggest you take at least a couple of minutes right now to think about the mathematics of it, and try to formulate a solution —even a preliminary one. Nothing can replace that type of mental exercise.

Okay, now here’s what I found to be the final piece of the puzzle to arrive to my solution; it’s something I call “complementary” or “background–foreground” thinking (there’s probably a better name for it, but this is how I think of it). Edit: After re–reading some passages of one my favourite books ever —GEB— I can see that this concept is usually referred to as “Figure and Ground”. I’ll try to remember this…

Let me give you an example. Maybe you have confronted the Birthday paradox before, where you want to calculate the exact probability that any two people in a group of \(n\) people have the same birthday. You can approach this in two different ways, and one of them is going to be vastly easier than the other. You can try to go “straight” to the solution (what you see in the foreground) and consider every pair of people and the probability that they do have the same birthday. Obtaining the answer through this process is very complicated because of the relations formed between the pairs and the fact that you want to know the probability of any pair having the same birthday. The other approach is looking at the background or complement, and think of the probability that the \(n\) people have all different birthdays (let’s call it \(\bar{p}\)), and then your answer comes from the complement \(1 - \bar{p}(n)\). Much easier to calculate.

I hope the crux of the matter is clear. Sometimes if you can’t solve a problem looking at the foreground, it might be useful to look at the background and try to solve it from there. This is what I applied here. The idea is to initially consider all sticks as if they were of the second type; this gives us an initial expected weight \(W_i\). After that, subtract from \(W_i\) a weight from the sticks of type 1, proportionate to the “excess” in our calculation.

Why an “excess”? Well, it should be easy to see that if some of the sticks are of type 1, then our first estimation \(W_i\) is larger than the right answer, because no matter how we look at it, all sticks of type 1 are picked only once, no more. Let’s call \(\hat{E}\) the expected amount of times that one particular stick would be picked, if all sticks were of type 2. Then we have:

However, for sticks of type 1, this expected value is exceeded by the following amount (\(E_x\)):

Alright, now we can formulate the following algorithm:

• Let \(A_T\) be the average weight of all the sticks.
• Let \(E\) be the expected number of sticks that have to be picked (if all were of type 2). This comes directly from the coupon collector’s problem as \(E=n \cdot H_n\).
• \(W_i = A_T \cdot E\)
• If there is one or more sticks of type 1:
  • Let \(N_1\) be the number of sticks of type 1 and \(A_1\) the average weight of the sticks of type 1.
  • \(W_f = W_i - N_1(H_n - 1) \cdot A_1\)
• Else, \(W_f = W_i\)

Our answer is \(W_f\).

A Dangerous Maze (II)

Problem Name: A Dangerous Maze (II)
LightOJ ID: 1395
UVa ID: 12411
Keywords: probability, expected value

You are inside a maze, in front of a series of doors. By choosing a door, you follow a path, taking a certain amount of time, and at its end you find yourself either out of the maze, or back at the beginning. The question is, if the probability for choosing any given path is the same for all doors, then what is the expected amount of time to get out if the maze (if it’s at all possible)?

However, there’s an interesting twist: you also remember the last \(K\) decisions you made, and if you have previously chosen a door that takes you back to the beginning, you won’t select it again, as long as it remains one of your last \(K\) decisions.

I found the concept behind this problem very interesting, and at first I tried to come up with some sort of dynamic programming solution. However, after some consideration, it became clear that such an approach would be infeasible due to the problem constraints (the number of doors \(n\) can be 100, and \(K\) can be any number between 0 and \(n\)), and the intricate relations formed when you consider your K–sized memory.

So I tried the pure math way… armed with a pencil and a stack of paper, I filled many pages with equations and drawings to help me model the problem conveniently, making some mistakes along the way, correcting them, trying to find some kind of pattern until I could identify something that could let me formulate a conjecture that I could then translate into code. In this post I’ll try to summarise my findings.

First of all, let’s split the doors into two sets, and label them as follows:

Where \(a_i\) is the time for the ith door that takes you out of the maze, and \(b_i\) is the time for the ith door that leads you back to where you started. The total number of “positive” doors (the ones that lead you out) is denoted \(p\), and the total number of “negative” doors (the ones that take you back to the beginning) is \(q\). Notice that \(n=p+q\).

Now, let’s define \(E\) as follows:

\(E(S)\)

The expected amount of time to get out of the maze, after having visited the sequence of doors \(S\).

The sequence (ordered list) given as argument to the \(E\) function is important because it represents your “memory”.

When you’re just starting your journey, you haven’t visited any doors, so the value of \(E\) would look like this:

In other words, \(E\) is defined recursively, based on the fact that whenever you choose one of the \(b\) doors, you are back at the beginning, but having added your last decision to your sequence (note the use of parenthesis as notation for the sequences).

Let’s add a few more definitions, in order to simplify the expressions that come a little further below:

\(\hat{E}_i\)

The sum of all possible \(E(S)\), where \(S\) has exactly \(i\) elements.

With this, let’s reformulate \(E(())\), and see what happens when \(K=0\):

The equation [2] is the answer for the case where \(K=0\), meaning you can’t remember any previous decisions (which is, by the way, the same situation as in the first A Dangerous Maze problem, LightOJ ID 1027).

Things start to get interesting when you consider \(K > 0\):

Equation [3] requires the most attention, but it’s simply the result of thinking what is the result of adding \(E(\,(b_u)\,)\) for all possible values of \(b_u\).

The same reasoning can be used for \(K=2\) and \(K=3\), but doing the actual calculations for \(\hat{E}_2\) and so on becomes increasingly difficult. You can try to deduce all of this for yourself, but suffice to say that the results for \(E\) with the first values of \(K\) are the following:

Can you see the pattern? (Also, do you see how I managed to fill pages upon pages with my conjectures and wrong turns?)

All in all, a very nice problem, with some interesting mathematics behind it. I still don’t know if there’s a shorter way to deduce the general formula (maybe using some number or probability theory I’m not aware of), instead of just using conjectures… If you have any ideas, let me know :).

Winning Streak

Problem Name: Winning Streak
UVa ID: 11176
Keywords: dynamic programming, probability, expected value

This is a very nice problem that involves probability and dynamic programming. What I find particularly nice about it is that formulating the D.P. structure requires, I think, a little creativity.

First, it’s necessary to understand how the expected value is calculated, and how are the probabilities of separate events combined to produce the probability that all events occur.

With that out of the way, and after some time pondering on how to model this problem for a D.P. solution, we could initially define the relation \(f(i, j)\) as follows:

\(f(i, j)\)

The probability of having a winning streak of exactly \(j\), after \(i\) games.

However, it is more convenient to define it slightly different, for reasons that will become apparent in the reasoning below:

\(f(i, j)\)

The probability of having a winning streak of \(j\) or less, after \(i\) games.

For example, \(f(5, 3)\) would be the probability of having a winning streak of 0, 1, 2 or 3 after 5 consecutive games. Then we can begin to see how our D.P. data structure will be filled. First of all, for all pairs \((i, j)\) where \(j \geq i\), it’s easy to see that the probability is 1:

Now, when \(j = i-1\), the value of \(f(i,j)\) will be \((1 - p^i)\), where \(p\) is the probability of winning a game. This is because the only way to have a winning streak of \(i\) in \(i\) games is winning them all in a row (hence the \(p^i\)), and that is the only case that need to be excluded from \(f(i, i - 1)\).

We have now:

For the remaining positions (\(j < i-1\)), we need to figure a way to calculate their values, relating it to what we already have. Let’s compare the meaning of \(f(i, j)\) and \(f(i-1, j)\).

When we think about \(f(i-1, j)\), we recognise that it corresponds to the probability of the sequences of games:

Where \(G_k\) for all \(k\) between 1 and \(i-1\) is either W or L, and where there are at most \(j\) consecutive W’s. Similarly, \(f(i, j)\) is the sequence:

Where there are also at most \(j\) consecutive W’s. Let’s consider what is happening with \(G_i\). It could be L, in which case nothing changes, because it doesn’t create any winning streak bigger than \(j\). Or it could be W, and in that case, we need to remove those cases where it does create a winning streak of \(j+1\).

Given that we can be sure that in the sequence up to \(G_{i-1}\) there are at most \(j\) consecutive W’s, then the only way for \(G_i\) to create a winning streak of \(j+1\) is this:

And so, we reach to the formula for our remaining positions (where \(j < i-1\)):

To get our answer we just need to iterate over the nth row of our data structure, and use the fact that \(f(n, j) - f(n, j-1)\) is the probability of having a winning streak of exactly \(j\) in \(n\) games.

Our final implementation in code then could look something like this:

// dp[i][j] will have the probability of having a maximum winning streak of
// j in i consecutive games
double dp[MAXN + 1][MAXN + 1];

// pp[i] will have p^i
double pp[MAXN + 1];

int n;       // from the input, the number of consecutive games
double p;    // from the input, the probability of winning 1 game
double ans;

void run_dp()
{
    pp[0] = 1.0;
    for (int i = 1; i <= n; ++i) pp[i] = pp[i - 1] * p;

    for (int j = 0; j <= n; ++j)
        dp[0][j] = 1.0;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n; ++j) {
            dp[i][j] = dp[i-1][j];

            if (j == i - 1)
                dp[i][j] -= pp[i];
            else if (j < i - 1)
                dp[i][j] -= dp[i - j - 2][j] * (1-p) * pp[j+1];
        }

    ans = 0.0;
    for (int j = 1; j <= n; ++j)
        ans += j * (dp[n][j] - dp[n][j - 1]);
}