Fewest Cameras to Watch Everything
A camera placed on a node watches that node and every node one edge away from it. Print the fewest cameras that leave NO node unwatched.
4 nodes, edges 1-2 1-3 3-4 -> 2
5 nodes in a star -> 1 a camera at the centre sees everything
## Not the same as 567
Problem 567 guarded every EDGE; this guards every NODE. The difference matters, and the answers really do differ: on the path of eight nodes, 567 answers 4 and this answers 3.
That is worth checking before writing any code, because the two problems look alike enough that the 567 recurrence is a tempting thing to reuse.
## Two numbers are not enough
The natural attempt keeps take and skip as before. It fails, because "no camera on u"
is not one situation but two:
· u has no camera, but a child does, so u is already watched
· u has no camera and no child has one, so u still needs its PARENT to hold one
The parent must distinguish those, because the second one obliges it. Two numbers cannot carry that, so the state has three values:
has[u] = fewest cameras in u's subtree, with a camera on u
cov[u] = fewest, no camera on u, but u is watched by a child
unc[u] = fewest, no camera on u, and u is not watched at all
## The recurrence
With a camera on u, every child is watched by u itself, so a child may be in any state:
has[u] = 1 + sum over children c of min(has[c], cov[c], unc[c])
For unc[u], no child may hold a camera, and every child must already be watched from below:
unc[u] = sum over children c of cov[c]
cov[u] is the interesting one. Each child contributes min(has[c], cov[c]), but at least
ONE child must actually be in has. Take the plain minimum first, and if no child happened to
choose has, pay the cheapest upgrade:
cov[u] = sum of min(has[c], cov[c])
+ (0 if some child already chose has,
else min over children of has[c] - cov[c])
The answer is min(has[root], cov[root]), because the root has no parent and so may not be
left uncovered.
## The base case
A leaf has no children. It can hold a camera, for a cost of 1, or hold none and be uncovered,
for 0. It cannot be covered from below, so cov at a leaf is IMPOSSIBLE, not zero.
Setting it to zero is the single most common bug here, and it produces answers that are too small. Use a large sentinel and make sure adding to it does not overflow.
## Boundaries
A single node needs one camera, since there is no parent to cover it. That is the case where
cov[root] is impossible and has[root] is the only choice.
## Cost
Time O(n). Space O(n).