STROPERS - Editorial

PROBLEM LINK:

Practice
Div1
Div2

Setter: Anton Trygub
Tester: Alexander Morozov
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

MEDIUM

PREREQUISITES:

Good observation skills

PROBLEM:

In this problem, we deal with binary strings (i.e strings containing only 0's and 1's) .

Two strings A and B are said to be equivalent (i.e A \sim B) if their lengths are equal and A can be transformed to B by performing the given operation 0 or more times:

  • Choose a substring of A containing even number of 1's and reverse it.

For a given binary string S, we need to find the total number of equivalence classes for all the substrings of S . In other words, we need to get the set of binary strings \mathcal{C} with smallest possible size such that for any substring R of S, there exists a string X \in \mathcal{C} such that R \sim X .

QUICK EXPLANATION:

  • For every substring X of given S, store the following length(X), number\_of\_ones(X) and the number of positions i (where 1 \leq i \leq length(X)) of X where
    (X[1] +X[2]+... + X[i]) \bmod 2 = 1 .

  • The number of such unique triples is the answer. We can solve this easily in O(N^2*\log(N)) by using sets where N is the length of string S .

EXPLANATION:

The first thing to note is that if for two strings A and B we have A \sim B, then A and B must belong to the same equivalence class. Now let us find some observations related to equivalent strings which help us solve the problem easily:

  • Observation 1 : If A \sim B, then B \sim A
    This must be clearly visible since if we can perform some operations to convert A to B, we can reverse those sequence of operations to convert B to A .

  • Observation 2 : If A \sim B, then length(A) = length(B) and the number of 1's in A and B are same.

  • Observation 3 : If A \sim B, then cnt_A = cnt_B where cnt_S for a string S is defined as follows:
    cnt_S = \{ Number of positions i where 1 \leq i \leq length(S) and (\sum_{j = 1}^{i} S_j) \bmod 2 = 1 \}

The last observation is the most crucial observation. Let us prove it.

Proof

Since A \sim B, we must must have some sequence of k \ge 0 operations op_1, op_2, ..., op_k to convert A to B. If we are able to prove that applying the operation once on any substring of A satisfying the given criteria leads to a string X with cnt_A = cnt_X, the value of cnt_A will be preserved after applying every operation and hence we are done with the proof.

For proving this, let us consider some notations for a string S with length N :

  • pref_S[i]= (\sum_{j = 1}^{i} S_j) \bmod 2

  • sum_S(l, r) = (\sum_{j = l}^{r} S_j) \bmod 2

Let us re-define cnt_S(l, r) = \{ Number of positions i where l \leq i \leq r and pref[i]=1\}

Now suppose we have applied operation on substring of S from l to r where 1 \leq l \leq r \leq N to convert S to T . We need to prove cnt_S(1, N) = cnt_T(1, N).

Since there are even number of ones from l to r, sum_S(l, r)=sum_T(l, r)= 0 .

We have pref_S[i] = pref_T[i] for 1 \leq i \lt l since that portion of the string is unchanged. Thus, cnt_S(1,l-1) = cnt_T(1, l-1) .

Note: All the additions done on arrays pref and sum are performed modulo 2 .

We also have pref_S[i] = pref_T[i] for r \lt i \leq N. This is because
pref_T[i] = pref_T[l-1] + sum_T(l,r) +sum_T(r+1,i)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = pref_S[l-1] + sum_T(l,r) +sum_S(r+1,i)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = pref_S[l-1] + 0 +sum_S(r+1,i)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = pref_S[l-1] + sum_S(l,r) +sum_S(r+1,i)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = pref_S[i]

Thus cnt_S(r+1, N) = cnt_T(r +1 , N) .

If we are able to prove cnt_S(l, r) = cnt_T(l, r) then
cnt_S(1, N) = cnt_S(1, l-1) + cnt_S(l, r) + cnt_S(r+1, N)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = cnt_T(1, l-1) + cnt_T(l, r) + cnt_T(r+1, N)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = cnt_T(1, N)
which is exactly what we want.

First, note that for any l \leq i \leq r where S[i] = 0 and sum(l, r) = 0, we will definitely have
sum_S(l, i) = sum_S(i, r) .

Let the number of 1's from l to r be x.

Now, we will have exactly x/2 positions in l \leq i \leq r having S[i] = 1 and pref_S[i] = 1 (think why this is true) . The same thing follows for string T also.

Also, for each position i from l to r where S[i] =0, we have

