Solution to 2010 ACM Problem: Castles

Question

Post your best solutions! You can find the full problem description and examples here: ACM 2010 problems (pdf)

You have a set of castles connected by roads, and you want to conquer all the castles with the minimum number of soldiers. Each castle has three properties: the minimum number of soldiers required to take it, the number of soldiers that will die taking it, and the number of soldiers that must be left behind to hold it.

There is exactly one path between any two castles (the roads form a tree). You can pick any castle as the first target, but you must follow the roads afterward. You can only travel a road twice. Your mobile army must stay in one group.

Answer 1

I would solve this this way:

Bruteforce all starting castles (100 max) For each starting castle: fill up array

need[i] and cost[i] means that when you go from chosen starting point to i, and trying to conqure subtree starting at i, you would need at least need[i] solders and cost[i] solders would die.

min_solder_to_attack_castle[i] goes from input file.

Obviously, need[] and cost[] values are obvious for "terminal" castles. Then, for each castle which have known need[] and cost[] values for all "childs" you calculate need and cost for this castle this way:

cost[i] = sum(cost[childs])

Getting need[i] is the tricky part: we know it's somewhere between max(min_solder_to_attack_castle[all childs]), and max(min_solder_to_attack_castle[all childs])+max(cost[all childs]). Trying all variants would cost us (number_of_childs)! and potentially be n!, and probably optimizations would help here, here is where I stopped for now.

Answer 2

I would solve this in reverse - you want to have as few men "wasted" after taking the last castle as possible. Since we can't pass through a castle without taking it, we will obviously end at a "leaf" castle.

It is straightforward to walk backwards from all leaf castles to determine the total number of men "wasted" on each subtree - then it's simply a matter of walking the subtrees in the right order.

Elementary, my dear Watson.

Answer 3

The first thing to realize is that, as far as the numbers go, there is no difference between soldiers lost and soldiers left behind. So we can reduce the castle properties to soldiers lost and required.

The second thing to realize is that if you go down a branch of the tree, you must complete the whole branch for returning. This allows us to reduce the entire branch to a single "mega castle" with aggregate soldiers required and lost.

So, assuming we can compute the costs of branches, we're left with two problems: where to start, and how to choose which branch to descend first. I'm just going to brute force the start position, but it might be possible to do better. Choosing which branch to descend is a bit harder. The number of soldiers of lost is trivial, but the number required is not. There are n! possibilities, so we can't just try them all.

Instead of thinking about how many soldiers are lost/required at each castle, I'm going to go backwards. Start with 0 soldiers, and add them when you attack a castle, ensuring we end up with at least the required amount. There are two cases: either there is a castle which we meet the requirement for, or there is not. If there is, (un)do that castle (this is optimal, because we used the minimum number of soldiers). If there isn't, add an additional soldier and try again (this is optimal, because we must add a soldier to continue). Now it should become obvious: we want to (un)do castle with requirements closest to the number lost first. Just sort by (required minus lost) and that's your order.

So the final algorithm looks like this:

• Brute force the starting point
• Recursively reduce branches into aggregate castles (memoize this result, for the other starting points)
• Visit branches in descending (required minus lost) order.

The running time is O(n * c^2 * lg(c)), where n is the number of castles and c is the maximum connectivity of any single castle. This worse because there are at most n*c 'branches', and a node takes at most c*lg(c) time to evaluate after its branches have been evaluated. [The branches and nodes are computed at most once thanks to memoization]

I think it's possible to do better, but I'm not sure how.