Codeforces Round 992 (Div. 2) C. Ordered Permutations.
The problem statement
The problem starts by defining the following function for any permutation of integers \(1\) to \(n\):
\[S(p) = \sum_{1 \leq l \leq r \leq n} \min(p_l, p_{l+1}, \dots , p_{r})\]The function is actually the sum of the minimum elements of all possible subarrays of a permutation \(p\).
For a given \(n\), the problem asks to find the \(k\)-th permutation in lexicographical order among the permutations giving the maximum or report that there is none.
Permutations yielding maximum \(S(p)\)
The first task is to identify the permutations that yield the maximum value of \(S(p)\). Let’s observe some permutations for \(n = 3\).
| Permutation | Subarrays | \(S(p)\) values | Sum of \(S(p)\)s |
|---|---|---|---|
| \([1, 2, 3]\) | \([1], [1, 2], [1, 2, 3]\) \([2], [2, 3]\) \([3]\) |
\(1, 1, 1\) \(2, 2\) \(3\) |
\(10\) |
| \([1, 3, 2]\) | \([1], [1, 3], [1, 3, 2]\) \([3], [3, 2]\) \([2]\) |
\(1, 1, 1\) \(3, 2\) \(2\) |
\(10\) |
| \([2, 1, 3]\) | \([2], [2, 1], [2, 1, 3]\) \([1], [1, 3]\) \([3]\) |
\(2, 1, 1\) \(1, 1\) \(3\) |
\(9\) |
| \([2, 3, 1]\) | \([2], [2, 3], [2, 3, 1]\) \([3], [3, 1]\) \([1]\) |
\(2, 2, 1\) \(3, 1\) \(1\) |
\(10\) |
Here, the maximum sum is \(10\), achieved only by the permutations \([1, 2, 3]\), \([1, 3, 2]\), and \([2, 3, 1]\). Now, what is the characteristic of these permutations?
The first clue comes from observing the position of \(1\) in the permutations. Notice that in the maximum sum permutations, \(1\) is always either at the beginning or at the end. It is because if \(1\) is in the middle, it occurs as the minimum value in more subarrays, reducing the overall sum.
If this is the case for the smallest element \(1\) in the overall permutation, the same must be the case for the next smallest element \(2\) in the remaining subarray. Observing the permutations above confirms the fact. The rule generalizes to the following: each element is either at the beginning or at the end of the subarray.
Counting the permutations
Each element can be either at the beginning or at the end, that is, there are two choices for each element, except the last one, because the last element’s position is determined by the rest. That naturally alludes to binary representation. Therefore, there are total \(2^{n-1}\) permutations that gives the maximum value of \(S(p)\).
Finding the \(k\)-th permutation
Then comes the question of finding the ordering of these permutations, if there are any. Let’s again observe the permutations for \(n = 3\), juxtaposed against their binary encodings.
| Permutation | Binary Encoding | Explanation |
|---|---|---|
[1, 2, 3] |
0 0 0 |
All elements remain in their positions. |
[1, 3, 2] |
0 1 0 |
The second element in the subarrary [2, 3] moved to the end. |
[2, 3, 1] |
1 0 0 |
Only the first element moved to the end; remaining subarray [2, 3] remains the same. |
[3, 2, 1] |
1 1 0 |
Both the first and second elements moved to the end. |
Notice that the binary encoding in increasing order also gives the lexicographical ordering of the permutations. It is because in lexicographical ordering, the last, or least significant, positions change earlier and more often, and the first, or most significant, positions change later and less often. Just like how bits change in binary counting in increasing order.
Caveats
- For any given \(n\), there can be \(2^{n-1}\) permutations yielding the maximum sum. If \(k\) is greater than that, the permutation doesn’t exist.
- Checking for \(k\) needs bit additional care, because \(2^{n-1}\) will overflow as the bound of \(n\) \(2 × 10^{5}\) is very large. For \(n > 40\) the number of desired permutations (\(1,099,511,627,776\) close to \(10^{12}\)) exceeds the bound of \(k\) (\(10^{12}\)). Therefore, the check \(k < 2^{n-1}\) is necessary only for \(n < 40\).
Implementation
Here is my implementation incorporating the ideas above in C++.