pref_S[i] = pref_S[l-1]+sum_S(l, i)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ =pref_T[l -1] + sum_S(i, r)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ = pref_T[l -1] + sum_T(l, r-i+l) = pref_T[r-i+l].

This implies that for every position i in S where S[i]=0, we will have a unique position
j = r-i+l in T such that T[j] = 0 and pref_S[i]=pref_T[j] .

Based on this observations, we can conclude cnt_S(l,r)=cnt_T(l, r) and
hence cnt_S(1,N)= cnt_T(1,N) .

This completes the proof.

Now, I claim that if two strings A and B satisfy length(A) = length(B), number\_of\_ones(A) = number\_of\_ones(B) and cnt_S = cnt_T, then A \sim B .

The first two conditions are obvious, but the third condition isn’t. Here is the proof for it.

Proof

The main idea of proving it is to show there exists a string S such that A \sim S and B \sim S. Then A \sim B .

Let the number of 1's in A and B be equal to x .
Do the following sequence of operations on A:

  • Start from i=1

  • If A[i] = 1, then increment i

  • Else find an index j such that A[j]=1 and the number of 1's in A[l,...,r] is even and reverse that substring. If there is so such j, then stop the process.

Here is an example:
Suppose A= 01010110, we do the following :
01010110 \to 10100110 \to 11001010 \to 11101000

After performing these series of operations, it is guaranteed that the resultant string say A' has x-1 ones at the positions from 1 to x-1 (beginning of the string) and the remaining 1 at such a position that cnt_A=cnt_{A'} (there could be only one such position) . Similarly, B is converted to B' by performing these series of operations on B . Also cnt_B=cnt_{B'} . SInce we have initially assumed that cnt_A = cnt_B, we get cnt_{A'} = cnt_{B'} and thus the last 1 will be at the same location in A' and B' . Hence A \sim B.

Therefore, given a binary string S, we can evaluate for each substring X of S the following 3 parameters length(S), number\_of\_ones(X), cnt_X and the number of these unique triples is the answer. We can evaluate this easily (for example by using a set) .

TIME COMPLEXITY:

O(N^2 \cdot \log(N)) ( where N is the length of string S \ ) for each testcase if set is used (see solution code). This can be optimised to O(N^2) is we use hash set but that is not required.

SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		cin >> s;
		int n = s.size();
		//length count_of_ones count_of_positions_of_odd_parity_sum
		set<tuple<int, int, int>> classes;
		for (int i = 0; i < n; i++)
		{
			int ones = 0;
			int cnt = 0;
			for (int j = i; j < n; j++)
			{
				if (s[j] == '1')
					ones++;
				if (ones & 1)
					cnt++;
				classes.insert(make_tuple(j - i + 1, ones, cnt));
			}
		}
		cout << classes.size() << endl;
	}
}
Setter's solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

int main()
{
#ifdef iq
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _t;
    cin >> _t;
    while (_t--)
    {
        string s;
        cin >> s;
        set<pair<int, pair<int, int>>> q;
        for (int i = 0; i < (int)s.size(); i++)
        {
            string t = s.substr(i);
            int cnt = 0, sum = 0;
            for (int j = 0; j < (int)t.size(); j++)
            {
                if (t[j] == '1')
                {
                    cnt++;
                    sum = -sum + j;
                }
                q.insert({cnt, {sum, j}});
            }
        }
        cout << q.size() << '\n';
    }
}

VIDEO EDITORIAL:

Please comment below if you have any questions, alternate solutions, or suggestions.

10 Likes

At least 1 TT explanation would had been appreciated

12 Likes

I DID SAME AND GOT TLE;
TLE in 1-st tc of second sub-task;
Solution: 40422605 | CodeChef
see, it’s same;

the question was good but at least one test case explanation should be there

16 Likes

i did it in a greedy way.
any string can be uniquely transformed by trying to move all the 1’s at the start in bubble sort faishon.

On observation one may find that after the transormation the substring will be of the form
111… 000000…100000… so one needs to find the unique position of 1 for each substring in fast way then one can use Run length encoding to quickly store it as 1-[count]-0-[count]-1-0-[count].

O(n^2)

https://www.codechef.com/viewsolution/40425704
for reference (here it does not have run length encoding) and was TLE for t>900 . cuz we were storing the whole strings in set

String x ="";

                if(curr==-1){
                    x = "0-"+len;
                }else{
                    sbb.setLength(0);
                    len-=curr+1;                    
                    sbb.append("1-"+count);
                    sbb.append("-0-"+(curr-count));
                    sbb.append("-1-");
                    sbb.append("0-"+(len));
                    x = sbb.toString();
                }

