PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: pols_agyi_pols
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Combinatorics
PROBLEM:
For a permutation P, define f(P) to be the minimum possible value of the final array after performing the following process:
- Choose indices i \lt j \lt k such that P_i \lt P_j \lt P_k, and delete P_j.
You’re given a permutation P that’s partially filled.
Find the sum of f(Q) across all permutations Q obtained by filling in P.
EXPLANATION:
First, we compute f(Q) for a fixed permutation Q.
Observe that, for a fixed index i:
- If Q_i \lt Q_j for every j \lt i, then it’s impossible to delete Q_i, since it can never be in the middle of an increasing sequence of length 3.
That is, if Q_i is a prefix minimum of the permutation, it cannot be deleted. - Similarly, if Q_i \gt Q_j for every j \gt i (meaning Q_i is a suffix maximum), it’s impossible to delete Q_i.
Any element that’s either a prefix minimum or suffix maximum cannot be deleted.
On the other hand, any element that’s neither a prefix minimum or a suffix maximum can be deleted.
How?
Suppose Q_i is neither a prefix minimum nor a suffix maximum.
Let x be the prefix minimum till index i. We know that x \lt Q_i.
Let y be the suffix maximum after index i. We know that y \gt Q_i.
Choosing the elements (x, Q_i, y) allows us to delete index Q_j.
Note that even if other moves are performed before deleting Q_i, the elements x and y cannot be deleted, so making this move is always possible.
Since f(Q) is defined to be the minimum possible sum after deletions, it thus simply equals the sum of all elements of Q that are either prefix minimums or suffix maximums.
With this characterization in hand, let’s solve subtask 1.
Here, we’re free to choose any permutation we like.
Fix a value x. Let’s compute the number of permutations in which x is either a prefix minimum or a suffix maximu,.
- If x is a prefix minimum, no value \lt x should occur before it.
- Let’s fix the positions occupied by the elements 1, 2, 3, \ldots, x.
There are \binom{N}{x} ways to do this. - Once these x positions are chosen, x itself should occupy the leftmost of them, while the remaining elements can be placed in any order: there are thus (x-1)! ways to arrange them.
- Elements \gt x can be placed in any order in the remaining positions, for (N-x)! arrangements.
- Let’s fix the positions occupied by the elements 1, 2, 3, \ldots, x.
- If x is a suffix maximum, we can use similar logic.
- Fix the positions of elements \geq x, which gives us \binom{N}{N-x+1} choices.
- Of them, x should occupy the rightmost one, while the others can be arranged in any order, for (N-x)! ways.
- The elements \lt x can take any order among the remaining positions, for (x-1)! ways.
- However, we’ve double-counted permutations in which x is both a prefix minimum and a suffix maximum.
There are exactly (x-1)! \cdot (N-x)! such permutations, since everything smaller than x should occur after it in some order, while everything larger than it should occur before it in some order.
In summary, the number of permutations in which x is either a prefix minimum or a suffix maximum is
x is added to the answer once for each such permutation.
So, the answer to subtask 1 is simply
Binomial coefficients can be computed in constant time if factorials are precomputed, so this entire summation can be found in \mathcal{O}(N).
Subtask 2 it not too different from the first, but we’re no longer free to choose positions as we like.
Let’s go back to our initial idea: fix a value of x, and count the number of permutations in which x is either a prefix minimum or a suffix maximum.
We’ll focus on just counting the number of permutations where it’s a prefix minimum, since the other part is similar.
First, let’s define a few values:
- L denotes the minimum index such that 0 \lt P_L \lt x (and L = N+1 if no such index exists).
- Note that x must be placed at an index \lt L, otherwise it can’t be a prefix minimum.
- m_1 denotes the number of elements \lt x that don’t exist in P.
Similarly m_2 denotes the number of elements that are \gt x and don’t exist in P. - Z denotes the number of zeros (empty positions) in P.
- \text{suf}_i denotes the number of zeros at positions i, i+1, \ldots, N, i.e, in the suffix starting at index i.
We consider two cases.
- Suppose x doesn’t exist yet in P.
- Choose the positions of x and the m_1 smaller elements, giving \displaystyle\binom{Z}{m_1 + 1} ways.
- x will be placed at the leftmost spot among the chosen positions.
However, if all the positions chosen are \gt L, x will itself be placed after L, which isn’t allowed. - To account for that, subtract the number of ways of choosing m_1 + 1 positions after index L, which is just \displaystyle\binom{\text{suf}_L}{m_1 + 1}.
- We place x at the leftmost chosen position, and then there are m_1! \cdot m_2! ways to arrange the remaining elements.
- Choose the positions of x and the m_1 smaller elements, giving \displaystyle\binom{Z}{m_1 + 1} ways.
- Suppose x does exist already in P, say at index i.
- If x exists to the right of L, it can never be a prefix minimum.
- Otherwise, we simply choose m_1 empty positions to the right of index i to contain the remaining elements smaller than x.
This is done in \displaystyle \binom{\text{suf}_{i}}{m_1} ways. - Once again, there are m_1! \cdot m_2! ways to arrange the unfixed elements once positions are chosen.
So, just as in subtask 1, it’s possible to compute the contribution of a single element in constant time - as long as appropriate quantities (such as factorials and prefix/suffix zeros) are found first.
Similar logic applies to counting permutations where x is a suffix maximum, and those where it’s both a prefix minimum and suffix maximum (which needs to be subtracted out).
The time complexity remains \mathcal{O}(N).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+1;
ll factorialNumInverse[N + 1];
ll naturalNumInverse[N + 1];
ll fact[N + 1];
void InverseofNumber(ll p)
{
naturalNumInverse[0] = naturalNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}
void InverseofFactorial(ll p)
{
factorialNumInverse[0] = factorialNumInverse[1] = 1;
for (int i = 2; i <= N; i++)
factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}
void factorial(ll p)
{
fact[0] = 1;
for (int i = 1; i <= N; i++) {
fact[i] = (fact[i - 1] * i) % p;
}
}
ll Binomial(ll N, ll R, ll p)
{
if(R<0){
return 0;
}
ll ans = ((fact[N] * factorialNumInverse[R])
% p * factorialNumInverse[N - R])
% p;
return ans;
}
void start()
{
ll p = 998244353;
InverseofNumber(p);
InverseofFactorial(p);
factorial(p);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
start();
while(kitne_cases_hain--){
ll n;
cin>>n;
ll a[n+1];
ll pos[n+1]={};
ll right[n+2]={};
ll fixed[n+2]={};
vector <ll> v;
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
if(a[i]==0){
v.push_back(i);
}else{
fixed[a[i]]=1;
}
}
ll total=v.size();
v.push_back(n+5);
for(int i=n;i>=1;i--){
right[i]=max(right[i+1],pos[i]);
fixed[i]+=fixed[i+1];
}
ll ans=0;
ll l=n+1;
ll cntl=0;
ll r,cntr;
ll emptyl,emptyr,not_removed;
for(int i=1;i<=n;i++){
if(pos[i]!=0){
r=right[i+1];
cntr=n-i-fixed[i+1];
not_removed=0;
if(l>pos[i]){
emptyr=lower_bound(v.begin(),v.end(),pos[i])-v.begin();
emptyr=total-emptyr;
if(emptyr>=cntl){
not_removed+=Binomial(emptyr,cntl,998244353);
}
}
if(r<pos[i]){
emptyl=lower_bound(v.begin(),v.end(),pos[i])-v.begin();
if(emptyl>=cntr){
not_removed+=Binomial(emptyl,cntr,998244353);
not_removed%=998244353;
}
}
if(pos[i]==n-i+1 && r<pos[i] && l>pos[i]){
not_removed+=998244352;
not_removed%=998244353;
}
not_removed=(((not_removed*fact[cntl])%998244353)*fact[cntr])%998244353;
not_removed*=i;
not_removed%=998244353;
ans+=not_removed;
ans%=998244353;
l=min(l,pos[i]);
}else{
r=right[i+1];
cntr=n-i-fixed[i+1];
emptyl=lower_bound(v.begin(),v.end(),l)-v.begin();
emptyr=lower_bound(v.begin(),v.end(),r)-v.begin();
emptyr=total-emptyr;
not_removed=0;
if(emptyr){
emptyr=min(emptyr,total-cntr);
not_removed=Binomial(total,cntl,998244353)-Binomial(total-emptyr,cntl-emptyr,998244353)+998244353;
not_removed%=998244353;
}
if(emptyl){
emptyl=min(emptyl,total-cntl);
not_removed+=(Binomial(total,cntr,998244353)-Binomial(total-emptyl,cntr-emptyl,998244353)+998244353);
not_removed%=998244353;
}
if(r<(n-i+1) && l>(n-i+1) && !a[n-i+1]){
not_removed+=998244352;
not_removed%=998244353;
}
not_removed=(((not_removed*fact[cntl])%998244353)*fact[cntr])%998244353;
not_removed*=i;
not_removed%=998244353;
ans+=not_removed;
ans%=998244353;
cntl++;
}
}
cout<<ans<<"\n";
}
return 0;
}
Editorialist's code (Python)
N = 2 * 10**5 + 10
mod = 998244353
fac = [1]*N
ifac = [1]*N
fac[0] = 1
for i in range(1, N): fac[i] = fac[i-1] * i % mod
for i in range(N): ifac[i] = pow(fac[i], mod-2, mod)
def C(n, r):
if r < 0 or n < r: return 0
return fac[n] * ifac[r] % mod * ifac[n-r] % mod
for _ in range(int(input())):
n = int(input())
p = [0] + list(map(int, input().split()))
zeroct = [0]*(n+1)
for i in range(1, n+1):
zeroct[i] = zeroct[i-1] + (p[i] == 0)
zeroct.append(zeroct[-1])
pos = [0]*(n+1)
for i in range(1, n+1):
if p[i] > 0: pos[p[i]] = i
pmin = [n+1]*(n+1)
for i in range(1, n+1):
if pos[i] == 0: pmin[i] = pmin[i-1]
else: pmin[i] = min(pmin[i-1], pos[i])
smax = [0]*(n+2)
for i in reversed(range(1, n+1)):
if pos[i] == 0: smax[i] = smax[i+1]
else: smax[i] = max(smax[i+1], pos[i])
ans = 0
less, more = 0, zeroct[n]
for x in range(1, n+1):
L = pmin[x]
R = smax[x]
ways = 0
if pos[x] == 0:
more -= 1
ways += C(zeroct[n], less + 1) - C(zeroct[n] - zeroct[L], less + 1)
ways += C(zeroct[n], more + 1) - C(zeroct[R], more + 1)
if L > n+1-x and R < n+1-x: ways -= 1
ans += x * ways * fac[less] * fac[more] % mod
less += 1
else:
if pos[x] == L: ways += C(zeroct[n] - zeroct[L], less)
if pos[x] == R: ways += C(zeroct[R], more)
if L == n+1-x and R == n+1-x: ways -= 1
ans += x * ways * fac[less] * fac[more] % mod
print(ans % mod)