Link to pdf on UVa OJ
There are at most 4 colors of marbles that we need to put in a row. Adjacent marbles with the same color form a group. The conditions for putting the marbles is that adjacent groups must not have the same size or the same color. The first group and the last group also are considered adjacent.
What happened on my mind : After I read the problem statement, I looked at the number of colors, just 4, looked at limit for each color, only 7, I thought to myself, ok I'll do a backtrack and apply the rules and we are done ^_^. Then I looked at the number of test cases, 3000. Oh, that may not work (it may still work, but it made me think a little bit more) I thought a lot of these states have common subproblems, oh dynamic programming? What should the state be? In a Dynamic Programming solution, the first thing is to define the state, which needs a little explore and educated guessing based on your understanding of the problem. Happily I found the state soon. What should be taken into account for each state? Remaining number of each color, and last group size, and last group color, because when we are trying to put a group we must check it not to be the same as last group size and color. Oh that's not enough, we need to include the first group size and color, because when we have put the last group in the row, it is ok if it's not equal to the first group, ok add it to the state as well.
If we call remaining number of each color by A, B, C & D then I came up with this :
f( A, B, C, D, firstSize, firstColor, lastSize, lastColor ), after guessing the state we should count them.
number of states = 8 * 8 * 8 * 8 * 4 * 5 * 4 * 5 = 1.7 million states, good.
Then calculate the recurrence and cost of calculating each state based on it's subproblems.
For each state we have to choose between 4 colors and take at most 3 marbles from that, so 12. That's great.
What is the base case? If no marbles are remaining, we check first group and last group.
The only thing not supported in this is when there is only one color (because then the first group and last group would have the same color and I'll return 0), or there are no marbles at all. These cases must be handle separately.
For more details please take a look at my code on github.
There are at most 4 colors of marbles that we need to put in a row. Adjacent marbles with the same color form a group. The conditions for putting the marbles is that adjacent groups must not have the same size or the same color. The first group and the last group also are considered adjacent.
What happened on my mind : After I read the problem statement, I looked at the number of colors, just 4, looked at limit for each color, only 7, I thought to myself, ok I'll do a backtrack and apply the rules and we are done ^_^. Then I looked at the number of test cases, 3000. Oh, that may not work (it may still work, but it made me think a little bit more) I thought a lot of these states have common subproblems, oh dynamic programming? What should the state be? In a Dynamic Programming solution, the first thing is to define the state, which needs a little explore and educated guessing based on your understanding of the problem. Happily I found the state soon. What should be taken into account for each state? Remaining number of each color, and last group size, and last group color, because when we are trying to put a group we must check it not to be the same as last group size and color. Oh that's not enough, we need to include the first group size and color, because when we have put the last group in the row, it is ok if it's not equal to the first group, ok add it to the state as well.
If we call remaining number of each color by A, B, C & D then I came up with this :
f( A, B, C, D, firstSize, firstColor, lastSize, lastColor ), after guessing the state we should count them.
number of states = 8 * 8 * 8 * 8 * 4 * 5 * 4 * 5 = 1.7 million states, good.
Then calculate the recurrence and cost of calculating each state based on it's subproblems.
For each state we have to choose between 4 colors and take at most 3 marbles from that, so 12. That's great.
What is the base case? If no marbles are remaining, we check first group and last group.
The only thing not supported in this is when there is only one color (because then the first group and last group would have the same color and I'll return 0), or there are no marbles at all. These cases must be handle separately.
For more details please take a look at my code on github.
No comments:
Post a Comment