This is Run length encoding snippet
i dont know why but my latest submission is not showing up but got AC though.

An example
0010001 0101 -> 1000100 0101
notice we found the first pair and reversed it to bubble up the q at starting position
1 00010001 01 -> 110001000 01
11 000100001 -> 11100001000

https://www.codechef.com/submit/complete/40445272

3 Likes

I also solved this problem similarly. @resda

1 Like

I also did it in greedy way and accumulated all (but last) 1’s in the beginning of the result. I calculated the hash to store this result string myself (using the hash from previous result) so as to avoid repeated computations. After implementing the hash function I noticed that I was getting same hash for different strings, so that’s why I have to implement Double Hashing. Here is the link to my solution.
https://www.codechef.com/viewsolution/40427313
P.S. - I also tried to store the result string in set/unordered_map, but it was giving me TLE due to internal hash computations(which was taking O(n) time per string in worst case) for each result string.

At least, explain the testcases properly. And how out of nowhere comes the observation 3?

3 Likes

Instead you could have just used a bigger prime number for calculating your hash! Something in the range of 10^16.

2 Likes

Hi, there is a proof written for the observation 3. Please go through it.

I feel like an idiot after seeing the explanation :slightly_frowning_face:
Another lesson learnt today :+1:

1 Like

image

Can anybody appreciate this … even ACRush(7 star) did it in 7 minutes he might took atleast 30 seconds to read … what’s going on…

no it isn’t the same, you use 3 for loops

My solution/explanation is like almost similar to editorialist but little bit different.

Let any string with x 1’s see this way. There are x+1 partitions divided by 1’s. In every partition there are some non-negative 0’s. Let name the paritions 1,2,3,…,x+1.
Claim - We can move any 0 from odd number partition to any other odd number partition. Similarly any 0 from even number partition to any other even number partition.

For example , (00)1(0)1()1(00)1(00) [ ‘(’ and ‘)’ are just for visualising partitions, not part of string]
Moves to move a 0 from 1st partition to 5th partition(first 1st to 3rd then 3rd to 5th)
00101100100 -> 01010100100 ->01011001000
(00)1(0)1()1(00)1(00) --swap(1,4)–> (0)1(0)1(0)1(00)1(00) --swap(5,9)-> (0)1(0)1()1(00)1(000)

For every substring, we calculate a triple - (no of 1’s, no of 0’s at odd partitions, no of 0’s at even partitions)

Number of distict such triples is answer. As any two substrings with same triple can be transformed in each other with a series of movements. It can be proved that after any valid transformation values of tuple don’t change.

https://www.codechef.com/viewsolution/40114832

5 Likes

Ok. Thanks for the suggestion. I tried it and it worked fine.
https://www.codechef.com/viewsolution/40450605

if i submit code for 3 problems in 1 min (after testing it on my laptop for hours) and get AC does it mean i only took 1 min to solve all 3 ?

After doing some example transformations , i observed , [ n is the the number of ones in the string ]

In any string we can move all (n-1) one’s to right or left

The number of zero’s between this last 1 to previous 1 will give you the
equivalence class.

After shifting all 1’s to left the number of zero’s between the last two 1’s will equal if both strings belong to the same class or similarly differ if both the strings will not belong to the same class.

And of course the length of two strings should be equal.

But i didn’t find a way to prove this , but now after reading your post , it make sense and it can be proved easily.

1 Like

I have done what is told in the editorial using python but still i am getting TLE.

Code

def f(s):
n=len(s)
ans=[]
for i in range(n):
for l in range(i+1,n+1):
#print(s[i: l])
ans.append(s[i:l])
return ans

for _ in range(int(input())):
s=input()
a=f(s)
ans=set()
for i in a:
l=len(i)
t=0
c=0
for j in range(l):
if(i[j]==‘1’):
t+=1
if(t%2==1):
c+=1
ans.add((len(i),i.count(‘1’),c))
print(len(ans))
#print(ans)

here is the LINK
Can someone tell me what i am doing wrong here?

I have stored the decimal values of substrings instead and tried to make each decimal number to minimum. I have used dictionary here. Finally it worked :slight_smile:
Here is my solution ( in python3):
https://www.codechef.com/viewsolution/40384412

@resda can you please explain your algo in detail for how you were bringing all the one’s to the beginning . I tried the same thing but I was making the string lexicographically smallest string .But it didn’t work .