EVIPRO Editorial

PROBLEM LINK:

Practice
Contest

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;
} 
4 Likes

Editorialist code partially accepted.

It was overflow issue.

//old
ans = 1ll * cur * n * (n+1)/2;
//because of very very large n
ans = 1ll * n * (n+1)/2;
ans *= cur;
//doing division before avoids overflow

Sorry anyway, I just saw it correct and didn’t check the score while testing.

5 Likes

Thanks for the correction.

Can someone explain, how iN(N+1)/2 come?
Thanks.

1 Like

This is total number of sub strings you can make.
For example: For string length 3

Starting with index 1: Substrings are (1,1), (1,2), (1,3)
Starting with index 2: Substrings are (2,2), (2,3)
Starting with index 3: Substrings are (3,3)
So for string of length n. Such cases are: n+(n-1)+(n-2)+…+(1) = n*(n+1)/2

And at first we assume that no changes are made while choosing these substrings. Hence identical pairs are assumed to be same in every case initially.

But why we multiply with I? here I means number of adjacent identical characters in our string.
I hope you understand my doubt and thanks for answering…

Initially we assume that no changes are made while choosing these substrings. Hence identical pairs are assumed to be same in every case initially. For example while at first while choosing (1,3) or any L,R we didn’t alter the bits. Hence the adjecant pair remain same as the original string (Initial assumption).

So for all the L,R pairs the number of such identical pairs is IN(N+1)/2 and then we take case to case analysis of L,R and increase or decrease the answer depending on the situation of that L,R pair.

1 Like

Can someone explain this logic pls.
FOR(i,0,SZ(s) - 1)
{
if (s[i] == s[i + 1])
{
res += 1LL * n * (n + 1) / 2 - n;
}
else
{
res += n;
}
}

Scanner s = new Scanner(System.in);
int t = s.nextInt();
while (t-- > 0) {

		String str = s.next();
		if (str.length() == 1) {
			System.out.println(0);
		} else {

			int n = str.length();
			int original = 0;
			int[] left = new int[n];
			int[] right = new int[n];
			int rightsum = 0;
			for (int i = 0; i < n; i++) {

				if (i - 1 >= 0) {
					if (1 - Character.getNumericValue(str.charAt(i - 1)) == Character
							.getNumericValue(str.charAt(i)))
						left[i] = 1;
					else
						left[i] = -1;

					if (Character.getNumericValue(str.charAt(i - 1)) == Character.getNumericValue(str.charAt(i)))
						original++;
				}
				if (i + 1 < n) {
					if (1 - Character.getNumericValue(str.charAt(i)) == Character
							.getNumericValue(str.charAt(i + 1)))
						right[i] = 1;
					else
						right[i] = -1;
					rightsum += right[i];

				}

			}
			
			int firstpart = (original * (n*(n+1)))/2;
			int residue = 0 ;
			int total = rightsum*n;
			//System.out.println(firstpart + " ----");
			for(int i = 0 ;i < n; i++) {
				int temp = left[i]*(n-i)-residue;
				total = total+temp;
				//System.out.println(residue);
				residue = residue+right[i];
				
			}
			total = total+firstpart;
			System.out.println(total);

		}

	}

this worked for smaller cases and i got WA for the other 50 points can someone please explain why?

for(int j = 2 ; j <= n ; j++){
        if(str[j] == str[j-1])
            ans -= (n - j + 1);
        else ans += (n - j + 1);
    }

Can someone please explain this part of code

It wasnt clear in the editorial above, please elaborate,

I have deduced few rules, they are below,

if both sides are different, count *increases*
if left is same and right is different, increases
if right is same and left is different, decreases
if two sides are same then, decreases

Please elaborate, how did you get your approach

Yes please someone come as a saviour and elaborate it efficiently so others are able to understand

1 Like

can anyone explain this part please?

if(s[i]==s[i+1]) then we have to calculate for how many range operations this will contribute 1 i.e:
if we take any range (0 , i-1) and and range (i+2 , l-1)(where l is length of string) and also including the ranges which where indices {i,i+1} presents i.e: (l - i - 1)i .
therefore total no of ranges for s[i]==s[i+1] is : i
(l-i-1) + i*(i-1)/2 + (l-i)*(l-i-1)/2 ;
and for s[i]!=s[i+1] we have take those ranges which take either i or i+1 not both i.e: i + (l - i) , i for no. of ranges which take i and (l - i) for ranges which take i+1 index .