D. Kevin’s Problem
Author: Suhendry Effendy.
Prepared by: Suhendry Effendy, Felix Halim.
Problem: D – Kevin’s Problem
This problem asked you to count how many permutation of N integers such that a certain integer is selected by Kevin’s strategy (described in the problem statement). This is a pure counting problem.
Originally, the expected solution for this problem has O(N3) time complexity. However, when we prepared the problem, we found a better solution which has O(N2) time complexity, but we did not increase the difficulty of this problem, hence an O(N3) solutions are still accepted.
I’m not going to discuss the solution here as it’s quite messy (thus, hard to explain). I don’t think there is any trick to the solution, you just have to derive the solution by combining nCk and factorial (i.e. counting stuffs).