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!

Comments

  1. UnknownOctober 23, 2016 at 4:58 AM

    I have a doubt.
    Do you think the first condition of the recursive function is required?
    I mean the condition in which if c = blue you compute f(i-1,red) + f(i-1,white).

    ReplyDelete
  2. Alex JohnJune 7, 2017 at 1:32 PM

    They are generally good at any height. Still, if you want to compliment any type of construction, you can follow this key rule.Wholesale Printing Company

    ReplyDelete
  3. adist98July 18, 2019 at 5:10 PM

    You don't actually require the function that checks for colour BLUE.

    ReplyDelete

Post a Comment

Popular posts from this blog

Problem discussion: ShufflingCardsDiv2 - Topcoder SRM 641 900pt

Topcoder SRM 641 happened a few days ago and featured an unusually easy problem set for division 2. Before continuing reading the post, please read the problem statement (login required). Now that you have read the problem statement, let me state the most important fact in the problem statement The cards are shuffled exactly twice. This is very important because it makes the problem much easier. Since there are only two shuffles, there are a limited number of steps to be followed. Let’s analyze the shuffling procedure closely. In the beginning we have \(2N\) cards numbered from \(1\) to \(2N\). These cards are divided into two piles: one containing the first half cards \(1 \cdots N\) and the other containing the remaining cards. Let’s denote the cards which have number less than or equal to \(N\) as \(A\) and the others as \(B\). Now, the two piles will look like this \(\text{A A A A A …}\) \(\text{B B B B B …}\) After performing the interleaving, we will get a deck that look
Read more

Introduction to tries through Facebook Hacker Cup 2015 Round 1 - Autocomplete

Image
In the last week's post I discussed the solution to the problem "Homework" from Facebook Hacker Cup 2015 Round 1. This post is about the problem "Autocomplete" from the same round. You can  read the problem statement  available on the Facebook website. If you don't have a Facebook account, you can download problem statements from Codeforces Gym . I will re-state the problem in fewer lines. You have a new phone which has an auto-complete feature. But, it will complete your word only if there is there is no ambiguity on how the word should be completed. Formally, it will complete a word iff there is exactly one way to complete the word. It so happens that the phone's dictionary is empty by default. So, for the auto-complete feature to work, before typing a word you need to add that word to the dictionary. You need to send a message containing \(N\) words. What is the minimum number of characters must you type to send all \(N\) words? (Note that the
Read more

Problem discussion: Facebook Hacker Cup 2015 Round 1 - Homework

It's been a long time since I last wrote on this blog and a lot has happened since then. The most important of all is that my personal website is up at  anirudhrb.com  and consequently this blog can now be accessed at  blog.anirudhrb.com . Also, you can now reach through email at  mail@anirudhrb.com . Let's get down to business now. The online part of Facebook Hacker Cup 2015 concluded recently and the top 25 contestants have been selected to compete in the onsite finals. The problem I am writing about in this post appeared in the Round 1 (there were 3 rounds). The title of the problem is "Homework" and here is the abridged statement: Given three integers \(A\), \(B\) and \(K\), find the number of integers in range \(\big[A, B\big] \) that have a "primacity" of \(K\). Primacity of a number \(N\) is defined as the number of distinct prime factors of \(N\). You have to process \(T\) such queries. The constraints are as follows: \(2 \le A \le B \le 10^
Read more