# codechef question multiples of 3

guys i have been stuck in this question for hours …it’s a simple question but i don’t know where am i going wrong.could somebody tell me what’s wrong in the code:

``````#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int k[100004];
int tree[300000];
int inp()
{
int n=0;
char ch;
ch=getchar_unlocked();
while(ch>=48 && ch<=57)
{
n=(n<<3)+(n<<1)+ch-'0';
ch=getchar_unlocked();
}
return n;
}

void init(int node,int left,int right)
{
if(left==right)
{
if((k==0)||(k%3==0))
{
tree[node]=1;
}
return;
}
init(2*node,left,(left+right)/2);
init(2*node+1,(left+right)/2+1,right);
tree[node]=tree[2*node]+tree[2*node+1];
}
void update(int node,int left,int right,int a,int b)
{
if(a>right||b<left)
return;

if(left==right)
{
k++;
if(k%3==0)
{
tree[node]=1;
}
else
{
tree[node]=0;
}
return;
}

//cout<<"node "<<node<<" "<<left<<" "<<right<<endl;

update(2*node,left,(left+right)/2,a,b);
update(2*node+1,(left+right)/2+1,right,a,b);
tree[node]=tree[2*node]+tree[2*node+1];
}

int count(int node,int left,int right,int a,int b)
{
if(a>right||b<left)
return -1;

if(left>=a && right<=b)
{
return tree[node];
}
int p1,p2;

p1=count(2*node,left,(left+right)/2,a,b);
p2=count(2*node+1,(left+right)/2+1,right,a,b);
//cout<<"node "<<node<<" "<<p1<<" "<<p2<<endl;
if(p1==-1)
return p2;
if(p2==-1)
return p1;
else
{
return p1+p2;
}
}

int main()
{
int t,c,a,b,n,q,i;
scanf("%d%d",&n,&q);
memset(k,0,sizeof(k));
init(1,0,n-1);         //initialize the tree values

/*for(i=1;i<(1<<4);i++)
{
cout<<"tree["<<i<<"] = "<<tree[i]<<endl;
}*/
while(q--)
{
//scanf("%d%d%d",&c,&a,&b);
c=inp();
a=inp();
b=inp();
if(!c)
{
update(1,0,n-1,a,b);
}
else
{
printf("%d\n",count(1,0,n-1,a,b));

/*for(i=1;i<(1<<4);i++)
{
cout<<"tree["<<i<<"] = "<<tree[i]<<endl;
}*/

}
}
return 0;
}``````

and here is the link of the question:http://www.codechef.com/problems/MULTQ3/

What was the question? or target problem?

i have posted the question link above…

The number of states you use in a segment are not enough. It is possible that in a range u can have all 3 kind of elements 3k,3k+1,3k+2 after the updates are done . So store the count of all 3 kinds of elements in each segment.

but i am updating the tree[] only when i reach the leaves and from there i update the rest of the segments…so why do i need to store all the three states?? can you elaborate??

I have a range from (1-8) and my elements are 1,1,1,2,2,2,3,3 . Tell me how will u store this information??

well,initially all the elements are index(0-7)0,0,0,0,0,0,0,0…when i run init()all the nodes of tree[](in this case 15 because of 15 sub intervals) will be set to their initial values(8,4,4,2,2,2,2,1,1,1,1,1,1,1,1,1).
the array can be reached in 3 updates:
1)increment 0 7 now arr[]={1,1,1,1,1,1,1,1}
and tree[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}(index 1 to 15)
2)increment 3 7 now arr[]={1,1,1,2,2,2,2,2}
and tree[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

3)increment 6 7 now arr[]={1,1,1,2,2,2,3,3}
and tree[]={2,0,2,0,0,0,2,0,0,0,0,0,0,1,1}

Okay firstly your inp() function doesn’t work correctly use scanf instead which i guess u figured out. The code u pasted above wasn’t working for the given sample test case also. So atleast check if ur code works for sample test cases or not.

Even then u will get Time Limit Exceeded(TLE) because ur update takes O(n) time which isn’t sufficient. Learn about Lazy Propagation with segment tree which is O(logn) for updating the interval in segment tree.

sorry for commenting in the answer section but i have checked my code for the sample test cases and the testcase you provided(using scanf)and they were giving the right results.but what you said about the update() is correct.it is O(n).But the code is giving wrong answer and i know whether it is due to faulty inp() or some error in the logic.

No people use comments to reply and answers section to answer the questions. I just typed in the answer section unknowingly. I saw u getting TLE for some submission. So maybe ur logic was correct but just takes more time. So try implementing it using the lazy propagation . Let me know if ur having trouble solving it.

well…thanks for the link…i will go through the lazy propagation and revert back to you for any doubts…

@saikrishna,could you explain to me when do we update the lazy node and how do we use it to update the tree node ? i am not getting it .

link This link is english translation but covers the whole idea. Try understanding this.

U update the lazy node only when u visit the node while traversing for update or query.

//