You are asked to design 10 flags with vertical stripes using three colors: blue, orange, yellow. You are asked not to have two neighboring stripes of the same color. You are also asked not to have yellow and orange stripes next to each other as it doesn't look nice. Your goal to minimize the number of stripes I need to use. So, you can make 3 different one-striped flags. You can make 4 different two-striped flags: blue-yellow, blue-orange, yellow-blue, orange-blue. You can make 6 different three-striped flags: blue-yellow-blue, yellow-blue-yellow, orange-blue-orange, blue-orange-blue, orange-blue-yellow, yellow-blue-orange. That is, you can make 13 different flags using 3 stripes at most. Your task is, given the number of flags and the details of colors that may not be adjacent to each other (a color always has atleast one forbidden neighbor namely itself),return the minimum number of stripes you need to design the given number of different flags using at most that amount of stripes.

My original bruteforce solution was to go level by level increasing the number of stripes used one at a time, and after each level completion checking if the total number of flags has been reached. But this approach takes hours on the computer to execute when the number of flags is huge, say 10^17. It is required that the solution be found in 2 seconds. My feeling is that we need to find some kind of series progression that will vary from input to input. Once the series is found we condense it into a formula and use it to solve the problem. I tried with some sample inputs but no luck finding any such series (even for the example given above). Any clues?

Ok here is my try -- would something like this work?

N == total number of available colors F == total number of colors that can't be next to each other C == total number of flags needed

Gagan (/^_^\) SCJP2 SCWCD IBM486 <br />Die-hard JavaMonk -- little Java a day, keeps you going.<br /><a href="http://www.objectfirst.com/blog" target="_blank" rel="nofollow">My Blog</a>

Gagan Indus
Ranch Hand

Joined: Feb 28, 2001
Posts: 346

posted

0

Never mind i read your question again and it appears you already tried what i was suggesting.

Ramboo's reply seems could do the trick.

A Bhattacharya
Ranch Hand

Joined: Oct 22, 2007
Posts: 125

posted

0

I can't understand either of your answers. In the given example, the forbidde combinations are BB, OO, OY, YY, YO which are 5 in number. For 3 stripes, we have a total of n*n*n = 27 permutations of which we need to eliminate the invalid ones. From the 5 invalid combinations given, we need to construct invalid combinations with 3 stripes. From BB we get: BBB, OBB, BBO, YYB, BBY From OO we get: BOO, OOB, OOO, YOO, OOY From OY we get: BOY, OYB, OOY*,OYO, YOY, OYY From YY we get: BYY, YYB, OYY*,YYO,YYY From YO we get: BYO, YOB, OYO*,YOO*,YYO*,YOY*

The ones marked * are those that already have been counted; so we get 21 invalid ones. Hence only 27-21=6 are valid ones with 3 stripes. Can you explain how your formula is working along these lines? [ May 12, 2008: Message edited by: A Bhattacharya ]

Rambo Prasad
Ranch Hand

Joined: Feb 23, 2006
Posts: 628

posted

0

Bhattacharya,

My solution is wrong...I didn't take into consideration the repetition of colors...

Can the flag have more than 3 strips or is 3 the max [ May 12, 2008: Message edited by: Rambo Prasad ]

A Bhattacharya
Ranch Hand

Joined: Oct 22, 2007
Posts: 125

posted

0

Yes it can have more than 3; the question is to find teh minimum no of stripes required to be able to form the required no of flags, in this example 10. I was demonstrating (as an intermediate step in the solution) how we might find the flags that can be formed using 3 stripes.

Hmm... graphs are a fundamental tool for most of Computer Science problems (or they're my hammer ) One possible solution is create a graph where the nodes are the stripe colors and the arcs are the allowed pair combinations. Now the problem is to find the shortest n paths (=number of flags) visiting each node one time at most (i.e using each color zero or one time). I need to assume that you have a known number of colors and the order matters (i.e. YB is a different flag than BY). If flags can have 1 stripe (just one color in the whole flag) you start counting the paths of size 1 (will be the number of nodes), otherwise, start with the paths of length 2. Doesn't seem to be expensive as the number of colors is low, but probably more optimizations can be done (i.e. the longest path from a node will give [sumatory of path length] different flags). What do you guys think?

(I realized you can repeat colors as long as they're not adjacent... this removes the condition that each vertex must be visited only once at most... doesn't seem to affect the algorithm, though) [ May 15, 2008: Message edited by: Gabriel Claramunt ]