CAPTCITI Approach

Can anyone explain me how to solve Snakes capturing the Mongoose Cities problem ?

2 Likes

I approached this problem through DP. I had 2 different DP’s DPa[node] and DPb[node].

DPa[node] = cost of conquering subtree rooted at node assuming that the parent of the node was already conquered
DPb[node] = cost of conquering subtree rooted at node assuming that the parent of the node was not yet conquered and will be conquered after conquering this node.

For a lead node: DPa[leaf] = 0, because if its parent has been conquered then even this will be conquered.
DPb[leaf] = p[i] as the only way to conquer this would be to send troops at day 0.

For non-leaf node:

buycost of node = (sum of DPa[u] for u children of node) + p[node]

DPa[node] will be the cost of conquering P[node] - 1 children before this node and the rest after this.
We can easily calculate this with the help of a difference array between DPb and DPa. DPa[node] is the minimum between this val and the buycost.

DPb[node] will be the cost of conquering p[node] children before this node and the rest after. DPbb[node] is the minimum between this val and the buycost.

The only difference between A and B is that in A we conquer P[i] - 1 nodes while in B we conquer P[i] nodes.

Final answer is min(DPa[0], DPb[0])

3 Likes

This is what I came up with as well :slight_smile:

Link to code please…