PROBLEM LINK:
Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
Given a binary string S, you should compute the sum of F(S,L,R) over all pairs of integers (L,R) where (1≤L≤R≤|S|) and the function F(S,L,R) is defined as follows:
- Create a string U
- Set U=S
- For each i (L≤i≤R), flip the i-th character of U (change ‘1’ to ‘0’ or ‘0’ to ‘1’).
Then, F(S,L,R) is the number of valid pairs (i,i+1) such that U_i=U_{i+1}.
DIFFICULTY:
Easy
CONSTRAINTS
1 \leq |S| \leq 3*10^6
EXPLANATION:
Assume that you have a binary string B and you flipped it, the number of pairs i,i+1 where B_i=B_{i+1} will remain the same.
Now let’s flip a substring starting from index L and ending at index R (denote it by [L,R]) and think what will happen.
The number of identical adjacent characters in the substring [L,R] stayed the same. (since it was flipped completely).
The number of identical adjacent characters in the substrings [1,L-1],[R+1,|S|] stayed the same. (since they were never changed).
The only pairs that may change are (L-1,L) and (R,R+1). (except when L=1 or R=|S| of course).
So always the new number of pairs would change by x where -2 \leq x \leq +2
Let’s assume that our string is 1-indexed.
First, let’s calculate the number of adjacent identical characters in our string with a single loop and denote it by I. Our initial answer would be \frac{I*N*(N+1)}{2} (we will assume that the number of pairs won’t change). Now let’s consider every possible substring and add the change resulting from it being flipped to our final answer.
Now for each character in our string, let’s count how many ways it can be selected as a start for our flipped substring. For some index i the number of ways is |S|-i+1. For each of these, the value of F would change by either -1 if S_i=S_{i-1} or +1 otherwise.
Also for each character in our string, let’s count how many ways it can be selected as an end for our flipped substring. For some index i the number of ways is i. For each of these, the value of F would change by either -1 if S_i=S_{i+1} or +1 otherwise.
Complexity O(N)
Check solutions for more details.
Editorialist solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
string str;
cin>>str;
int n = str.size();
str = "#" + str;
long long ans = 0 , cur = 0;
for(int j = 2 ; j <= n ; j++) {
if (str[j] == str[j - 1])
++cur;
}
ans = 1ll * n * (n + 1)/2;
ans *= cur;
for(int j = 2 ; j <= n ; j++){
if(str[j] == str[j-1])
ans -= (n - j + 1);
else ans += (n - j + 1);
}
for(int j = 1 ; j < n ; j++){
if(str[j] == str[j+1])
ans -= j;
else ans += j;
}
cout<<ans<<endl;
}
}
Tester Solution
#include "bits/stdc++.h"
#include <chrono>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 3000007;
const int MOD = 1000000007;
const double Pi = acos(-1.0);
int A[MAX];
int main(int argc, char* argv[])
{
ios::sync_with_stdio(false); cin.tie(0);
srand(time(0));
int t;
cin >> t;
FOR(tt,0,t)
{
string s;
cin >> s;
int n = SZ(s);
Int res = 0;
FOR(i,0,SZ(s) - 1)
{
if (s[i] == s[i + 1])
{
res += 1LL * n * (n + 1) / 2 - n;
}
else
{
res += n;
}
}
cout << res << endl;
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}