You are not logged in. Please login at www.codechef.com to post your questions!

×

ADDMUL - Editorial

19
3

PROBLEM LINK:

Practice
Contest

Author: Devendra Agarwal
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

DIFFICULTY:

Medium

PREREQUISITES:

segment tree, lazy propagation, basic maths

PROBLEM:

Given array $A$ of $N$ size and $M$ operations of type:

  1. Add $v$ to all elements in a range.
  2. Multiply $v$ to all elements in a range.
  3. Reset all items to $v$ in a range.
  4. Report sum in a range.

QUICK EXPLANATION:

================
Build a segment tree, where at each node we store $\textrm{sum}$ and variables $\textrm{mul}$ and $\textrm{add}$, which denotes that the lazy update $A_i \leftarrow \textrm{mul}*A_i + \textrm{add}$ needs to be applied. If required, we update the current node's sum and variables and propagate the laziness down the tree. Also, an multiplication update $v$ at a node can be summarised as $\textrm{mul} \leftarrow \textrm{mul}*v$ and $\textrm{add} \leftarrow \textrm{add}*v$ and also addition update $v$ at a node can be written as $\textrm{add} \leftarrow \textrm{add} + v$. Set operation with value $v$ can be written as $\textrm{mul} \leftarrow 0$ and $\textrm{add} \leftarrow v$.

EXPLANATION:

================

BASIC SEGMENT TREE STUFF

I assume you know how segment trees and lazy propagation work and the basic concepts behind them like time complexity, nodes, intervals. First, I'll introduce some terminology I'm going to use.

  • Node: It's one of the nodes in the segment tree, it represents a contiguous interval of the array $A$.
  • Interval of a node is the actual range covered by the node.
  • Answer of a node is defined the actual value needed for interval queries. Here, for example, we need sum of values in the range.

Let's think step by step here.

  • For range query problems, try to see if segment tree can be used.
  • When does segment tree work? When you can merge two contiguous intervals(i.e nodes) to get answer of merged interval(node) in sublinear time. If complexity of merging is $O(K)$, then complexity for each operation can be worst case $O(\textrm{log N}*K)$. For example, when we talk about range minimum function, we can get minimum value of merged interval by taking minimum of answers of two individual intervals.
  • Also, for range updates you need to use lazy propagation. What does lazy propagation require to work? It requires that for an interval if we have multiple update operations, we can calculate the answer for that interval without actually updating every element in that interval. For example, if we are trying to find range minimum and range updation query is increase all elements by value $v$, then our new minimum is sum of existing minimum with $v$. Here also, we should be able to do this operation in sublinear time because it contributes to the factor of updations and queries.

Let's see how we use above two points to find here a solution using segment trees. Let's see the query part first: query is range sum, so merging two intervals is easy, just take the individual sums.

THE LAZY PROPAGATION SOLUTION

Now, let's see how we can handle all updations in such a way that we can find answer for an interval without actually updating the whole interval. We are going to store some data about the updations being done at that interval node and process it to find the answer. What could be this data? How do we find out? We need to observe what kind of operations we are doing. After some certain updations, our $A_i$ could be transformed to something like $((A_i*v_1 + v_2)*v_3 + v_4 + v_5)*v_6 + v_7$, where $v_1$ to $v_7$ are values of range multiplication or range addition. Now, we can store all these values $v_1$ to $v_7$ at our node, but we might have to do $O(\textrm{number of queries})$ operations at each node, which is not really sublinear. We need to find a compact notation at each node interval.

Now, thing worth noting here is that $A_i$ has been transformed to a linear function of $A_i$ i.e. something of form $(\textrm{mul}*A_i + \textrm{add})$. Now, let's say I make one more multiplication range update $v$, what's the new value of $A_i$. It's $(\textrm{mul}*v*A_i + \textrm{add}*v)$. So, we update $\textrm{mul}$ $*=$ $v$ and $\textrm{add}$ $*=$ $v$ at our node. Similarly, if we make a sum update with value $v$, the new value of $A_i$ is $(\textrm{mul}*A_i + \textrm{add} + v)$, so we update $\textrm{add}$ $+=$ $v$. For setting all elements to $v$, we can just make one multiplication with $0$ and then addition with value $v$.

So, if this interval is in range $L$ to $R$, for interval sum, we need $\sum_{i=L}^{R}(\textrm{mul}*A_i + \textrm{add}$) which we can write as $(R-L+1)*\textrm{add} + \textrm{mul}*\sum_{i=L}^{R}A_i$. So, we have to store sum of original $A_i$ and $R$ and $L$(basically size) and two variables $\textrm{mul}$ and $\textrm{add}$ at each node. Now, to make things easier we can just directly store the $\textrm{sum}$ of a node(i.e.* sum of all elements in that interval) instead of storing sum of original $A_i$. Then, for each range multiplication update or range addition update, we also update this $\textrm{sum}$ along with the variables $\textrm{mul}$ and $\textrm{add}$.

Also, as we do we in lazy propagation, we propagate the laziness to the children of a node, if we need to query a children of a lazy node. In this problem, we can individually propagate variables $\textrm{mul}$ and $\textrm{add}$. So, if at a node $\textrm{mul} \ne 1$, then we can say that this node is multiplication lazy and if required, we'll propagate this variable down to the children of this node. Similarly, if at a node $\textrm{add} \ne 0$, we can say that this node is addition lazy and propagate this laziness down to its children.

COMPLEXITY:

For building the segment tree we need $O(N \textrm{log} N)$ and each query is $O(\textrm{log} N)$, so total complexity is $O(N \textrm{log} N + Q \textrm{log} N)$.

PROBLEMS TO SOLVE:

QSET
SPOJ HORRIBLE
FNCS
MSTICK
ANUSAR
FRBSUM
Sherlock and Unique Substrings

AUTHOR'S, TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 26 Jun '15, 07:54

darkshadows's gravatar image

5★darkshadows ♦
3.0k93161187
accept rate: 12%

edited 13 Jul '15, 15:51


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

link

answered 13 Jul '15, 15:48

ketanhwr's gravatar image

6★ketanhwr
1.9k31744
accept rate: 15%

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

link

answered 13 Jul '15, 17:16

sagarpatel's gravatar image

4★sagarpatel
822
accept rate: 0%

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?

link

answered 13 Jul '15, 15:45

xrisk's gravatar image

3★xrisk
1943
accept rate: 0%

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

link

answered 13 Jul '15, 16:38

aviaryan's gravatar image

4★aviaryan
6016
accept rate: 25%

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

link

answered 14 Sep '15, 19:28

nik_sru's gravatar image

1★nik_sru
512
accept rate: 0%

Is it possible to solve this problem using BIT and are there any other approaches for solving first 3 sub-tasks other than segment tree ?

link

answered 13 Jul '15, 15:21

siddhartha4444's gravatar image

4★siddhartha4444
1547
accept rate: 0%

3

Before switching to segtree i did square root decomposition http://www.codechef.com/viewsolution/7349823 . It worked for 1st 2nd and 4th subtask but not for 3rd subtask .

(13 Jul '15, 15:52) rajat16037★

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

(13 Jul '15, 16:04) ayushj103★

Code Code you tell me test case where my solution failed used the same concept but could not figure out where i have made a mistake

link

answered 13 Jul '15, 15:22

Mocshare's gravatar image

3★Mocshare
3115
accept rate: 0%

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

link
This answer is marked "community wiki".

answered 13 Jul '15, 16:13

juststartedcd's gravatar image

1★juststartedcd
1
accept rate: 0%

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 http://www.spoj.com/forum/viewtopic.php?f=27&t=8296.... Also, Please indent your code for others to understand it easily....

(14 Jul '15, 21:04) likecs6★

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

link

answered 13 Jul '15, 16:43

rishabh__joshi's gravatar image

3★rishabh__joshi
1
accept rate: 0%

the time limit has been set dumbly , I implemented everything as in editorial but then also got tle , http://www.codechef.com/viewsolution/7475043

link

answered 13 Jul '15, 17:17

terminated's gravatar image

3★terminated
434
accept rate: 0%

@terminated I think time limit was well set :)

link

answered 13 Jul '15, 20:40

root8950's gravatar image

5★root8950
634
accept rate: 0%

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

link

answered 13 Jul '15, 20:48

psbbboyz's gravatar image

3★psbbboyz
1
accept rate: 0%

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=addmulnode+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! :)

link

answered 13 Jul '15, 22:32

archazey's gravatar image

6★archazey
472
accept rate: 0%

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.

link

answered 14 Jul '15, 00:39

punjabidon's gravatar image

5★punjabidon
111
accept rate: 0%

Thanks a lot for the similar problems list ^_^

link

answered 14 Jul '15, 14:25

aragar's gravatar image

4★aragar
994
accept rate: 7%

What is the problem with this solution?

include <iostream>

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;

}

link

answered 16 Jul '15, 18:00

shivam312's gravatar image

3★shivam312
812
accept rate: 0%

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

link

answered 16 Jul '15, 18:37

glow's gravatar image

3★glow
6312
accept rate: 0%

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.

link

answered 17 Jul '15, 11:44

sohamd95's gravatar image

4★sohamd95
584
accept rate: 14%

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

I am also getting WA on similar spoj problem http://www.spoj.com/problems/HORRIBLE/ My spoj solution id http://www.spoj.com/submit/HORRIBLE/id=14688264 I am not able to figure out why i am getting WA in both problems. Please help me out?

link

answered 17 Jul '15, 14:41

ashlesh123's gravatar image

3★ashlesh123
11
accept rate: 0%

edited 18 Jul '15, 10:52

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

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

link

answered 17 Jul '15, 15:04

achilles96's gravatar image

4★achilles96
1
accept rate: 0%

http://ideone.com/JBAB5E

Can you please check my code? What's wrong with it?

link

answered 02 Oct '15, 11:06

senbihan's gravatar image

4★senbihan
162
accept rate: 16%

Very nice question to implement lazy propagation :)

link

answered 23 Oct '15, 13:08

mayank_r_b's gravatar image

4★mayank_r_b
723
accept rate: 9%

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

here is the solution : solution

link

answered 17 Jun '17, 19:40

scorpion_ajay's gravatar image

4★scorpion_ajay
232
accept rate: 0%

edited 17 Jun '17, 19:42

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,072
×2,315
×1,496
×140
×126

question asked: 26 Jun '15, 07:54

question was seen: 12,424 times

last updated: 17 Jun '17, 19:42