ADDMUL - Editorial

xrisk · July 13, 2015, 3:45pm

I think you have made a mistake in this sentence where you write

Set operation with value v can be
written as mul←1 and add←0.

Later on you write For setting all elements to v, we can just make one multiplication with 0 and then addition with value v.
So I guess mul, should be set to 0 and add to v?

ketanhwr · July 13, 2015, 3:48pm

This was an amazing problem! Took a lot of tinkering and checking. And obviously required some common sense

juststartedcd · July 13, 2015, 4:13pm

i did all the things specified above…buy creating an add[]and multiply[]array…and calculating the sum with lazy propagation still i was getting TLE all the time…i dont know where i was wrong…here is my code…
http://www.codechef.com/viewsolution/7474886

pls can someone tell me whats wrong…it will be a great help…

aviaryan · July 13, 2015, 4:38pm

Great problem. Really felt nice to solve this one. Thanks to the author.

rishabh_joshi_1 · July 13, 2015, 4:43pm

How (if) can we use ‘heavy light decomposition’ to solve this problem?

sagarpatel · July 13, 2015, 5:16pm

+1 to the editorialist, explanation is great, and mentioning the similar problems for practice, I really appreciate his efforts and Thanks!!

terminated · July 13, 2015, 5:17pm

the time limit has been set dumbly , I implemented everything as in editorial but then also got tle , CodeChef: Practical coding for everyone

root8950 · July 13, 2015, 8:40pm

@terminated I think time limit was well set

psbbboyz · July 13, 2015, 8:48pm

Hello all,

Is there some way of accessing the test cases for this problem statement? The contest judge declared that my solution was segfaulting. I generated test cases in the order as suggested in the problem statement which ran successfully in my machine, so I would like to check with the actual test cases where the segfaulting is occurring.

Thanks
Sudharshan

archazey · July 13, 2015, 10:32pm

What it is not mentioned is how you really do the propagation,a key element in this problem. This was my biggest problem. Here the priority of operations is important. You cannot do the propagation how you want…
So if you propagate from a node to right node,you know that the updates from node where made later( because of propagation itself).
Let’s say sum in right node is X(after we make all updates with its vals , add and mul).Now we come with information from node,knowing it was made later,it comes like that:(X+a1+a2+a3)a4a5+a6 … So mul and add from right node become mul*=mulnode and add=add*mulnode+addnode
That observation was important to me and I spent some time thinking …
If any of you found a easier way,please let me know!

punjabidon · July 14, 2015, 12:39am

Can anyone properly explain how to propagate the add and mul values to the left and right node? I think that point is a bit unclear in the editorial.

aragar · July 14, 2015, 2:25pm

Thanks a lot for the similar problems list

shivam312 · July 16, 2015, 6:00pm

What is the problem with this solution?

#include
#include <stdio.h>

using namespace std;

int main() {

long n, q, m = 1000000007L;
cin>>n>>q;
long a[n];
for(long i=0;i<n;i++)    {
    cin>>a[i];
}
long t, x,y, v;

for(long i=0;i<q;i++)    {
    cin>>t>>x>>y;
    x--;
    y--;
    
    if(t==1)    {
        cin>>v;
        for(long j=x;j<=y;j++)   {
            a[j]+=v;
            a[j]%=m;
        }
    }
    else if(t==2)   {
         cin>>v;
        for(long j=x;j<=y;j++)   {
            a[j]*=v;
            a[j]%=m;
        }
    }
    else if(t==3)   {
         cin>>v;
        for(long j=x;j<=y;j++)   {
            a[j]=v;
           // a[j]%=m;
        }
    }
    else if(t==4)   {
        int sum = 0;
        for(long j=x;j<=y;j++)   {
            sum+=a[j];
            sum%=m;
        }
        cout<<sum;
    }
}


return 0;

}

glow · July 16, 2015, 6:37pm

@shivam312 the only problem is that it is very slow. Suppose if we have 1000 queries and in each query we have L=1 and R=1000 than we u can see that nit will take a lot of time in doing computation. So thats why u get TLE.

sohamd95 · July 17, 2015, 11:44am

Amazing problem! I did it after reading the editorial. It took a while; but it really reinforced my understanding of segment trees. You can view my solution here if interested.

ashlesh123 · July 17, 2015, 2:41pm

I am getting WA
https://www.codechef.com/viewsolution/7492057

I am also getting WA on similar spoj problem SPOJ.com - Problem HORRIBLE
My spoj solution id Sphere Online Judge (SPOJ) - Submit a solution
I am not able to figure out why i am getting WA in both problems. Please help me out?