PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
A naive DP solution to this problem solves it in O(N * 2^N). Store the state of the targets in a bitmask, and for each of the possible 2^N states, simulate each of the possible outcomes from firing at each of the N targets, then choose the one with the lowest expected number of shots. Since it’s possible to hit a target that’s already been hit, the expected number of shots required is (1+sum(P(T) * E(T)))/(1-Q), where P(T) is the probability of hitting target T (and T hasn’t been hit yet), E(T) is the expected number of additional shots needed if target T is hit, and Q is the probability of hitting a target that’s already been hit or missing completely (if Q is 1, the shot is useless).
The solution can be improved by noticing that once 2 adjecent targets have been hit, the remaining targets to the left of these targets can be considered indepently of those to the right, since no single shot could ever have the potential to effect both. The number of states where no 2 adjacent targets have been hit is O(φ^N), where φ is (sqrt(5)+1)/2, the golden ratio. The total runtime is thus O(N * φ^N).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.