MULTQ3 - Editorial

editorial
, , ,
7

Hey…I have solved this question using seg-trees but Im getting WRONG ANSWER. Here is my code.
https://www.codechef.com/viewsolution/15771326

Thanks in advance.

8

How can one identify that this should be solved through segment tree ?
are there any ways to identify such problems (related to segment etc) ?
also is there any other way to solve this ?

1 Like
9

@piyusjain1555 its a question of “lazy propagation” in “segment tree”… looks like you were a beginner for coding… so you can google and learn how to do this type of questions… u have have a look at FLIPCOIN which is similar to this question…

1 Like
10

The following is the idea.

Initially, all the numbers are divisible by 3. tree[node][0] = hi - lo + 1

Now, let’s say we are updating range [lo … hi] and hi - lo + 1 = 4.

Each update to range [lo … hi] of tree node moves the count in the following fashion.

Update number 1 -> all 0’s will be 1. 0000 -> 1111 and we save these numbers in tree[node][1]

Update 1: tree[node][1] = tree[node][0].

Update number 2 -> all 1’s will be 2. 1111 -> 2222. So we save these numbers in tree[node][2]

Update 2: tree[node][2] = tree[node][1].

Update number 3 -> all 2’s will be 3. 2222 -> 3333. They are now divisible by 3, so we save these numbers in tree[node][0]

Update 3: tree[node][0] = tree[node][2]

and so on.

1 Like
11

:slight_smile: You must use data structure in order to process any query in O(logn), not O(n), which let your solution TLE :slight_smile:

12

How is FLIPCOIN similar to this? I solved it without segment tree.

13

How ?
Link to solution ?

14

LOL python is making people fool
Python is optimizing it for you !!
it might be using some data structure internally.
#DontTrustPython
That’s why beginners shouldn’t use python.

1 Like
15

Here is the solution.
Can you please tell me where it uses segment tree?

1 Like
16

Thanks for the reply.
Now I think I should switch to C++.

1 Like
17

Use a loop to invert and let me know if you still get 100pts
Inbuilt function can use anything it wants to. We never know.
Specially in python.

18

I already did that and that gave me TLE.
I am using numpy(written in C and Python) library that’s why it gives AC.

1 Like
19
20
21

can someone tell me what is going wrong here. i used 3 segment trees instead of a node containing 3 values .
https://www.codechef.com/viewsolution/29924416

thanks in advanced.

22

Sol : CodeChef: Practical coding for everyone
Is this problem not for python programmers? I am getting TLE using Segment tree + Lazy Propagation

23

You forgot to use the modulo operator.
Correct code should have lazy[c]%3==1

24

can any help me where i am doing the wrong my solution passes for the all the basic test cases i am not able to find any test cases where my solution fails
my solution link - CodeChef: Practical coding for everyone

it is saying run time error
if any one is able to provide a test case which is making run time error it will be great help…

25

why is this giving tle please help!

26

What do u do with the add[k]?