PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: nishu_sharma18
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have an array A containing N integers. You can increase at most one of its elements by 1.
Find the maximum number of subarrays that contain at least one even element after doing this.
EXPLANATION:
Since we only care about the parity of each element, we can reduce the entire array to 0's and 1's, depending on whether they’re odd or even.
Our aim is to maximize the number of subarrays that contain at least one occurrence of 0, and to do so, we’re allowed to choose one element and flip it from 0 to 1 or vice versa (since increasing an integer by 1 flips its parity).
First, let’s see how to quickly compute the number of subarrays containing at least one 0 for a fixed boolean array A.
One way of doing this is to compute the number of subarrays that don’t contain a 0 (meaning they’re all 1's), and subtract this from the total number of subarrays.
To find the number of subarrays containing only 1's, we can find all maximal “blocks” of 1's in A (maximal meaning they can’t be extended).
If these maximal blocks have lengths c_1, c_2, \ldots, c_k, then the number of subarrays containing only 1's is exactly
This is because any subarray containing only 1's must be fully contained within one of these blocks; and the number of subarrays contained within a block of length x is \frac{x\cdot (x+1)}{2}.
Computing these blocks (and their lengths) can be done easily in \mathcal{O}(N) time by just looping through the array.
Now, we need to figure out how flipping a single element can improve this.
Obviously, changing a 0 to a 1 (i.e even to odd) is useless - so we only need to consider changing some 1 to a 0.
Let S_i = 1, and suppose we flip this index. Let’s count how many new subarrays now contain a 0, but didn’t before (clearly, any subarray that previously contained a 0 will still contain it).
Let the block containing index i be the range [L_i, R_i]
Then, observe that the new subarrays containing a 0 are exactly those subarrays of [L_i, R_i] which include index i - in other words, subarrays whose left endpoint lies between L_i and i, and right endpoint lies between i and R_i.
There are (i-L_i+1) \cdot (R_i-i+1) such subarrays.
L_i and R_i can be found when initially computing the blocks, and once they’re known, we’re able to process a single index in \mathcal{O}(1) time.
So, simply try every i and take the best answer among them all.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
int curr = 0;
vector <int> b;
for (auto x : a){
if (x & 1){
curr++;
} else {
if (curr) b.push_back(curr);
curr = 0;
}
}
if (curr) b.push_back(curr);
int ans = n * (n + 1) / 2;
int mx = 0;
for (auto x : b) ans -= x * (x + 1) / 2, mx = max(mx, x);
if (mx % 2 == 0) ans += (mx / 2) * (mx / 2 + 1);
else ans += (mx / 2 + 1) * (mx / 2 + 1);
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include "bits/stdc++.h"
#define int long long
using namespace std;
int solve1(vector<int> a) {
int n = a.size(),ans =0;
for(int i=0 ;i<n ;i++){
a[i]%=2;
}
int prevzero=-1;
for(int i = 0; i <n; i++){
if(a[i]==0)
prevzero = i;
ans+= (prevzero+1);
}
vector<int> rightzero(n);
int rZero=n;
for(int i=n-1 ;i>=0 ;i--){
if(a[i]==0) rZero = i;
rightzero[i] = rZero;
}
prevzero = -1;
int extra =0;
for(int i=0 ;i<n ;i++){
if(a[i]==1){
int val = ((i-prevzero)*(rightzero[i]-i));
extra = max(extra,val);
}
else{
prevzero = i;
}
}
ans+= extra;
return ans;
}
void solve(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0 ;i<n ;i++) cin>>a[i];
cout<<solve1(a)<<'\n';
}
/*----------------------------------------------------------*/
int32_t main(){
int t;
cin>>t;
while(t--) solve();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
for i in range(n): a[i] %= 2
ans = n*(n+1)//2
left, right = [0]*(n+1), [0]*(n+1)
for i in range(n):
if a[i] == 0: left[i] = 0
else: left[i] = left[i-1] + 1
ans -= left[i]
for i in reversed(range(n)):
if a[i] == 0: right[i] = 0
else: right[i] = right[i+1] + 1
mx = 0
for i in range(n):
mx = max(mx, left[i] * right[i])
print(ans + mx)
