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) or \mathcal{O}(N!)

Subtask 3 is troll.

The intended solution for Subtask 4 was dynamic programming. Let A[k][n] represent the sum of all combinations of size k for the first 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. 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)


Comments

There are no comments at the moment.