Editorial for SAC '22 Code Challenge 5 P3 - Querying Presents

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: maxcruickshanks

Subtask 1

It suffices to loop through every possible permutation of students and increment a counter by 1 if the current permutation assigns every number to a different number than its index.

Time Complexity: \mathcal{O}(N!)

Subtask 2

Realize that (through either OEIS or previous problems) this is counting derangements, which has the following recurrence:

!n = (n-1)(!(n-1) + !(n-2)) for n \ge 2, where !0 = 1 and !1 = 0

Compute this for each query (or precompute for N \le 10^6) while \bmod 10^9 + 7.

Time Complexity: \mathcal{O}(\sum_{i=1}^T N_i)


There are no comments at the moment.