PROBLEM LINK:
Author: vikiwarrior
Tester: hellb0y_suru
Editorialist: vikiwarrior
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
You need to find whether it is possible to divide the string into 3 contiguous non-empty segments such that the score of every segment is the same and each character must belong to exactly one segment.
Score = V*X, where V is the decimal value of the bitstring when treated as binary and X is xor of each element of the bitstring.
EXPLANATION:
First observe that there are two factors affecting the score: the first one is the decimal value and the inter one is the XOR of elements.
If the XOR of the subarrays are zeros, we don’t need to care about the decimal values as the score will be 0.
We know that segment has even no. of ones then xor of value is zero.
Now, we can observe that if any even no. greater than 4 can be broken as a sum of three even nos hence if no of the ones in the bitstring is even and greater than 4 then the answer is “Yes“.
For, no. of ones equal to 2 and 4 we will write special cases.
Now, for odd nos of ones we can ensure that xor of all three segments cannot be 0 hence it has to be one and the binary value should be the same for the score to be equal.
If decimal values are equal then we can safely say that no. of ones in every segment should be the same. That means for no. of ones which are odd and not divisible by 3 the answer will be “No”.
For the rest cases that is when no. of one is odd and divisible by 3, you can check the identify the three segments as they will have exactly total no of one divided by 3 no. of 1’s in them. Now check if they have the same decimal value if yes then print “Yes” else “No”. The implementation of this can be seen in the author’s code.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
int n;
cin >> n;
cin >> s;
int i;
int c = 0;
for (i = 0; i < n; i++)
{
if (s[i] == '1')
{
c++;
}
}
if (c % 2 == 0)
{
if (c == 2)
{
vector<int> pos;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
pos.push_back(i);
}
if (n - (pos[1] - pos[0] + 1) >= 2)
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
}
else if (c == 4)
{
vector<int> pos;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
pos.push_back(i);
}
if ((pos[2] - pos[1] - 1 > 0) || n - (pos[3] - pos[0] + 1) >= 2)
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
}
else
{
cout << "YES\n";
}
}
else
{
int ones = c;
if (ones % 3)
{
cout << "No" << endl;
continue;
}
int k = ones / 3;
int firstone = 0;
vector<int> pos;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
{
firstone++;
}
if (firstone == 1 && s[i] == '1')
{
pos.push_back(i);
}
if (firstone == k)
{
firstone = 0;
}
}
int start = pos[0];
int mid = pos[1];
int end = pos[2];
while (end < n && s[start] == s[mid] && s[mid] == s[end])
{
start++;
mid++;
end++;
}
if (end == n)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
}
return 0;
}
Tester's Solution
#include "bits/stdc++.h"
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T>
ostream &operator<<(ostream &output,const vector<T> &v){
if(v.empty()) return output;
for(int i=0;i<v.size()-1;i++) output << v[i] <<" ";
output << v.back();
return output;
}
template<typename T>
istream &operator>>(istream &input,vector<T> &v){
for(auto &i: v) cin >> i;
return input;
}
int power(long long x,long long n,const long long P){
if(x==0) return 0;
if(n==0 || x==1) return 1LL;
x%=P;
int res = 1;
while(n>0){
if(n&1) res = (ll) res * x %P;
x = (ll) x * x % P;
n/=2;
}
return res;
}
long long int power(long long int x,long long int n){
if(x==0) return 0;
else if(n==0 || x==1) return 1;
long long res = 1;
while(n>0){
if(n&1) res *= x;
x *= x;
n /=2;
}
return res;
}
int inv(long long x){ return power(x,MOD-2,MOD);}
long long int gcd(const long long int a,const long long int b){
if(b == 0) return a;
return gcd(b,a%b);
}
long long int lcm(const long long int a,const long long int b){
return (a*b)/gcd(a,b);
}
pair<int,int> dx[4] = {make_pair(-1,0),make_pair(1,0),make_pair(0,-1),make_pair(0,1)};
void __sol(){
int n; cin >> n;
string s; cin >> s;
int cnt = 0;
for(auto &i: s) cnt+= i == '1';
if(cnt==0) puts("Yes");
else if(cnt == 1) puts("No");
else if(cnt == 2){
if((s[0]=='0' && s[1]=='0')||(s[n-1]=='0' && s[n-2]=='0')||(s[0]=='0' && s[n-1]=='0')) puts("Yes");
else puts("No");
}
else if(cnt == 4){
if((s[0]=='0' && s[1]=='0')||(s[n-1]=='0' && s[n-2]=='0')||(s[0]=='0' && s[n-1]=='0')) puts("Yes");
else{
int i = 0;
cnt = 0;
for(;i<n && cnt<2;i++){
cnt+=s[i]=='1';
}
s[i]=='0' ? puts("Yes") : puts("No");
}
}
else if(cnt%3==0 && cnt&1){
string a="",b="",c="";
cnt/=3;
int lastzero = 0;
while(!s.empty() && s.back()=='0') lastzero++ , s.pop_back();
n = s.size();
bool f = 1;
int i = 0;
while(i<n && s[i]=='0') i++;
int gg = 0;
while(i<n && gg<cnt){
gg += s[i]=='1';
a+=s[i];
i++;
}
int x = 0;
while(i<n && s[i]=='0') i++ , x++;
if(x<lastzero) f = 0;
gg = 0;
while(i<n && gg<cnt){
gg += s[i]=='1';
b += s[i];
i++;
}
x = 0;
while(i<n && s[i]=='0') i++ , x++;
if(x < lastzero) f = 0;
while(i<n) c+=s[i],i++;
if(a==b && b==c && f) puts("Yes");
else puts("No");
}
else{
if(cnt%2==0) puts("Yes");
else puts("No");
}
return;
}
int main(){
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
clock_t time_req = clock();
fastio;
int tc=1; cin >> tc;
while(tc--) __sol();
time_req = clock() - time_req;
// cerr << "Finished in: "<< (float)time_req/CLOCKS_PER_SEC << " seconds" << endl;
return 0;
}