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:
Maximum subarray sum
PROBLEM:
The beauty of a permutation is the number of its prefixes that are themselves permutations.
You’re given a permutation P. At most once, you can choose an even-length subarray of P, partition it into blocks of two, and swap the elements within each block.
Find the maximum possible beauty of P.
EXPLANATION:
First, we need a way to quickly check when a prefix is a permutation or not.
There are several different criteria you can use for this, for example:
- The sum of the first i elements should equal \frac{i\cdot (i+1)}{2}; or
- The maximum of the first i elements should equal i.
In the editorial, I will use the first criterion to perform any necessary checks, but the other ways can be made to work too with appropriate changes.
Suppose we perform the operation on subarray [L, R]. Let’s analyze what exactly happens to each prefix.
- For i \lt L, the prefix of length i is completely unchanged.
- For i \gt R, the prefix of length i has some of its elements rearranged, but the set of elements remains the same.
So, if it was a permutation before the operation it will remain so after it, and if it wasn’t a permutation before the operation it will remain not one after it.
Functionally, that means nothing has changed about such an i. - In fact, the same thing can be observed for i = L+1, L+3, L+5, \ldots, R.
That is, the elements in each such prefix get rearranged a bit, but the set of elements within them remains the same - so from the perspective of the beauty of P, nothing changes.
That leaves only the prefixes L, L+2, L+4, \ldots, R-1 that see an actual change in elements.
In particular, you may notice that for each such i, the only change is that:
- The element P_i is no longer present in it (since it moves to index i+1).
- The element P_{i+1} is now present in it.
- Nothing else changes!
The elements at indices 1 to i-1 remain the same, just in possibly a different order (which doesn’t affect whether the prefix is a permutation or not).
Further, observe that this change at index i doesn’t really depend on L and R at all - it depends purely on i.
So, we can essentially consider each index i independently, and see what happens when P_i is swapped with P_{i+1}.
So, let’s precompute for each index i the change in the beauty of P if P_i and P_{i+1} are swapped.
Let \text{pref}_i be the sum of the first i elements of P, that is, P_1 + P_2 + \ldots + P_i.
As noted at the start, the first i elements form a permutation if and only if \text{pref}_i = \frac{i\cdot (i+1)}{2}.
If P_i and P_{i+1} are swapped, \text{pref}_i changes to \text{pref}_i + P_{i+1} - P_i.
So, it’s quite easy to check whether the first i elements form a permutation, both before and after (i, i+1) is swapped.
Let C_i denote the change in answer if P_i is swapped with P_{i+1}.
That is,
- If swapping doesn’t change whether the prefix is/isn’t a permutation, C_i = 0.
- If it wasn’t initially a permutation but becomes one after swapping, C_i = 1.
- If it was initially a permutation but isn’t one after swapping, C_i = -1.
Now, note that choosing subarray [L, R] changes the answer by exactly C_L + C_{L+2} + C_{L+4} + \ldots + C_{R-1}.
We want, of course, the maximum possible change.
This corresponds to just the maximum subarray sum of the array C, when considering even and odd indices separately.
That is, consider the two separate arrays [C_1, C_3, C_5, \ldots ] and [C_2, C_4, C_6, \ldots ].
Find the maximum subarray sum of each of these individually, and take the maximum of the two.
This is the maximum possible change in beauty we can obtain.
Add this to the initial beauty of P to obtain the final answer.
Computing the maximum subarray sum of an array is a well-known problem, and can be done in linear time - see here.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
while(kitne_cases_hain--){
ll n;
cin>>n;
ll a[n];
ll mex[n+1];
mex[0]=1;
ll perm[n]={};
set <ll> s;
for(int i=0;i<n;i++){
cin>>a[i];
s.insert(a[i]);
mex[i+1]=mex[i];
while(s.count(mex[i+1])){
mex[i+1]++;
}
if(mex[i+1]==i+2){
perm[i]=1;
}
}
ll sum[n+1]={};
for(int i=n-1;i>=0;i--){
sum[i]=sum[i+1]+perm[i];
}
ll ans=sum[0];
ll best[2]={};
ll cnt=0;
ll maxi=0;
for(int i=1;i<n;i++){
if(maxi<=i){
if(perm[i-1]){
best[i%2]=max(best[i%2]+perm[i],cnt+perm[i]+perm[i-1]);
}else{
if(mex[i-1]==a[i]){
best[i%2]=max(best[i%2]+perm[i]+1,cnt+perm[i]+1);
}else{
best[i%2]=max(best[i%2]+perm[i],cnt+perm[i]);
}
}
}else{
best[i%2]=max(best[i%2]+perm[i],cnt+perm[i]);
}
ans=max(ans,best[i%2]+sum[i+1]);
cnt+=perm[i-1];
maxi=max(maxi,a[i-1]);
}
cout<<ans<<"\n";
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
ans = sm = 0
cursum = [0, 0]
add = 0
for i in range(n):
sm += p[i]
if sm == (i+1)*(i+2)//2: ans += 1
if i+1 < n:
before = sm == (i+1)*(i+2)//2
after = (sm + p[i+1] - p[i]) == (i+1)*(i+2)//2
cursum[i%2] = max(0, cursum[i%2] + after - before)
add = max(add, cursum[i%2])
print(ans + add)
