BSXOR-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Nishank Suresh, Satyam
Editorialist: Devendra Singh

DIFFICULTY:

Simple

PREREQUISITES:

bitwise XOR operation

PROBLEM:

Chef has a binary string S of length N. He wonders if it is possible to divide S into exactly K non-empty substrings such that each S_i belongs to exactly one substring and the \texttt{XOR} of each substring is the same. Can you help Chef to determine if it is possible to do so?

Note: \texttt{XOR} of substring S_{L \cdots R} is defined as: \texttt{XOR} (S_{L \cdots R}) = S_L \oplus S_{L+1} \oplus \cdots \oplus S_R.

Here, \oplus denotes the bitwise XOR operation.

EXPLANATION:

The bitwise XOR of any binary string is either 0 or 1. Therefore if an answer exists then it is either K non-overlapping substrings having XOR equal to 1 or K non-overlapping substrings having XOR equal to 0. We can iterate over the binary string and check whether we can divide the string into K non-overlapping substrings having XOR equal to 0 or K non-overlapping substrings having XOR equal to 1
We can greedily select the first K-1 substrings having same XOR (0\: or\: 1) and check whether there XOR is equal to the substring formed by the remaining characters. If it is equal output YES else NO.

We can show that if an answer exists it can always be constructed by this greedy approach.
Suppose there exists an answer such that the first K-1 substrings are not selected greedily, let it be S[1,S_1],S[S_1+1,S_2],....................S[S_{K-1}+1,N], where S_i is the right end of the selected substring. Let there be and index S_0 < S_1 such that XOR of substring S[1,S_1] is same as XOR of substring S[1,S0], we select S[1,S0] as the first substring and append the remaining characters of substring S[1,S_1] to the start of the second string. The XOR of 1st and 2nd substrings remains same as XOR\:of\: S[1,S_0]=S[1,S_1] and XOR\:of\:S[S_0+1,S_2]=S[1,S_2]\oplus S[1,S_0] = S[S_1+1,S_2] as XOR of S[1,S_1]=S[1,S_0] Now move to the next substring and keep on repeating the same procedure until all the K-1 substrings are selected greedily i.e. we select the substring as soon as the XOR becomes equal to what we need (0\: or\: 1).

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's Solution

#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(…)
#endif

#define int long long
#define endl β€œ\n”
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5;

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == β€˜-’)
{
assert(fi == -1);
is_neg = true;
continue;
}
if(β€˜0’ <= g && g <= β€˜9’)
{
x *= 10;
x += g - β€˜0’;
if(cnt == 0)
fi = g - β€˜0’;
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ’ ’ << r << ’ ’ << x << β€˜\n’;
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}

string readString(int l, int r, char endd)
{
string ret = β€œβ€;
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ’ '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, β€˜\n’); }
string readStringLn(int l, int r) { return readString(l, r, β€˜\n’); }
string readStringSp(int l, int r) { return readString(l, r, ’ '); }
void readEOF() { assert(getchar() == EOF); }

vector readVectorInt(int n, long long l, long long r)
{
vector a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

void solve()
{
int n = readIntSp(1, 1e5);
int k = readIntLn(1, n);
string s = readStringLn(n, n);
bool ok = false;
for(int x: {0, 1})
{
int cur = 0, cnt = 0, i = 0;
for(; i < n and cnt < k - 1; i++)
{
cur ^= s[i] - β€˜0’;
if(cur == x)
cnt++, cur = 0;
}
if(i == n)
continue;
for(; i < n; i++)
cur ^= s[i] - β€˜0’;
ok |= (cur == x);
}
cout << (ok ? β€œYES” : β€œNO”) << endl;
}

int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1e5);
for(int tc = 1; tc <= T; tc++)
{
// cout << β€œCase #” << tc << ": ";
solve();
}
return 0;
}

Tester-1's Solution(Python)
for _ in range(int(input())):
	n, k = map(int, input().split())
	s = input()
	zeros, ones, pref = 0, 0, 0
	for c in s:
		if c == '1':
			pref ^= 1
		zeros += pref == 0
		ones += pref != (ones%2)
	print('YES' if (pref == 0 and zeros >= k) or (ones >= k and ones%2 == k%2) else 'NO')
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif 
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){  
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
int MAX=100000;
int check_bin(string s){
    for(auto it:s){
        if((it!='0')&&(it!='1')){
            return 0;
        }
    }
    return 1;
}
int sum_cases=0;
void solve(){
    int n=readIntSp(1,MAX); int k=readIntLn(1,n);
    sum_cases+=n;
    string s=readStringLn(n,n);
    assert(check_bin(s));
    int now=0;
    vector<int> track; int zro=0;
    for(int i=0;i<n;i++){
        now+=s[i]-'0'; now=now%2;
        track.push_back(now); zro+=now==0;
    }  
    int freq=0; 
    if((k%2==0)&&(now)){
        cout<<"NO\n";
        return;  
    }
    if(k%2==0){
        if(zro>=k){  
            cout<<"YES\n";
            return;
        }
        now=1;
    }
    else{
        now=track.back();
    }
    int us=now;
    for(int i=0;i<n;i++){
        if(track[i]==now){
            now^=us;
            freq++;
        }
    }
    if(freq>=k){  
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);                              
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                          
    #endif         
    int test_cases=readIntLn(1,MAX); 
    while(test_cases--){
        solve();
    }
    assert(getchar()==-1);
    assert(sum_cases<=2*MAX); 
    return 0;
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int x = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            x ^= 1;
        if (x == 1 && cnt<k-1 && i!=n-1)
            cnt++, x = 0;
    }
    if (cnt == k-1 && x==1)
    {
        cout << "YES\n";
        return;
    }
    x = cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            x ^= 1;
        if (x == 0 && cnt<k-1 && i!=n-1)
            cnt++;
    }
    if (cnt == k-1 && x==0) 
    {
        cout << "YES\n";
        return;
    }
    else
        cout << "NO\n";
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}

1 Like

i have a doubt in test case of 111, why no soln? can’t we split it as [1, 2] and [3,3] substring? as of the first substring 1 ^ 1 = 0 and for second also 1 ^ 1 = 0 , what i have missed??

[1, 2] and [3, 3] will be 11 and 1.
The second sub-string have only one character, so for first sub-string 1 ^ 1 = 0, and for second sub-string 1 = 1.
There’s no way to split 111 into two sub-strings with same xor.

3 Likes

Oh, i was confused whether we have to take single element xor with itself, thanks got it

Could anyone point out the three test cases I missed?

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

1 Like

Can someone tell me what is wrong with this approach ?
https://www.codechef.com/viewsolution/62874598

Can I know tasks 1 and 2 in subtask 1 to know where my solution went wrong

https://www.codechef.com/viewsolution/62812907
Any idea why this solution is giving WA ?

Hey @parzival18s :wave:
there is the problem of index of bound in else as when w becomes n in if condition it will point null value.

1 Like

I see. That was a terrible blunder on my side. Thanks for pointing it out.

1
4
1111