PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: bhavy_24_11
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Elementary combinatorics
PROBLEM:
You’re given an array A containing distinct integers.
Find the number of rearrangements P of A that maximize \text{MEX}(R), where
R_i = \max(P_1, \ldots, P_i) - \min(P_1, \ldots, P_i)
EXPLANATION:
Let’s first analyze the array R for a fixed rearrangement P.
We can make the following observations:
- R_1 = P_1 - P_1 = 0 always.
So, we always have \text{MEX}(R) \gt 0. - R is a non-decreasing array, i.e. R_i \ge R_{i-1}.
This is because \max(P_1, \ldots, P_i) \ge \max(P_1, \ldots, P_{i-1}) and similarly \min(P_1, \ldots, P_i) \le \min(P_1, \ldots, P_{i-1}).
This means \text{MEX}(R) is simply the first missing value in R, because if a value is missing it can never appear at a future index.
In particular, this means the first time an element in R increases by more than 1 will determine its MEX.
That is, let i be the smallest index such that R_i+1 \lt R_{i+1}.
Then we’ll have \text{MEX}(R) = R_i + 1.
Next, let’s analyze how the array R grows in value from left to right.
Let m_i = \min(P_1, \ldots, P_i) and M_i = \max(P_1, \ldots, P_i).
Then,
- If P_{i+1} \lt m_i, we’ll have m_{i+1} = P_{i+1} and M_{i+1} = M_i.
This gives R_{i+1} = M_i - P_{i+1}, meaning that R_{i+1} grows by exactly (m_i - P_{i+1}) compared to R_i. - Similarly, if P_{i+1} \gt M_i, we see that R_{i+1} will grow by (P_{i+1} - M_i) compared to R_i.
- Finally, if m_i \le P_{i+1} \le M_i, then the minimum and maximum both don’t change; so R_i = R_{i+1}.
Here is where we use the fact that the elements of our array are distinct.
Suppose we’ve decided the first element, P_1.
Then, if we want to make \text{MEX}(R) as large as possible,
- P_2 must equal either P_1 - 1 or P_1 + 1. (It cannot equal P_1 since elements are distinct.)
- P_3 must equal m_2-1 or M_2+1 to continue the streak of increases.
- P_4 must equal m_3-1 or M_3+1 to continue increasing, and so on.
- In general, if we’re able to make P_i equal either m_{i-1}-1 or M_{i-1}+1, we can continue increasing the MEX.
- Observe that as a result of doing this, we’ll always have every integer between m_i and M_i placed.
Because we have distinct integers, it’s thus impossible to keep the MEX the same by choosing to place an integer in [m_i, M_i] - we’re forced to change it if we want to have a chance at maximizing it.
- Observe that as a result of doing this, we’ll always have every integer between m_i and M_i placed.
Looking at this process, we see that we’ll place some consecutive integers in a prefix of P, till we’re unable to do so - and this is exactly when we’ll obtain the MEX as well because there will be a jump greater than 1.
Specifically, suppose we have with us all the integers l, l+1, l+2, \ldots, r.
Then, we can certainly obtain a MEX of (r-l+1) by just placing these integers in order (and then doing whatever with the remaining elements), since the corresponding elements of R will simply be 0, 1, 2, \ldots, r-l.
This immediately tells us what the maximum possible MEX attainable is: it’s simply the largest possible length of a segment [l, r] such that we have all the values l, l+1, \ldots, r available to us.
Now that we know what the maximum possible MEX is, let’s look at counting configurations that attain it.
Suppose we fix the maximal segment [l, r] that will help us attain the MEX.
We know that the first r-l+1 elements of P must then be these elements in some order, while the remaining elements can fill the remaining positions in any order (since they no longer affect the MEX).
There are N - (r-l+1) remaining elements, and any order of them works so that’s a multiplier of (N - (r-l+1))!
We now focus on just placing the elements [l, r] themselves in the prefix.
We must place them in such a way that we always have a set of contiguous elements placed.
One easy way to count the number of possible ways is to look at the placement in reverse.
Observe that:
- The last element has to be either l or r, since it must extend either the minimum or the maximum.
This gives us two choices; after which we then have a range of length (r-l) instead (either [l, r-1] or [l+1, r]). - The second-last element then has to be one of the endpoints of the new range.
Again, we have two choices, and the length of the range shrinks by 1. - This continues over and over, till we end up with only a single element remaining which must be placed in the first position.
- Since every step except the last had two options, there are 2^{r-l} possibilities in total.
So, the number of permutations of A that attain the maximum MEX, while placing all of [l, r] in the first (r-l+1) elements, simply equals
Now, note that there can be multiple maximal ranges.
For example if A = [1, 2, 8, 9] then the maximum range length is 2, attained by both [1, 2] and [8, 9].
However, maximal ranges can never intersect with each other (otherwise they wouldn’t be maximal), and so we can simply add up the answers for all maximal ranges since they’ll correspond to different configurations.
Note that we’re only interested in maximal ranges of maximum length, so the contribution of each such range to the answer is the same.
To find maximal ranges, simply sort the array A in ascending order and iterate through it; keeping the length of the current range in a variable and either incrementing it or resetting it to 1 depending on what the next value is.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
mx, p, cur = 0, -1, 0
for x in a:
if x == p+1: cur += 1
else: cur = 1
p = x
mx = max(mx, cur)
mod = 998244353
val = pow(2, mx-1, mod)
for i in range(1, n-mx+1):
val = (val * i) % mod
p, cur = -1, 0
ans = 0
for x in a:
if x == p+1: cur += 1
else: cur = 1
p = x
if cur == mx: ans += val
print(ans % mod)