Editorial for Back To School '18: An FFT Problem

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.

Author: richardyi25

Subtasks 1 and 2 are intended to reward brute force solutions.

Time Complexity: $\mathcal{O}(2^N)$ $O (2^{N})$ or $\mathcal{O}(N!)$ $O (N!)$

Subtask 3 is troll.

The intended solution for Subtask 4 was dynamic programming. Let $A[k][n]$ $A [k] [n]$ represent the sum of all combinations of size $k$ $k$ for the first $n$ $n$ books.

Another perspective to take is that this problem is equivalent to finding the coefficients of the expansion of $(x + a_1)(x + a_2)(x + a_3) \dots (x + a_n)$ $(x + a_{1}) (x + a_{2}) (x + a_{3}) \dots (x + a_{n})$ , except the leading coefficient, which is always $1$ $1$ . This can be proven with Vieta's formulas. The most straightforward implementation of this method yields the same recurrence relation as the first method.

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

Comments

There are no comments at the moment.