MULTQ3 - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

The problem can be solved using segment trees. Every node of the tree stores the following data :

  1. tree0[k] : In the range [low…high] covered by this node, how many numbers are divisible by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
  2. tree1[k] : In the range [low…high] covered by this node, how many numbers leave a remainder of 1 when divided by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
  3. add[k] : What is the quantity which is added to all numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
6 Likes
2

Can we solve it using BIT? If yes then How??

6 Likes
3

#include

using namespace std;

int main()
{
int n,q;
scanf("%d %d", &n, &q);

    int a[3],coin[100001]={0},head;

   while(q--)
    {
        for(int j=0;j<3;j++)
            scanf("%d", &a[j]);
            head=0;

        if(a[0] == 0)
        {
               for(int i=a[1];i<=a[2];i++)
                    coin[i]++;
        }
        else
        {
             for(int i=a[1];i<=a[2];i++)
                if(coin[i]%3 == 0)
                    head++;

             printf("%d\n" , head);
        }
    }

}

WHY is this giving TLE error???

4

#include

using namespace std;

int main()
{
int n,q;
scanf("%d %d", &n, &q);

    int a[3],coin[100001]={0},head;

   while(q--)
    {
        for(int j=0;j<3;j++)
            scanf("%d", &a[j]);
            head=0;

        if(a[0] == 0)
        {
               for(int i=a[1];i<=a[2];i++)
                    coin[i]++;
        }
        else
        {
             for(int i=a[1];i<=a[2];i++)
                if(coin[i]%3 == 0)
                    head++;

             printf("%d\n" , head);
        }
    }

}

WHY is this giving TLE error???

5

plz elaborate your explaination…its too difficult too understand from such 3 confusing statements u have mentioned just for the sake of editorial… - _ -

1 Like
6

Can anyone help me, pls ?? I use Segment Tree but I got Wrong Answer and I don’t know why. This is my submission, help me, please. CodeChef: Practical coding for everyone

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