Editorial for DMOPC '21 Contest 5 P3 - Permutations & Primes

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: 4fecta

Subtask 1

First of all, let's see how we can determine who the winner is for any arbitrary permutation of heights. It turns out this is a relatively simple dynamic programming problem. If we let $dp[i] := 1$ ~dp[i] := 1~ if Nene-Robo starts at the building with height $i$ ~i~ and the player making the move wins and $0$ ~0~ otherwise, then we can iterate the buildings in increasing order of height to calculate higher DP states. Note that for each building we only need to consider transitioning to buildings that are a prime distance away. Since there are $\mathcal{O}(N/\ln N)$ ~\mathcal{O}(N/\ln N)~ prime numbers under $N$ ~N~ and $N$ ~N~ states to compute, this DP runs in a total of $\mathcal{O}(N^2/\ln N)$ ~\mathcal{O}(N^2/\ln N)~. This may seem scarily large, but the computational time is much smaller in practice if we break out of the transition loop as soon as we find a winning possibility.

A simple way to leverage the work above into a solution is to loop through all permutations of $1, \dots, N$ ~1, \dots, N~ in lexicographically increasing order, stopping and outputting the permutation as soon as we find one with $dp[N] = 1$ ~dp[N] = 1~. Is the time complexity of this $\mathcal{O}(N!N^2/\ln N)$ ~\mathcal{O}(N!N^2/\ln N)~? No, in fact, it is still $\mathcal{O}(N^2/\ln N)$ ~\mathcal{O}(N^2/\ln N)~ per test case! We'll see why in the next section.

Time Complexity: $\mathcal{O}(TN^2/\ln N)$ ~\mathcal{O}(TN^2/\ln N)~

Subtask 2

Why was our previous solution so fast? If we print the answer for some values of $N$ ~N~, we will see that the answer is almost always $1, 2, \dots, N-2, N-1, N$ ~1, 2, \dots, N-2, N-1, N~. If not, it is almost always the second smallest permutation $1, 2, \dots, N-2, N, N-1$ ~1, 2, \dots, N-2, N, N-1~. If neither of these are winning for Nene, then we can prove that the next smallest permutation $1, 2, \dots, N, N-2, N-1$ ~1, 2, \dots, N, N-2, N-1~ will always be winning for Nene. There is a simple proof of this fact which will be left as an exercise to the reader. Now that we have these observations, we can instead precompute the DP array only for the identity permutation $1, 2, \dots, N-2, N-1, N$ ~1, 2, \dots, N-2, N-1, N~. After all, the set of possible moves for $1, 2, \dots, N-2, N, N-1$ ~1, 2, \dots, N-2, N, N-1~ is the exact same as the set of possible moves for $1, 2, \dots, N-2, N-1$ ~1, 2, \dots, N-2, N-1~. This allows us to determine the answer to each test case in $\mathcal{O}(1)$ ~\mathcal{O}(1)~ time.

Time Complexity: $\mathcal{O}(N^2/\ln N + TN)$ ~\mathcal{O}(N^2/\ln N + TN)~

Comments

There are no comments at the moment.