ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1225. Flags

How to use dynamic programming to solve this problem?
Posted by Nick 13 Jan 2014 19:16
How to use dynamic programming to solve this problem? I used fibonacci.
Re: How to use dynamic programming to solve this problem?
Posted by Egor 20 Aug 2015 02:15
As far as I understand, this problem is about combinations and not about fibonacci.

If there was only the first condition, then for any N we have only 2 possibilities to create the flag.
That is, f(1) = 2, f(2) = 2, f(3) = 2, f(4) = 2, ..., f(N) = 2;
This is true, because the choice of the first stripe determines the rest of the flag automatically. If you choose the first stripe to be white-colored then you are destined to choose the red stripe to be the second one. And vice versa. Don't make my words a HOLY WISDOM - think about it till you can feel it yourself. Don't read next, until you fully and completely get it.

The second condition is here to complicate your life. It doesn't do anything to our function f(x) if x equals to 1 or 2. That is, f(1) and f(2) are still equal to 2.
(By the way, I've just noticed that I've pulled the function from under the pillow. Well, in my mind this function returns the amount of different flags that can be created if you need to make it from x stripes. Ok, now we're moving on...)

But it allows us to INSERT the blue stripe between the two: white and red stripes.

This concept of INSERTION is really the key here. Think about it. If you were supposed to gain anything intellectually from solving this task at all, I bet, it was this very concept.

If we have some sequence of 2-colored flag: WRWRWRWRWRWRWR (White and Red), and this sequence contains all the N stripes that we need, then we really don't have any place to INSERT our blue stipe.
You think, ok, that's fair, and remove one of the stipes (e.g. the left-most). Now you have the place for your blue stripe ... and you can insert it in many ways: wBrwrwrwrwr or wrBwrwrwrwr or wrwBrwrwrwr ... well, you get the point :)
This way, by removing one of the stripes you have created X COMBINATIONS. This word is also important, that is why it is all upper-case :)

If you remove ONE MORE stripe (think about removing as n - 1 or better n--), you now have to INSERT 2 blue stripes somewhere in the sequence wrwrwrwrwrwr...
E.g. wBrBwrwrwrwrwrwr, or wBrwrwrwrwrwrwBr. Now there should be more COMBINATIONS than in the previous case (figure out yourself, how many :) ).

The last point I want to make is that you have to know your limits. That is, you have to understand when to stop removing stipes from the flag and stop INSERTING blue stripes in it. When you get to this point (keeping in mind all the previous points), you will figure this out by yourself easily...

Edited by author 20.08.2015 02:16

Edited by author 20.08.2015 02:18

Edited by author 20.08.2015 02:23

Edited by author 20.08.2015 02:23

Edited by author 20.08.2015 02:25

Edited by author 20.08.2015 02:26

Edited by author 20.08.2015 02:27

Edited by author 20.08.2015 02:27

Edited by author 15.10.2016 20:15

Edited by author 15.10.2016 20:16

Edited by author 15.10.2016 20:20

Edited by author 15.10.2016 20:21

Edited by author 15.10.2016 20:21
Re: How to use dynamic programming to solve this problem?
Posted by thugwaffle 13 Sep 2015 23:43
This is really extremely helpful in reasoning about the problem, thank you
Re: How to use dynamic programming to solve this problem?
Posted by Chuk.Charles 17 Sep 2015 17:07
Егору зачет! За крутое решение и за знание англ)
Re: How to use dynamic programming to solve this problem?
Posted by Khanhhuy_19 27 Dec 2017 18:09
lol