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)$ $O (2^{N})$

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

Comments

There are no comments at the moment.