## Wednesday, October 8, 2014

### Problem discussion: Timus OJ 1225 Flags

This was one of the interesting problems I solved last week. I was just checking out Timus OJ when I stumbled across it. Here is the abridged problem statement (read the original statement at Timus OJ):
Given $$n$$, the number of stripes, find the number of distinct ways the stripes can be colored if the only colors that can be used are white, blue and red. These constraints should be satisfied:
• No two consecutive stripes should be of the same color
• A blue stripe must always be between a red and a white one or a white and a red one.
If you want to try to come up with a solution yourself first, now is a good time. I am going to explain my solution in the next paragraph. If you want to submit your solution you need to register at http://acm.timus.ru.

The first thing to notice is that the last stripe cannot be blue since a blue stripe can appear only between a red and a white stripe. So, the solution to the problem is $\text{number of ways in which red is last + number of ways in which white is last}$ But how do we find those quantities?

If the last stripe is red, the stripe before it has to be either white or blue. Suppose we have a number of arrangements in which the second stripe from the last is white. All these arrangements contribute to the number of arrangements with last stripe red because we can color the last stripe red in all such arrangements. But, this is not the only way we can get arrangements with the last stripe red because we haven’t yet considered the case in which the second to last stripe is blue.

Now, suppose that the second to last stripe is blue. The stripe that comes before this can be either red or white. If that stripe is red then the last stripe cannot be red so we ignore that case. So, all arrangements in which the third stripe from the last is white can have the last stripe red if we add a blue and a red stripe (in that order). Observe that there are no more ways of getting the last stripe as red other than the two discussed (convince yourself of this).

Similar arguments can be made for finding the number of ways in which the last stripe is white. It is clear that we have managed to come up with a recursive solution to the problem. Let’s state the recurrence relation in a bit more formally.
Let $$f(i, c)$$ be the number of ways of coloring the stripes $$1,\, 2,\, ...\, ,\,i$$ such that the $$i^{th}$$ stripe has the color $$c$$.
$\begin{equation} f(i, c) = \begin{cases} f(i - 1, red) + f(i - 1, white) & \text{if } c = blue, \\ f(i - 1, white) + f(i - 2, white) & \text{if } c = red, \\ f(i - 1, red) + f(i - 2, red) & \text{if } c = white. \end{cases} \end{equation}$ So, the final answer will be $\begin{equation} answer = f(n, red) + f(n, white) \end{equation}$ where $$n$$ is the total number of stripes.
The next step is to observe that this recursive solution has overlapping sub-problems. If it is not obvious, you can convince yourself of this by drawing a recursion tree. So, we need to use dynamic programming to speed up our solution. We have $$3N$$ dp states (why?) and hence the time complexity is $$\mathcal{O}(3N) = \mathcal{O}(N)$$.

As always I will leave the implementation to you. But, if you are stuck you can have a look at my solution.

Have a nice day!