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)$ ~\mathcal{O}(2^N)~ or $\mathcal{O}(N!)$ ~\mathcal{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)$ , 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)$ ~\mathcal{O}(N^2)~

Comments

There are no comments at the moment.