PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums
PROBLEM:
A binary string is good if it’s possible to convert it to a palindrome by repeatedly deleting a pair of adjacent equal elements.
The goodness of a binary string is the length of its longest good substring.
Given a binary string S, compute the sum of goodness across all of its substrings.
EXPLANATION:
First, let’s analyze when a binary string S is good.
Suppose we’ve performed several operations on S, and it’s now a palindrome.
Then, if S has some adjacent equal characters, we can delete them in such a way that S remains a palindrome:
- If the adjacent pair is entirely in the left (or right) half of S, there’s a mirrored pair of equal adjacent elements in the other half, so we can delete both pairs and S will remain a palindrome.
- If the adjacent pair crosses the middle, it can be verified that deleting them doesn’t change palindromicity either.
So, the final palindrome we end up can be assumed to not contain any equal adjacent elements.
That means it must be either empty, or an alternating string, i.e. 01010\ldots or 10101\ldots
Note that an alternating string is a palindrome if and only if its length is odd (or it is empty).
Now, we want to figure out whether there exists a sequence of moves such that the reduced string is either empty, or alternating and of odd length.
While it looks like there are many possible choices for the operations, and the order in which they must be performed, it turns out that this is a case of the illusion of choice: no matter which order we perform the operations in, the final string we end up with is unique!
Proof
There are a few different ways to prove this. Here’s one of them.
Let’s flip all the characters at odd positions of S. We’ll denote this transformed string by S'.
For example, \texttt{10010010} \to \texttt{11000111}.Now, note that deleting two adjacent equal characters in S is equivalent to deleting two adjacent unequal characters in S' (because if they were equal in S, one of them would’ve been flipped in S').
So, our operation is now “delete a 10 or 01 substring in S'”.
This is nicer to think about, because now each operation removes exactly one 0 and one 1.
Further, since two adjacent elements are deleted, the index parities of other elements won’t change - meaning that the S' for the new string S (after deletion) is the same as just deleting the corresponding elements from the current S' (basically, there’s no need to recompute S' after each operation).Now, suppose S' has x zeros and y ones.
- If x = y, we’ll be able to delete all of them and the resulting string will be empty.
- If x \gt y we’ll have x-y zeros in the end.
Note that this corresponds to the original string being reduced to 0101\ldots of length x-y.- If x\lt y we’ll have y-x zeros in the end instead.
This corresponds to the original string being reduced to 1010\ldots of length y-x.In any case, the final string S' is unique, which proves that the final string S is also unique.
This also tells us how to find the length of the final string which is what we’re interested in (recall that we want it to be a palindrome, which happens only when the length is either 0 or odd).
This fact is very useful because it tells us something quite powerful: the goodness of a string (i.e. the length of its longest good substring) is either |S|, or |S|-1.
Why?
Given that we know that the reduced string is unique, this is pretty easy to show.
Suppose S is not good.
Without loss of generality, let S_N = 0.
Consider the substring S_1S_2\ldots S_{N-1}. Suppose this substring is also not good - then its reduced form must have positive even length.
Let T denote the reduced form of S_1S_2\ldots S_{N-1}.
- If T ends with a 0, then T + S_N can be operated on to remove the last two elements, resulting in an odd-length reduced string corresponding to S.
This can’t be the case since we assumed S isn’t good.- Similarly, if T ends with 1, then T+S_N is already a reduced string of odd length corresponding to S, again a contradiction.
This means S_1S_2\ldots S_{N-1} must be good, and so the goodness of S will be N-1 if it isn’t N.
Our aim is to compute the sum of goodness across all substrings of S.
However, we know that for a substring of length k, its goodness is either k or k-1.
In particular, each good substring contributes its own length to the answer, while everything else contributes its length minus one.
One way to look at this is that we initialize the answer to the sum of all substring lengths of S, and then subtract out the number of substrings that are not good.
The former quantity is easy to find, and is just \sum_{i=1}^N i\cdot (N-i+1).
So, we only need to compute the number of substrings that are not good.
To do this, we look back at how we proved uniqueness of the final string.
Let’s flip the characters at all even positions, i.e. convert 0 to 1 and vice versa.
Suppose there are x zeros and y ones in this modified string. Then the final string will have length |x-y|.
As noted at the start, an alternating string is a palindrome if and only if it either has odd length, or is empty.
So, our objective is now to count the number of substrings of the modified string for which |x-y| is either 0 or odd.
First, note that |x-y| and (x-y) (and (y-x)) have the same parity, so we can ignore the absolute value.
In fact, they have the same parity as x+y (which is the length of the substring), which makes one case very easy: |x-y| is odd if and only if the substring has odd length.
So, we can certainly add to the count every odd-length substring.
That leaves counting substrings with an equal number of zeros and ones.
This is a standard problem, and can be done with the help of prefix sums.
Let’s replace every 0 by -1. Then, y-x for a substring will simply correspond to its sum, so we want to count the number of substrings with sum that’s 0.
If we build the prefix sum of this new +1/-1 array, a subarray sum of zero corresponds to a pair of equal prefix sums.
This means we only need to find the number of pairs of equal prefix sums, which is easy enough to do in linear time by computing the frequencies of the prefix sums.
This gives us the number of good substrings, so the number of not-good substrings is just this count subtracted from \frac{N\cdot (N+1)}{2}.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
string s; cin >> s;
for (int i = 0; i < n; i++){
if (i & 1){
s[i] ^= '0' ^ '1';
}
}
// delete different adjacent
// need |0s - 1s| odd, or 0s = 1s?
int ans = 0;
for (int l = 1; l <= n; l++){
int v = n + 1 - l;
int add = l;
if (l % 2 == 0){
add--;
}
ans += add * v;
}
vector <int> ps(2 * n + 1, 0);
int curr = n;
ps[n]++;
for (auto x : s){
if (x == '0'){
curr++;
} else {
curr--;
}
ans += ps[curr]++;
}
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;
}
Editorialist's code (PyPy3)
import collections
for _ in range(int(input())):
n = int(input())
s = input()
a = []
for i in range(n):
if i%2 == 0: a.append(2*int(s[i]) - 1)
else:
if s[i] == '0': a.append(1)
else: a.append(-1)
# Count subarrays with sum = 0 or odd
pref, even, odd = 0, 1, 0
ct = collections.defaultdict(int)
ct[0] = 1
ans = 0
for i in range(n):
pref += a[i]
cur = i+1 - ct[pref]
if pref%2 == 0:
cur -= odd
even += 1
else:
cur -= even
odd += 1
ans += (i+1)*(i+2)//2 - cur
ct[pref] += 1
print(ans)