PROBLEM LINK:
Editorialist: Suhash Venkatesh
DIFFICULTY:
HARD
PREREQUISITES:
DP, Math
PROBLEM:
Given a 2 x N grid, you have to fill it with numbers from the range [1…K] such that there are no one or two cycles. Find the number of ways in which this can be done.
1 ≤ N ≤ 105
0 ≤ K ≤ 1018
EXPLANATION:
Simpler version:
Find the number of derangements of [1…N] such that there are no one or two cycles.
This is equivalent to the initial problem if N == K. This can be solved easily using the following recurrence:
f(n) = (n-1) * f(n-1) + (n-1) * (n-2) * f(n-3)
, where f(1) = 0, f(2) = 0, f(3) = 2.
It can be found on OEIS too, A038205. This can be derived using a similar derivation to number of derangements of N numbers. But sadly, this doesn’t help much for the harder version of the problem (K > N).
Actual version:
It is clear that if K < N, then the answer is 0. Hence, going forward we can assume that K >= N. For the first row of the grid, we can choose any N numbers from the given K numbers, and permute them in N factorial ways. Hence, number of ways = KCN * N! = KPN.
Here, KCN = K! / [N! * (K-N)!] and KPN = K! / (K-N)!
From now on, we can assume that the first row is filled with numbers [1…N] in order, from left to right (We can multiply the final answer by KPN). Now, we have to fill the second row with no.s [1…K], such that no one or two cycles are formed. Let’s divide [1…K] into 2 buckets:
Bucket 1: Contains no.s [1…N] => N numbers.
Bucket 2: Contains no.s [N+1…K] => (K-N) numbers.
An important property of bucket 2 is that, none of the no.s in this bucket will ever create a cycle. Let’s first try to fill slot 1 (Assume slots are numbered with [1…N] from left to right). We can either fill it with a no. from bucket 1 (or) a no. from bucket 2. If we choose a number from bucket 2, let’s say N+i (1 ≤ i ≤ K-N), then we know that the number 1 can occur at any slot since it will never create a cycle. We’ll end up with 1 => N+i, and any of the slots [2…N] can now have the number 1, without creating any cycle.
Key Observation:
Note that the size of bucket 2 never changes, and is always = (K-N). In the above description, we can re-label the number 1 as N+i and push it into bucket 2. Hence, even after this step - bucket 2 will contain exactly (K-N) no.s. We haven’t covered the case where we choose a no. from bucket 1. This is not important right now, since this would anyways not change the size of bucket 2.
An O(N2) solution:
Let f(i) denote the no. of ways of filling slots [1…i] with no.s from the following 2 buckets: Bucket 1 - [1…i] (i numbers), Bucket 2 - (K-N) numbers (all these no.s are > i), such that no one or two cycles are formed. Clearly, f(N) is the desired answer.
Let’s try to fill slot 1. There are 2 possibilities:
1.) Pick a number from bucket 1:
Let’s say a1 [1 => a1] (means slot 1 is filled with no. a1). Let’s try all cycle lengths >= 3: For cycle length = ‘j’, we’ll choose ‘j’ numbers {1, a1, a2, …, a(j-1)} such that (1 <= am <= i), and built a ‘j’ cycle in the following way: [1 => a1, a1 => a2, a2 => a3, …, a(j-2) => a(j-1), a(j-1) => 1].
For a ‘j’ cycle, the no. of ways = (i-1)C(j-1) * (j-1)! * f(i-j) = (i-1)P(j-1) * f(i-j)
Hence, summing over j = 3…i, no. of ways = sum(j = 3 to i) (i-1)P(j-1) * f(i-j)
After simplification, no. of ways = (i-1)! * sum(j = 3 to i) f(i-j) / (i-j)!
2.) Pick a number from bucket 2:
Let’s say we pick the number ‘b’ from bucket 2. We can do this in (K-N) ways. Let’s now try all cycle lengths >= 1: For cycle length = ‘j’, we’ll choose ‘j’ numbers {1, a1, a2, …, a(j-1)} such that (1 <= am <= i), and built a ‘j’ cycle in the following way: [1 => a1, a1 => a2, a2 => a3, …, a(j-2) => a(j-1), a(j-1) => 1]. Now, break the cycle by putting the number ‘b’ in slot a(j-1) [a(j-1) => b].
For a ‘j’ cycle, the no. of ways = (K-N) * (i-1)P(j-1) * f(i-j)
Hence, summing over j = 1…i, no. of ways = (K-N) * sum(j = 1 to i) (i-1)P(j-1) * f(i-j)
After simplification, no. of ways = (K-N) * (i-1)! * sum(j = 1 to i) f(i-j) / (i-j)!
Summing both the cases, we have:
f(i) = (K-N) * f(i-1) + (K-N) * (i-1) * f(i-2) + (K-N+1) * (i-1)! * sum(j = 3 to i) f(i-j) / (i-j)!
An O(N) solution:
The constraints don’t allow an O(N2) solution to pass. We need to do better. By observing the above formula carefully, it can be reduced to O(N).
Let’s define g(i) = sum (j = 1 to i) f(j) / j!
It can be written as g(i) = g(i-1) + f(i) / i!
And f(i) can be re-written as, f(i) = (K-N) * f(i-1) + (K-N) * (i-1) * f(i-2) + (K-N+1) * (i-1)! * g(i-3)
Thus, f(N) can be computed in O(N). The final answer is f(N) * KPN.
KPN can also be computed in O(N). Hence, the overall complexity of the solution is O(N).
Note: ‘K’ can be as large as 1018. Be careful with overflows.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.