Editorial for Nhiệm vụ Malnar

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.

Authors: Yuuki

Subtask 1:
Subtask đầu tiên có thể được giải bằng cách kiểm tra xem có ít nhất một lập trình viên hạnh phúc (happy programmer) với mỗi phân công nhiệm vụ hay không. Có tổng cộng $N$ cách phân công nhiệm vụ.

Subtask 2:
Ta có thể được giải bằng nguyên lý bù trừ (Inclusion-Exclusion Principle). Gọi $a(S)$ , với $S \subseteq \{1, 2, \dots, N\}$ , là số cách phân công nhiệm vụ mà tất cả lập trình viên trong tập $S$ đều hạnh phúc. Khi đó, số cách phân công "tốt" (good assignments) được tính theo công thức:

$\text{Tổng} = \sum_{S \subseteq \{1, 2, \dots, N\}} (-1)^{|S| + 1} a(S)$

Giả sử $S = \{s_1, s_2, \dots, s_k\}$ :

Nếu $s_1 + s_2 + \cdots + s_k > N$ , thì rõ ràng $a(S) = 0$ .
Nếu không, thì:

$a(S) = \binom{N}{s_1} \binom{N - s_1}{s_2} \cdots \binom{N - (s_1 + s_2 + \cdots + s_{k-1})}{s_k} \cdot \frac{(N - k)!}{(N - (s_1 + s_2 + \cdots + s_k))!}$

Ghi chú: Tổ hợp $\binom{n}{k}$ có thể được tiền xử lý trước bằng quan hệ truy hồi:

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Độ phức tạp của bước tiền xử lý là $O(N^2)$ , và độ phức tạp tổng quát cho toàn subtask này là $O(N^2 \cdot 2^N)$ .

Subtask 3:
Ta có thể được giải bằng quy hoạch động (Dynamic Programming). Gọi dp(n,k) là số cách phân công k nhiệm vụ cho n lập trình viên, trong đó có ít nhất một lập trình viên hạnh phúc. Có hai trường hợp:

Giao đúng n nhiệm vụ cho lập trình viên thứ n (làm cho lập trình viên này hạnh phúc). Khi đó, nếu $k \ge n$ , số cách được tính là:

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

Không giao đúng n nhiệm vụ cho lập trình viên thứ n. Khi đó:

$\textit{dp}(n,k) = \sum_{0 \le i \le k, i \ne n} \binom{k}{i} \cdot \textit{dp}(n-1, k-i)$

Độ phức tạp: Tổng độ phức tạp là $O(N^3)$ .

Comments

There are no comments at the moment.