Funny marbles is a problem from Dec 2013 Challenge and here’s the link for this problem http://www.codechef.com/problems/MARBLEGF
Given an array of marbles each student has initially we can have 3 queries
1.S 0 2 -> Sum of(marbles of 0th student to marbles of 2nd student).
2.G 0 3 -> Give 3 marbles to 0th student.
3.T 1 2 -> Take 2 marbles from 1st student.
Our aim is that for each (S x1 y1) query you need to output the sum of marbles from x1th to y1th student.
eg. There are 8 students and we have marbles each student initially has.
Let this be
1 2 3 4 5 6 7 8
Query S 0 2 gives 6 i.e (1+2+3).
Query G 0 3 would make marbles of 0th student to 4.
Query S 0 2 gives 9 i.e (4+2+3) now.
Brute force approach: If your query is S x1 y1 then traverse students from x1 to y1 and go addding the marbles and storing it in a variable(say sum).
But as the number of student can range at max to 1000000 so obviously this approach would fetch a TLE (Time limit exceeded) error.
**My approach:**While each element is input we calculate the cumulative sum of marbles from index 1 to index of the element we are inputting.
eg.
A 1 2 3 4 5 6 7 8
cs 1 3 6 10 15 21 28 36
Let the index of cs[] start with 1.
cs[] can be initialised using below code fragment:
cs[0]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&no);
cs[i]=cs[i-1]+no;
}
Updation : Now you can declare a structure and array of structures using the following code fragment:
typedef struct s{
int pos;
long long int gt;
}s;
s sp[50000];
pos denotes to which student we have given/taken marbles and gt is its value.
sp is an array of structures with 50000(no of queries) elements in it.
Now consider the queries
G 0 3
S 0 2
1.sp[0].pos=0 and sp[0].gt=3.
2.When entertaining the sum query you should traverse sp[j] where j are the elements in sp[].
For a given element in the sum query,if sp[] includes that student then add its gt to a var.
By this you would come to know for a given student in the sum query what is the effective value of gt and it would be stored in var.
3.Now doing this for all students in the sum query you would come to know the total effective value of gt for all students which can be stored in a variable(final value of var).
After all elements in sp[] have been travelled then the required answer will be cs[3]-cs[0]+var for the above case.
Now if the constraints were more strict(no of queries are much more)then by this approach you have to traverse all elements in sp[] to find out for what students we have done g/t operation.
So this approach would give a TLE if number of queries is bigger.
Optimized approach (using Fenwick trees):
As you may note that the main problem for the above approach came when we had to entertain a sum query after some g/t operations as we had to traverse all of them.
Lira’s mom has A[i] where i starts from 0.We are maintaing ft[] starting from index 1.
Now in fenwick trees we want to do this:
A 1 2 3 4 5 6 7 8
ft 1 3 3 10 5 11 7 36
ft[1]=1
ft[2]=1+2
ft[3]=3
ft[4]=1+2+3+4
ft[5]=5
ft[6]=6+7
ft[7]=7
ft[8]=1+2+3+4+5+6+7+8
to do this you can follow the below code fragment:
for(i=1;i<=n;i++)
{
scanf("%d",&a);
no=i;
while(no<=n)
{
ft[no]=ft[no]+a;
no=no+(no&-no);
}
}
suppose i=1 then no=1.After a is added to ft[1] then
no=0001
2's complement of no=1110+1=1111
no&2's comp=0001 & 1111=0001
0001+0001=0010 i.e 2
a is added to ft[2].
Then by same procedure a is added to ft[4] and ft[8].
do this for all i<=n.
So now we have initialised ft[] and we are ready to entertain queries.
Now consider the below code fragment which would calculate result of sum query for us.
y1++;
sum1=sum2=0;
while(x1>0||y1>0)
{
if(x1!=0)
sum1=sum1+ft[x1];
sum2=sum2+ft[y1];
if(x1!=0)
x1=x1&(x1-1);
y1=y1&(y1-1);
}
s=sum2-sum1;
temp[k++]=s;
For query S 5 7
sum1=ft[5]+ft[4]=5+10=15
sum2=ft[8]=36
So s= 21
Now comes the updation case.Suppose your query is G 3 3
x1++=0+1=1
while(x1<=n)
1.update ft[x1]
2.calculate x1 using formula x1=x1+(x1&-x1)
So ft[3],ft[4] and ft[8] have been updated.
Now if a query like S 5 7 is needed to be entertained
sum2 = ft[8]
sum1= ft[5]+ft[4]
sum2-sum1=21
As 3 was not in the range of 5 to 7,so increase of 3 in ft[8] was balanced by an equivalent increase in ft[4].
So for every g/t operation on a student you just update some ft[…] that you have put a student into.
eg.
You added 0th student marbles into ft[1],ft[2],ft[4] and ft[8].So for any updations made to 0th student marbles,you would also update the above ft[…].
So while entertaining a g/t query you just update corresponding ft[…] and when you are asked to calculate the sum of a given range you apply the above while loop for sum query and you are done.
**Note:**No need to traverse all g/t operations as in my approach.
My vote of thanks to all who helped to unveil the logic of this problem and made me march a step further.
