Editorial for COCI '06 Contest 1 #5 Bond

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

There are $N!$ ~N!~ ( $N$ ~N~ factorial) different ways of assigning missions to the agents. For $N=20$ ~N=20~, this number is too large to go through all of them and find the best.

Observe that, if we have already assigned agents $1$ ~1~ through $X$ ~X~ to some $X$ ~X~ missions, then the probability of the remaining missions being successfully completed does not depend on exactly which of the $X$ ~X~ agents were assigned to the $X$ ~X~ missions. This fact allows us to use dynamic programming to solve the task.

The state in the search will be the subset of missions that have been assigned (implemented using a bitmask), which also contains the number of missions assigned so far ( $X$ ~X~).

Space complexity: $\mathcal O(2^N)$ ~\mathcal O(2^N)~

Time complexity: $\mathcal O(N 2^N)$ ~\mathcal O(N 2^N)~

Comments

There are no comments at the moment.