The 4th problem has strictly combinatorial nature. You're given two numbers and
, where
. You have to answer two following questions:
- What is the number of permutations which can be created after performing exactly
swaps of adjacent elements from the sequence
- What is the number of permutations which can be created after performing at most
swaps of any two elements from the sequence
I omit in that editorial the fact that you have to return these results modulo , but remember to do that.
First question
Let's solve the first question first. The idea that came to my mind is to use the dynamic programming concept here. Let's define
number of permutations achievable from
using exactly
adjacent swaps, but with the restriction that we don't swap the same elements more than once.
In other words, is the number of permutations of
elements with exactly
inversions. That observation helps us to define a recursive relation. If we have already computed
for all
, we can get
by inserting the
-th element at some place and we know that if after that insertion, there are
elements after the
-th element, we just created exactly
new inversions. It follows that the complete recursive relations is:
which can be computed faster as:
The last term of the above equation is define only for , otherwise it's 0.
The base cases are:
for any
and
.
So far, we computed the number of permutations with exactly inversions. The last observation is that if you're allowed to do exactly
swaps, you can achieve any permutation with
inversions (the last element of that sequence is either 0 or 1 depending on the parity of
), because you can erase any inversion by swapping back these elements immediately after the inversion was made with exactly one additional swap. In other words, you can use exactly 2 swaps to make no swaps.
To compute the exact result, you have to sum up the values of for
.
Second question
I suspected that the answer is somehow connected to the Stirling numbers, but didn't know how exactly. I thought that I can write a brute force solutions to provide answers for small and then use the OEIS (the On-Line Encyclopedia of Integer Sequences) to figure out the exact solution. Let
be the answer to our question. It turned out that a brute force can be written as a simple DFS on the graph, where permutations are nodes, and there is an edge between two permutations if and only if you can transform one to the other using exactly one exchange of elements. I managed to do that quickly and it gave me the following table:
n / k | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
1 | 1 | ||||
2 | 1 | 2 | |||
3 | 1 | 4 | 6 | ||
4 | 1 | 7 | 18 | 24 | |
5 | 1 | 11 | 46 | 96 | 120 |
You can observe that the value for is the same as when
because if you can exchange
elements, you can create all permutations.
If you want to identify in OEIS an sequence depending on two variables ( and
here), you have to put its values in the row major form i.e. print values row by row. In that case, it's 1,1,2,1,4,6,1,7,18,24,1,11,46,96,120 and it gives the sequence A109822 and the recursive relation for that is:
where is the absolute value of the Stirling number of the first kind for
and
. These numbers can be computed using the recurence relation and a dynamic programming concept.
Summary
The time complexity for both questions is .
You can find my solution from the contest here: