ADDMUL - Editorial

editorial
, , , ,
9

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

2 Likes
10

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

11

@terminated I think time limit was well set :slight_smile:

12

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

13

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! :slight_smile:

1 Like
14

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.

1 Like
15

Thanks a lot for the similar problems list :slight_smile:

16

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;

}

17

@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.

18

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.

19

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?

20

Can someone tell me what is wrong with my solution.I did as told in the Editorial.

https://www.codechef.com/viewsolution/7492127

21

What’s wrong with my solution?
https://www.codechef.com/viewsolution/7919583

1 Like
22

[JBAB5E - Online C++0x Compiler & Debugging Tool - Ideone.com][1]

Can you please check my code? What’s wrong with it?
[1]: JBAB5E - Online C++0x Compiler & Debugging Tool - Ideone.com

23

Very nice question to implement lazy propagation :slight_smile:

24

can anybody tell me what’s wrong with my solution?

here is the solution :
[solution][1]
[1]: CodeChef: Practical coding for everyone

25

Before switching to segtree i did square root decomposition CodeChef: Practical coding for everyone . It worked for 1st 2nd and 4th subtask but not for 3rd subtask .

3 Likes
26

@rajat1603: did you try applying fast I/O to your solution? it may get AC.

27

I think your code is update all the elements in the range as you are using the statement - if(st!-end)… i.e. you are not using lazy propagation. Lazy means to update when and only required, update it leaf nodes and return immediately. For details refer to SPOJ Discussion board… Also, Please indent your code for others to understand it easily…

28

Yes someone please explain