UVa - 11125 - Arrange Some Marbles

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.

HackerRank > Interview Preparation Kit > Graphs > Matrix

Link to problem statement on HackerRank

We are given a tree than some of it's nodes has a machine on it, we have to cut the some edges so that no two of them have a path to each other. The cost of the edges we cut must be minimized.

First Approach : Disjoint Set
What happened in my mind : I looked at the final state, how does it look? We have a forest and each tree in this forest has exactly one node with a machine in it. (You can prove that each tree in this forest has exactly one tree, not zero, by proof of contradiction) Some edges have been cut in order to help us get to this state, right? The total cost of these edges must be minimized. This was when I thought of disjoint-set data structure. As you see we have some sets that no two of them have common nodes. (This is also like a maximum spanning tree, that from some point if two end-points of an edge have a machine in their component we will not do that) So we sort the edges in decreasing order to their cost and start merging them, when two endpoints of an edge have a machine in their component we skip that and add that to the answer.
The proof that this gives us the optimum answer is most like the proof that Kruskal algorithm gives Minimum Spanning Tree.

For more details look at my code on github.



Second Approach : DP on Tree
When I see a tree it's always tempting to hang it from some node and make it a rooted tree :D then compute something for the subtree starting from each node. In this case after some thinking I decided to define this value for each node f(node, machineCount, parent) means we have a rooted tree with node being the root of it, we want to do what the problem has asked for the subtree starting from node (cutting some edges in the subtree starting from node, so that no two machine nodes have a path to each other) and after paying that cost, if we grab node and take it, the component connected to it has exactly machineCount number of machines in it. Here machineCount can be 0 or 1, meaning the component connected to node must have exactly 0 or exactly 1 machines.
According to my experience in these questions (dp on tree), defining what needs to be returned is the key point. (exactly 0 or 1 machines in this case, and what 0 or 1 machine means?)
Now let's check different situations when calculating f(node, machineCount)

The very base case here is when machineCount = 0 and node has a machine in it, the answer to this would be Infinity, because we can't remove that machine, and whatever we cut from the subtree of node, when we grab node, it has at least 1 machines in it.

Now let's calculate this value
zeroMachineCost : (no machine in the subtree of tree)

zeroMachineCost = SUM ( min ( f(child, 0), f(child, 1) + edge(node, child) )  ) for all children of node

We have calculated the cost for when the component connecting to node has zero machines in it.

if ( machineCount == 1 && hasMachine[node] ==  true ) return zeroMachineCost;
if( machineCount == 0 && hasMachine[node] == false ) return zeroMachineCost;

The only case that remains is when hasMachine[node] is false, and machineCount == 1,
which means we need to take one machine from one of subtrees of node.



This part calculates that, as you see we assume the answer is Infinity (because node may has no children), then one by one for each child we deduct the part that had been added to zeroSum previously and add a component with one machine starting at child.

Take a look at my code on github for more details.