PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
You’re given a binary string S, and an empty basket.
Process Q queries.
Each query gives you [L, R], requiring you to add S[L, R] to the basket.
After each query, answer whether it’s possible to rearrange the strings in the basket to form the binary representation of an integer that’s divisible by 3.
EXPLANATION:
First, let’s understand how the binary representation of a number relates to its divisibility by 3.
Lemma: Let K be a non-negative integer, such that its binary representation has x even powers and y odd powers of 2.
Then, K is divisible by 3 if and only if x-y is a multiple of 3.Proof
For any integer k \geq 0, we have 2^{2k} \equiv 1 \pmod 3 and 2^{2k + 1} \equiv 2 \pmod 3.
So, when writing a number as a sum of powers of two, even and odd powers can be “paired up” to become 0, till we’re left with only occurrences of the same parity of power at which point their count has to be a multiple of 3 for the sum to be a multiple of 3.
Now, coming to the actual problem.
We have several strings with us in the basket, which must all be concatenated to form a single longer binary string.
As noted above, what really matters to us is the difference between the count of even and odd powers of 2 in the final concatenation, which we’d like to be a multiple of 3 (equivalently, 0 modulo 3).
Let d_i denote the number of even powers minus the number of odd powers in the i-th string added into the basket.
Note that when these strings are placed in order and concatenated, the i-th string will contribute either d_i or -d_i to the difference, depending on whether the total number of characters after it is even or odd respectively (since an odd number of characters will flip what even and odd mean to it).
The only way to control parity is of course to have an odd-length string.
So, for each string in the basket, there are really two parameters that matter: its d_i value (i.e. difference between counts of ones at odd and even positions), and the parity of its length.
So, there are 6 types of strings in our basket, and knowing each of their counts, we need to figure out whether d_i or -d_i can be chosen for each one so that the resulting summation ends up being 0 modulo 3.
Let c_{xy} denote the count of strings with us which have d_i = x, and a length parity of y (where y = 0 denotes even and y = 1 denotes odd).
We now (unfortunately) need to do a bit of casework.
First, suppose we don’t have any odd-length strings at all, i.e. c_{x1} = 0 for all x.
Then, we’re unable to change any d_i to -d_i, so the only thing we can do is sum up all the d_i and check if it ends up being a multiple of 3 or not.
Now, suppose we do have odd-length strings.
Note that every even-length string can now be freely chosen to have value either d_i or -d_i, by placing it either right at the end (no odd length strings after it) or just before the last odd-length string placed.
This gives us a lot of freedom: in fact, if we have at least two even-length strings with non-zero d_i, the answer is always Yes!
How?
Suppose you have two even-length strings with value 1.
Then, depending on how many of them are made -1, it’s possible to get all three of the values \{-1, 0, 1\} which correspond to \{0, 1, 2\} modulo 3.
So, we can simply arrange the other strings however we like, and then choose an appropriate arrangement of these last two strings to get a sum of 0.
You can verify that a similar setup works for two strings with value 2, and also one value-1 string and one value-2 string.
That leaves us with the case where there’s at most one even string with non-zero value.
There are now only two options for it: either d_i or -d_i; we can simply try both - which brings us to the last remaining detail: how to arrange the odd-length strings to get the result we want?
This is left as an exercise to the reader 
(You can look at the code attached below if you’re stuck).
One thing not mentioned above was how to actually compute the d_i values for each queried substring, but that’s a trivial exercise in prefix sums.
TIME COMPLEXITY:
\mathcal{O}(N + Q) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
using namespace std;
//0 010 1 2
//1 0 010 0
//0 1 010 1
bool solve(int s_01,int s_10,int s_1,int s_010,int s_0){
int odd = s_1 + s_010 + s_0;
int mx = max({s_1,s_0,s_010});
int mn = min({s_1,s_0,s_010});
if(mn >= 1)return 1;
int even = s_01 + s_10;
if(odd == 0){
int fin = s_10*2 + s_01*1;
fin %= 3;
if(fin)return 0;
return 1;
}
else{
if(even >= 2)return 1;
if(odd == mx){
int fin = odd&1;
if(s_0)fin = 0;
if(even){
if(fin)return 1;
return 0;
}
else{
if(fin)return 0;
return 1;
}
}
if(odd-mx >= 2)return 1;
if(!(odd&1)){
if(even)return 1;
else return 0;
}
if(s_0 <= 1)return 1;
else{
if(even)return 1;
else return 0;
}
}
}
void solve()
{
int n,q;
cin >> n >> q;
string s;
cin >> s;
int s_01 = 0,s_10 = 0,s_1 = 0,s_010 = 0,s_0 = 0;
vector<int> sf(n);
rrep(i,n-1,0){
if(s[i] == '1'){
if((n-1-i)&1)sf[i] = 2;
else sf[i] = 1;
}
}
rrep(i,n-2,0){
sf[i] += sf[i+1];
sf[i] %= 3;
}
while(q--){
int l,r;
cin >> l >> r;
l--;r--;
int sm = sf[l] - (r+1<n?sf[r+1]:0);
if((n-1-r)&1)sm *= 2;
sm %= 3;sm += 3;sm %= 3;
if((r-l)&1){
if(sm == 1)s_01++;
else if(sm == 2)s_10++;
}
else{
if(sm == 1)s_1++;
else if(sm == 2)s_010++;
else s_0++;
}
// cout << s_01 << " " << s_10 << " " << s_1 << " " << s_010 << " " << s_0 << "\n";
bool ans = solve(s_01,s_10,s_1,s_010,s_0);
cout << (ans ? "YES\n" : "NO\n");
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll e[3];
ll o[3];
ll solve(){
if((o[0]+o[1]+o[2])==0){
return (e[1]+2*e[2])%3;
}
ll x=e[1]+e[2];
if(x>=2){
return 0;
}
if(o[0] && o[1] && o[2]){
return 0;
}
ll mini,maxi,cnt;
ll z1=(o[0]+o[1]+o[2]+1)/2;
ll z2=(o[0]+o[1]+o[2])/2;
if(o[0] && o[1]){
mini=o[1];
if(z1<o[1]){
mini+=(o[1]-z1);
}
maxi=2*o[1];
if(z2<o[1]){
maxi-=(o[1]-z2);
}
if(x==0){
while(mini<=maxi){
if(mini%3==0){
return 0;
}
mini++;
}
return 1;
}else{
if(mini==maxi && mini%3==0){
return 1;
}else{
return 0;
}
}
}
if(o[0] && o[2]){
mini=o[2];
if(z1<o[2]){
mini+=(o[2]-z1);
}
maxi=2*o[2];
if(z2<o[2]){
maxi-=(o[2]-z2);
}
mini*=2;maxi*=2;
if(x==0){
while(mini<=maxi){
if(mini%3==0){
return 0;
}
mini+=2;
}
return 1;
}else{
if(mini==maxi && mini%3==0){
return 1;
}else{
return 0;
}
}
}
if(o[1] && o[2]){
if(min(o[1],o[2])>=2){
return 0;
}
if(min(o[1],o[2])==o[1]){
mini=1;maxi=2;
}else{
mini=2;maxi=1;
}
if(x==0){
cnt=mini+maxi*(z2*2+z1-1);
if(cnt%3==0){
return 0;
}
cnt=mini*2+maxi*(z2*2+z1-2);
if(cnt%3==0){
return 0;
}
return 1;
}else{
cnt=mini+maxi*(z2*2+z1-1);
if(cnt%3!=0){
return 0;
}
cnt=mini*2+maxi*(z2*2+z1-2);
if(cnt%3!=0){
return 0;
}
return 1;
}
}
mini=(z1+z2*2);
if(o[2]){
mini*=2;
}
if(o[0]){
mini=0;
}
maxi=mini;
if(x==0){
while(mini<=maxi){
if(mini%3==0){
return 0;
}
mini++;
}
return 1;
}else{
if(mini==maxi && mini%3==0){
return 1;
}else{
return 0;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
while(kitne_cases_hain--){
ll n,q;
cin>>n>>q;
string s;
cin>>s;
ll pre[n+1][2]={};
for(int i=0;i<3;i++){
o[i]=e[i]=0;
}
for(int i=0;i<n;i++){
if(s[i]=='1'){
pre[i+1][(i+1)%2]++;
}
pre[i+1][0]+=pre[i][0];
pre[i+1][1]+=pre[i][1];
}
ll l,r,x,y,ans;
while(q--){
cin>>l>>r;
x=(pre[r][r%2]-pre[l-1][r%2])+(pre[r][(r%2)^1]-pre[l-1][(r%2)^1])*2;x%=3;
if((r-l+1)%2){
o[x]++;
}else{
e[x]++;
}
ans=solve();
if(ans==0){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
}
return 0;
}