Editorial for COCI '19 Contest 5 #5 Zapina

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.

The first subtask can be solved by simply checking if there is at least one happy programmer for each possible assignment of tasks. There are $N^N$ $N^{N}$ possible task assignments in total.

The second subtask can be solved using the inclusion-exclusion principle. If with $a(S)$ $a (S)$ , where $S \subseteq \{1, 2, \dots, N\}$ $S \subseteq {1, 2, \dots, N}$ , denotes the number of task assignments in which all programmers from set $S$ $S$ are happy, then the number of good assignments is equal to

$\displaystyle \sum_{S \subseteq \{1, 2, \dots, N\}} (-1)^{|S|+1} a(S)$ $\sum_{S \subseteq {1, 2, \dots, N}} (- 1)^{| S | + 1} a (S)$

Let $S = \{s_1, s_2, \dots, s_k\}$ $S = {s_{1}, s_{2}, \dots, s_{k}}$ . If $s_1+s_2+\dots+s_k > N$ $s_{1} + s_{2} + \dots + s_{k} > N$ then obviously $a(S) = 0$ $a (S) = 0$ . Otherwise, it holds

$\displaystyle a(S) = \binom{N}{s_1} \binom{N-s_1}{s_2} \dots \binom{N-(s_1+s_2+\dots+s_{k-1})}{s_k} (N-k)^{N-(s_1+s_2+\dots+s_k)}$ $a (S) = (\binom{N}{s_{1}}) (\binom{N - s_{1}}{s_{2}}) \dots (\binom{N - (s_{1} + s_{2} + \dots + s_{k - 1})}{s_{k}}) (N - k)^{N - (s_{1} + s_{2} + \dots + s_{k})}$

Binomial coefficients can be precomputed using the well-known relation $\binom{n}{k} = \binom{n-1}{k-1}+\binom{n-1}{k}$ $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ in time complexity $\mathcal O(N^2)$ $O (N^{2})$ .

The total time complexity is $\mathcal O(N 2^N)$ $O (N 2^{N})$ .

Finally, the third subtask can be solved using dynamic programming. Let $dp(n, k)$ $d p (n, k)$ be the number of assignments of $k$ $k$ tasks to $n$ $n$ programmers among which there is at least one happy programmer. There are two possibilities – we can give the $n^\text{th}$ $n^{th}$ programmer exactly $n$ $n$ tasks (and make him happy), or we won't. In the first case, if $k \ge n$ $k \geq n$ , the number of ways equals

$\displaystyle \binom{k}{n} (n-1)^{k-n}$ $(\binom{k}{n}) (n - 1)^{k - n}$

and in the other it equals

$\displaystyle \sum_{0 \le i \le k, i \ne n} \binom{k}{i} dp(n-1, k-i)$ $\sum_{0 \leq i \leq k, i \neq n} (\binom{k}{i}) d p (n - 1, k - i)$

The total time complexity is $\mathcal O(N^3)$ $O (N^{3})$ .

Comments

There are no comments at the moment.