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?
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 ]
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 ]