ANUGCD - Editorial

general
, , ,
21

@Anudeep, Sir can you please tell where my code fails http://www.codechef.com/viewsolution/3622900

22

@anudeep2011
@xellos0
@rodrigozhou
I did this question using the segment tree and prime factorisation and I am interested in the other methods for doing this problem mentioned by you above. So, I request you to explain your solution solution a bit more so that i and others can have benefit of that because it is quite difficult to understand the code directly.

1 Like
23

I used Segment Tree and sparse tree in separate solution. My program was running in under 2s for the given constraints, but i kept getting TLE. Can you plz look at my solution, http://www.codechef.com/viewsolution/3557742 http://www.codechef.com/viewsolution/3557556

24

@rodrigozhou

I went through your code of ANUGCD solution using BIT. I didnā€™t quite understand your BIT query logic to find the max in a range. How can a BIT be used to perform range maximum query?

Can you please explain?

25

@anudeep2011 @rodrigozhou

Hi, I was going through the Binary Indexed Tree solution linked in the editorial. I could not quite understand how a BIT was used to perform range maximum query, specifically the following two blocks of update and query code:


void update(vector<int> &bit, int x, int val) {
    while (x < bit.size()) {
        bit[x] = max(bit[x], val);
        x += x & -x;
    }
}

int query(const vector<int> &v, const vector<int> &bit, int l, int r) {
    int ret = 0;
    l--;
    while (r > l) {
        int n = r - (r & -r);
        if (n >= l) {
            ret = max(ret, bit[r]);
            r = n;
        }
        else {
            ret = max(ret, v[r--]);
        }
    }
    return ret;
}

I havenā€™t come across and do not know of a method to get max/min value in a range using BIT. The above method looks buggy to me too. Can you guys please explain the above approach?

26

@sultanofswing

Just remember the usual query in BIT. It would be like this:

int query(const vector<int> &bit, int x) {
    int ret = 0;
    while (x > 0) {
        ret += bit[x];
        x -= x & -x;
    }
}

In the usual BIT query, bit[x] represents the accumulated sum in the range [x-(x&-x)+1, x]. Thatā€™s why you do ā€œx -= x & -xā€: youā€™re jumping to the next range not summed yet.

So, the idea to do a range query in a BIT is to check if the whole interval that bit[x] represents is contained in the range that I want.

In the header of the range query function, the parameters means: v is the array of values, bit is the BIT of v and the range query is for [l, r].

In line, ā€œint n = r - (r & -r)ā€ means that bit[r] has the accumulated sum of the range [n+1, r]. As I have already decreased the value of l, if n >= l, then [n+1, r] is fully contained in (l, r] and I can sum bit[r] to my answer. Otherwise, I cannot do this. So I just get the value set in the v[r] and advance r in just one index.

I used the sum function in the explanation instead of max, and I hope it is not a problem.

1 Like
27

@rodrigozhou

I understand and agree with your above explanation but I think it is valid only for range sum query and NOT min/max query.

Lets take an example (on an index 1 based BIT) for a range max query problem:
This is my input array of size 4:
index: 1 2 3 4
value: 5 3 1 4

This is the BIT constructed on the above input array which stores the max at each node according to your update function:
index: 1 2 3 4
value: 5 5 1 5

How do I get the range max in the interval, say (2, 4) in this case with the above query algorithm?

Expected answer: 4

28

So, youā€™re doing query(v,bit,l=2,r=4).

In the first iteration, n=4-(4&-4)=0. So, n<l. This means the interval [1,4] is not contained in [2,4]. Therefore, Iā€™ll do ret=max(ret,v[4])=4 and r=3.

In the second iteration, n=3-(3&-3)=2 and n>=l. This means the interval [3,3] is contained in [2,4] and I can take the accumulated value in bit[3]. So, ret=max(ret,bit[3])=4 and r=2.

In the third iteration, n=2-(2&-2)=0 and n<l. This case is analogue to the first iteration and Iā€™ll do ret=max(ret,v[2])=4 and r=1.

This finishes the while loop and the answer is ret=4.

1 Like
29

In fact, I think this works for any functionā€¦ I donā€™t see any restriction.

30

@rodrigozhou

I just noticed that you were doing ret = max(ret, v[rā€“]) and not ret = max(ret, bit[rā€“]).

Now that Iā€™ve understood it, I find your approach amazing! I was searching exactly for range min/max query using BIT for some time and I am glad that I came across your solution.

How did you come up with this approach? Have you considered writing an article on this? I doubt that many people know this.

31

@anudeep2011
Canā€™t We do solve this question using Moā€™s Algorithm. I have tried it but getting TLE.
Here is my code:https://www.codechef.com/viewsolution/8398234

32

Here is my solution if anyone wants to refer https://www.codechef.com/viewsolution/22490044 as I guess itā€™s pretty readable. Feel free to comment if anything isnā€™t clear. (PS: implemented after referring editorial :slight_smile: