An exercise - cats in a hall

Question

There are many mice in the hall of length n. An array of length n is given where a[i] describes the number of mice between the i-th and i+1-th meter of the hall.

You have k cats. Each cat can guard a connected fragment of the hall. The guarded segments may not intersect. Some segments may be left unguarded.

If a cat guards a segment from the i-th to the j-th meter of the hall, where s = a[i] + a[i+1] + ... + a[j-1] mice reside, it will catch max(s-(j-i-1)^2, 0) mice.

What is the maximal number of mice that can be caught?

I suspect that the algorithm should use dynamic programming, but I have no idea how to solve it.

I don't have any code since I don't have any algorithm yet (I try to create it), but my thoughts so far.

We can't use induction wrt to the number of cats. This could produce false results. For example if there's one segment where one cat can catch 7 mice and two disjoint places where a cat can catch 2 mice, then we'll get nothing from the result for one cat.

So we should solve the problem for a subsegment and calculate the answer from the answer for the subsegment.

But I don't know how to proceed further.

Answer 1

A cat has better effectiveness of protecting a smaller area, than protecting a bigger area.

Proof: if i > j |j-i-1| < |j-i| => (j-i-1)^2 < (j-i)^2 => s-(j-i-1)^2 > max(s-(j-i)^2, 0) => max(s-(j-i-1)^2, 0) >= max(s-(j-i)^2, 0) => max(s-(j-i-1)^2, 0) >= max(s-((j + j')-i-1)^2, 0) => A cat is more effective on smaller areas.

Since a cat is effective in smaller areas, if we use more cats, then a cat on average will protect smaller areas, so, we can arrange the cats in a more effective manner if we use more cats.

This means that all k cats should be used. With this, we have already excluded all cases when not all cats are used. Ok, except the case when there are more cats than meters, but that is a trivial case, when you should put a cat/meter to guard it.

So, when k <= n, we use all cats. The problem thus is partitioning. You want to find the optimal partitioning, with the heuristic described by the formula. This is very similar to chess.

Explanation: In chess, you have a starting position. You want to find the best move, so you calculate its main variations and variations that are sub-optimal are not calculated into the maximum depth. In your problem, you need to find the right move (positioning a cat to a given sector), just like in chess, but with different heuristics. The heuristics should be something, which is based on the depth (number of cats already positioned) and effectiveness (number of mice potentially caught / number of mice totally in the covered sector).

For instance, Alpha-Beta pruning is relatively easy to implement and according to this post, it has a complexity of O(b^(d/2)) in best case scenario. You can do further reading here.

EDIT: While the problem can be easily solved by Alpha-Beta pruning, RBarryYoung is right in his comment that the problem can be approached without modelling it like a game where an adversary moves, while modelling it like that is possible, since the "most negative answer" can be seen as the only answer, which increases the number of partitions needed and decreases the number of cats which can be used.

Answer 2

I would start by generating all possible single placements of cats (a placement is defined by the set of 1m-segments covered, for instance starting at meter 3 and ranging 2 meters from there), calculate their respective value (number of mice caught in the respective segment) and then find a selection of k (number of cats) such placements so that the placements do not overlap and the value is maximized. Since the overlap can be checked easily given two segments you don't have to construct a lookup table.

As Lajos-Arpad points out in his answer, it is always better to use all the cats you have available because there is a penalty for wider ranges/longer segments. When you can split a range in two using another cat, the total value always increases.

Optimizations:

• Eliminate placements spanning too many columns. Example: If your hall is 4 meters long and you have 3 cats, you don't place cats on 3 meter ranges.

• Eliminate placements that are dominated by other placements. If placement A spans a superset of the columns spanned by placement B but does not yield more mice, dismiss A. This can reduce the number of possible placements dramatically.

Implementation: The problem in this form lends itself well to 0-1 integer linear programming. The vector x to be found has length p (number of placements) and contains 1 or 0 at each position depending on whether the placement is in the solution or not. The value of a solution is trivially given by the sum of values of the placements. The constraints: Number of 1s is <= k and you have a constraint for each meter in your hall that prevents that two placements covering the respective meter are selected.

Another alternative is that you enumerate all possible combinations of placements and pick the best one (brute force). You can of course optimize this further. For instance you can sort the placements and pick the most valuable ones first. Keep track of the best solution so far and stop generating sub-selections when you see your current best solution cannot be bet in this branch.

Example: You have already selected 2 placements with a total value of 30, and you are to pick 3 more placements out 10 placements with the following values:

17, 10, 8, 4, 4, 3, 2, 1, 1, 1

If your current optimal solution has value 70 you can stop right here and backtrack. Regardless of which three placements you would pick, you would never add more value than 35 (sum of first three) but you need at least 41.