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:
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();
}
