In this HackerEarth vs 3 problem solution The fight for the best number in the globe is going to finally come to an end.The top two contenders for the best number are number 2 and number 3.It's the final the entire world was waiting for. Expectorates from all across the globe came to witness the breath taking finals.
The finals began in an astonishing way.A common problem was set for both of them which included both these number.The problem goes like this.
Given a binary string (that is a string consisting of only 0 and 1). They were supposed to perform two types of query on the string.
Type 0: Given two indices l and r.Print the value of the binary string from l to r modulo 3.
Type 1: Given an index l flip the value of that index if and only if the value at that index is 0.
The problem proved to be a really tough one for both of them.Hours passed by but neither of them could solve the problem.So both of them wants you to solve this problem and then you get the right to choose the best number in the globe.
HackerEarth 2 vs 3 problem solution.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#include<climits>
#include<stack>
using namespace std;
typedef long long int ll;
ll arr[100005]={0},tree[400005]={0};
struct in
{
ll val,length;
};
typedef struct in in;
void cons(ll ss,ll se,ll si)
{
if(ss>se)
return;
if(ss==se)
{
tree[si]=arr[ss];
//cout<<"&&&"<<ss<<" "<<arr[ss]<<endl;
return ;
}
ll mid=(ss+se)/2;
cons(ss,mid,2*si+1);
cons(mid+1,se,2*si+2);
ll rLength=(se-(mid+1))+1;
ll rVal=tree[2*si+2];
ll lVal=tree[2*si+1];
ll x=0;
if(lVal==2)
{
//x=(1<<(rLength+1));
if((rLength+1)%2==0)
x=1;
else
x=2;
}
else if(lVal==1)
{
//x=(1<<rLength);
if((rLength)%2==0)
x=1;
else
x=2;
}
x+=rVal;
x=x%3;
/*ll mVal;
if(rLength%2==0)
mVal=1;
else
mVal=2;
x=((lVal%3*mVal%3)%3+rVal%3)%3;
*/
tree[si]=x;
return;
}
in query(ll ss,ll se,ll s,ll e,ll si)
{
if(ss>se || s>se || e<ss)
{
return ((in){0,0}); //check
}
if(ss>=s && se<=e)
{
ll len=(se-ss)+1;
return ((in){tree[si],len});
}
ll mid=(ss+se)/2;
//ll rLength=(se-(mid+1))+1;
ll rLength=0,lLength=0;
in left=query(ss,mid,s,e,2*si+1);
in right=query(mid+1,se,s,e,2*si+2);
ll x=0;
ll lVal=left.val;
ll rVal=right.val;
lLength=left.length;
rLength=right.length;
//rLength=(se-(mid+1))+1;
//cout<<ss<<" "<<se<<" "<<lLength<<" "<<rLength<<" "<<lVal<<" "<<rVal<<endl;
if(lVal==2)
{
//x=(1<<(rLength+1));
if((rLength+1)%2==0)
x=1;
else
x=2;
}
else if(lVal==1)
{
//x=(1<<rLength);
if((rLength)%2==0)
x=1;
else
x=2;
}
x+=rVal;
x=x%3;
/*ll mVal;
if(rLength%2==0)
mVal=1;
else
mVal=2;
x=((lVal%3*mVal%3)%3+rVal%3)%3;
*/
ll length=lLength+rLength;
return ((in){x,length});
}
void update(ll ss,ll se,ll p,ll si)
{
if(ss>se || p>se ||p<ss)
{
return ;
}
if(ss==p && se==p)
{
tree[si]=1;
return;
}
ll dist=se-p;
ll val=tree[si];
if(dist%2==0)
val+=1;
else
val+=2;
val=val%3;
tree[si]=(val);
ll mid=(ss+se)/2;
if(ss<=p&&mid>=p)
update(ss,mid,p,2*si+1);
else if(mid+1<=p&&se>=p)
update(mid+1,se,p,2*si+2);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
string s;
ll tc,n,i,q,a,l,r,p;
memset(tree,0,sizeof(tree));
memset(arr,0,sizeof(arr));
cin>>n;
cin>>s;
for(i=0;i<n;i++)
{
arr[i]=s[i]-'0';
//cout<<arr[i]<<endl;
}
cons(0,n-1,0);
cin>>q;
while(q--)
{
cin>>a;
if(a==0)
{
cin>>l>>r;
cout<<query(0,n-1,l,r,0).val<<endl;
}
else
{
cin>>p;
if(arr[p]==1)
{
//cout<<"nothing done"<<endl;
}
else
{
arr[p]=1;
update(0,n-1,p,0);
}
}
}
return 0;
}Second solution
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
#include<unordered_set>
//#include<quadmath.h>
using namespace std;
namespace test{
void end_test(){
int val;
if (cin >> val){
exit(1);
}
}
void range_test(int t, int l, int r){
if (t < l || r < t){
exit(1);
}
}
}
#define MOD 3LL
#define MAX 100002
int n;
int q;
char s[MAX];
int a[MAX];
struct st{
bool flag;
long long int val;
int rang;
st(){
flag = false;
val = 0;
rang = 0;
}
};
long long int p2[MAX];
st seg[MAX*4];
void update(int b){
if (seg[b].flag){
seg[b].val = p2[seg[b].rang] + MOD - 1LL;
seg[b].val %= MOD;
if (b * 2 + 1 < MAX * 4){
seg[b * 2 + 1].flag = true;
}
if (b * 2 + 2 < MAX * 4){
seg[b * 2 + 2].flag = true;
}
seg[b].flag = false;
}
}
inline void init(int b, int l, int r){
seg[b].rang = r - l;
if (l + 1 == r){
seg[b].val = a[l];
return;
}
init(b * 2 + 1, l, (l + r) >> 1);
init(b * 2 + 2, (l + r) >> 1, r);
seg[b].val = seg[b * 2 + 1].val*p2[seg[b * 2 + 2].rang] + seg[b * 2 + 2].val;
seg[b].val %= MOD;
}
inline void add(int b, int l, int r, int ll, int rr){
update(b);
if (rr <= l || r <= ll){
return;
}
if (ll <= l&&r <= rr){
seg[b].flag = true;
update(b);
return;
}
add(b * 2 + 1, l, (l + r) >> 1, ll, rr);
add(b * 2 + 2, (l + r) >> 1, r, ll, rr);
seg[b].val = seg[b * 2 + 1].val*p2[seg[b*2+2].rang] + seg[b * 2 + 2].val;
seg[b].val %= MOD;
}
st emp;
inline st qq(int b, int l, int r, int ll, int rr){
update(b);
if (rr <= l || r <= ll){
return emp;
}
if (ll <= l&&r <= rr){
return seg[b];
}
st k=qq(b * 2 + 1, l, (l + r) >> 1, ll, rr);
st k2=qq(b * 2 + 2, (l + r) >> 1, r, ll, rr);
k.rang += k2.rang;
k.val *= p2[k2.rang];
k.val += k2.val;
k.val %= MOD;
return k;
}
int main(){
scanf("%d", &n);
scanf("%s", s);
test::range_test(n,1,100000);
for (int i = 0; i < n; i++){
a[i] = s[i] - '0';
test::range_test(a[i],0,1);
}
p2[0] = 1LL;
for (int i = 1; i < MAX; i++){
p2[i] = p2[i - 1];
p2[i] *= 2LL;
if (p2[i] >= MOD){
p2[i] %= MOD;
}
}
init(0, 0, n);
int q;
scanf("%d", &q);
while (q--){
int ty;
int a;
int b;
scanf("%d", &ty);
test::range_test(ty,0,1);
if (ty == 0){
scanf("%d%d", &a, &b);
if(a>b){
return 1;
}
test::range_test(a,0,n-1);
test::range_test(b,0,n-1);
st ans = qq(0, 0, n, a, b + 1);
printf("%lld\n", ans.val);
}
else{
scanf("%d", &a);
test::range_test(a,0,n-1);
add(0, 0, n, a, a + 1);
}
}
return 0;
}
0 Comments