Maximization problem in 1D
Problem:
We are given n points on a line numbered from 1..n and also the colors which we can use to connect any two adjacent points. 1 can be connected to 2 only no other points and 2 to 3 only and so on. There can be either one choices or more choices for connecting two points by choosing different colors of available choice. Now we need the maximum count of number of pairs of neighbouring edge of different color.
Any one can tell the approach to solve this problem?
We are given n points on a line numbered from 1..n and also the colors which we can use to connect any two adjacent points. 1 can be connected to 2 only no other points and 2 to 3 only and so on. There can be either one choices or more choices for connecting two points by choosing different colors of available choice. Now we need the maximum count of number of pairs of neighbouring edge of different color.
Any one can tell the approach to solve this problem?
There can be either one choices or more choices for connecting two points by choosing different colors of available choice.
Ignoring the translator failures for a moment, that directly contradicts 1 to 2, 2 to 3.
Also, there is no relationship defined between numbers and colors. Should I just assume that 2 is black and 7 is purple? that makes the answer 37, I believe.
Ignoring the translator failures for a moment, that directly contradicts 1 to 2, 2 to 3.
Also, there is no relationship defined between numbers and colors. Should I just assume that 2 is black and 7 is purple? that makes the answer 37, I believe.
Last edited on
@jonin...
Lets say 1 and 2 can join with option of blue and red color
2 and 3 can join with option of blue and white color
3 and 4 can join with option of white color only.
This shows that only adjacent points can be joined only and there will be certain choices of color to join adjacent points.
Now to maximize the cost of path from 1 to 4 we should find a path with the maximum possible transitions of colors.
So optimal answer will be choosing
Red for 1-2
Blue for 2-3
White for 3-4.
This can be done using backtraking but i need some efficient approach.
Lets say 1 and 2 can join with option of blue and red color
2 and 3 can join with option of blue and white color
3 and 4 can join with option of white color only.
This shows that only adjacent points can be joined only and there will be certain choices of color to join adjacent points.
Now to maximize the cost of path from 1 to 4 we should find a path with the maximum possible transitions of colors.
So optimal answer will be choosing
Red for 1-2
Blue for 2-3
White for 3-4.
This can be done using backtraking but i need some efficient approach.
ok. hmm.
still thinking.
so far looking at …
find all the connections with 1 possible color and assign them.
next, iteratively find connections with next to a solved connection and solve those. Do this until nothing is solved in an iteration. You know what you have solved, so you don't have to search, you can keep a list and directly access/locate the next item each time.
the question is whether that actually works :)
on yours it would do the last one first, set to white.
then it would do 2-3, see that white is already on one side so it can't be white, set to blue. Then it does 1-2, sees blue to the side, picks red. Your example does not really show it but you would look at what is possible on the unsolved side to choose. If 2-3 had blue, white, red, green, it would toss out white, blue, and red and pick green (1-2 can't be green). The logic here is critical to success, but I am not 100% sure what the rules are.
But does it always work? Not sure yet.
still thinking.
so far looking at …
find all the connections with 1 possible color and assign them.
next, iteratively find connections with next to a solved connection and solve those. Do this until nothing is solved in an iteration. You know what you have solved, so you don't have to search, you can keep a list and directly access/locate the next item each time.
the question is whether that actually works :)
on yours it would do the last one first, set to white.
then it would do 2-3, see that white is already on one side so it can't be white, set to blue. Then it does 1-2, sees blue to the side, picks red. Your example does not really show it but you would look at what is possible on the unsolved side to choose. If 2-3 had blue, white, red, green, it would toss out white, blue, and red and pick green (1-2 can't be green). The logic here is critical to success, but I am not 100% sure what the rules are.
But does it always work? Not sure yet.
Last edited on
Topic archived. No new replies allowed.