algorithm - An exercise - cats in a hall -

there many mice in hall of length n. array of length n given a[i] describes number of mice between i-th , i+1-th meter of hall.

you have k cats. each cat can guard connected fragment of hall. guarded segments may not intersect. segments may left unguarded.

if cat guards segment i-th j-th meter of hall, s = a[i] + a[i+1] + ... + a[j-1] mice reside, catch max(s-(j-i-1)^2, 0) mice.

what maximal number of mice can caught?

i suspect algorithm should use dynamic programming, have no idea how solve it.

i don't have code since don't have algorithm yet (i try create it), thoughts far.

we can't use induction wrt number of cats. produce false results. example if there's 1 segment 1 cat can catch 7 mice , 2 disjoint places cat can catch 2 mice, we'll nothing result 1 cat.

so should solve problem subsegment , calculate answer answer subsegment.

but don't know how proceed further.

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

proof: if > 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) => cat more effective on smaller areas.

since cat effective in smaller areas, if use more cats, cat on average protect smaller areas, so, we can arrange cats in more effective manner if use more cats.

this means all k cats should used. this, have excluded cases when not cats used. ok, except case when there more cats meters, trivial case, when should put cat/meter guard it.

so, when k <= n, use cats. problem partitioning. want find optimal partitioning, heuristic described formula. this similar chess.

explanation: in chess, have starting position. want find best move, calculate main variations , variations sub-optimal not calculated maximum depth. in problem, need find right move (positioning cat given sector), in chess, different heuristics. heuristics should something, based on depth (number of cats positioned) , effectiveness (number of mice potentially caught / number of mice totally in covered sector).

for instance, alpha-beta pruning relatively easy implement , according this post, has complexity of o(b^(d/2)) in best case scenario. can further reading here.

edit: while problem can solved alpha-beta pruning, rbarryyoung right in comment problem can approached without modelling game adversary moves, while modelling possible, since "most negative answer" can seen answer, increases number of partitions needed , decreases number of cats can used.