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

×

ANUGCD - Editorial

9
4

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Medium

PREREQUISITES:

Segment Tree, Factorize

PROBLEM:

Given N numbers in a sequence, answer M queries about what is the maximum number between L and R and the greatest common divisor between it and G is greater than 1.

EXPLANATION:

Every number X can be written in the factorized form: X = p1^k1 * p2^k2 * ... * pi^ki * ... * pn^kn. We can call all pi as X's factors (of course, pis are all different primes). For example, 18 = 2 * 3^2. So we can say that 18, has factors 2 and 3. Because pi >= 2, the number of factors, i.e. n, is in O(logX). Therefore, the total number of factors of the given N numbers are O(NlogN) (the range of N and numbers are same).

The greatest common divisor of two numbers is greater than 1, means that they have at least one common factor. If we enumerate the common factor C they have, the satisfied numbers are determined -- all numbers have factor C. After that, the only thing we need is to find the maximum in the query interval [L, R]. For this type of queries, an ordinary solution is to use Segment Tree.

With these two ideas in mind, let's start to assemble the whole algorithm, now.

  1. Factorize N numbers, and restore some vectors of position[pi], which records the positions of the numbers who has the factor pi. From the analysis above, we know that the sum of position[pi].size() is O(NlogN)
  2. Build several segment trees, the i-th one corresponds to the position[pi], maintaining the interval maximum in the tree node. Of course, you can also concate all position and make a whole segment tree.
  3. For a query number X and the interval [L,R], first factorize X. And for each factor, look up in the corresponding segment tree (or corresponding intervals, if you choose to build a whole segment tree) to get the maximum. Finally, take the maximum of the query results among different factors.

As analyzed before ,X has at most O(logX) factors. And each interval-maximum query takes only O(logN) time. Therefore, to answer a query, our algorithm only needs O(log^2 N) time.

In summary, the time complexity is O(NlogN + Qlog^2N), while O(NlogN) space needed.

As requested by many users here are solutions without segment trees.
Sqrt-Decomposition.
Binary Indexed Tree.
STL-MAP

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 18 Mar '14, 20:44

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446172
accept rate: 0%

edited 19 Mar '14, 13:56

anudeep2011's gravatar image

6★anudeep2011
2.2k72633


Is there an alternate solution that does not involve the usage of segment tree ?

link

answered 18 Mar '14, 20:49

xorfire_'s gravatar image

3★xorfire_
1614
accept rate: 0%

edited 18 Mar '14, 21:26

One possible way is sqrt decomposition, but I think it may get TLE. Let me further think about it.

(18 Mar '14, 20:59) shangjingbo ♦♦3★

I tried sqrt decomposition [ http://www.codechef.com/viewplaintext/3616120 ], it got TLE.

(18 Mar '14, 21:12) xorfire_3★
1

Yes. Here is my SQRT-Decomposition solution http://www.codechef.com/viewsolution/3620495

And here is a solution using BIT http://www.codechef.com/viewsolution/3533495

(19 Mar '14, 13:58) anudeep20116★
5

@anudeep2011 Thanks. Missing this problem will haunt me and my future generations for eternity.

(19 Mar '14, 15:18) xorfire_3★

Does precomputation of the first 100001 numbers' factors give tle? While implementing sieve I stored the factors of all the 10^5 elements in a vector.Rest procedure is same as given above.still got tle.http://www.codechef.com/viewsolution/3536122

link

answered 18 Mar '14, 22:08

ranjanvittal's gravatar image

5★ranjanvittal
161
accept rate: 0%

edited 18 Mar '14, 22:17

I have precomputed the factors and it can be done in linear time. Although my solution involves offline computation of answers. You can have a look at my approach here

(18 Mar '14, 22:51) atulsehgal3★
1

I actually had to do precomputation in order to get AC. Without it was just getting TLE.

(19 Mar '14, 00:38) junior944★

@anudeep2011:Can we solve this using Binary Indexed Trees?

link

answered 18 Mar '14, 22:17

knb_dtu's gravatar image

4★knb_dtu
410620
accept rate: 22%

edited 18 Mar '14, 22:18

2

@xorfire_

I did with BIT. I change the query function to query in a range, but it runs in O(log^2 n).

Here is my solution: http://www.codechef.com/viewsolution/3533495

(19 Mar '14, 02:42) rodrigozhou5★

@rodrigozhou Thanks.

(19 Mar '14, 06:42) xorfire_3★

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

(10 Jul '14, 00:32) sultanofswing6★

@anudeep2011: Thank You for such a nice problem :)

About the pre computation part, it is just like sieve, and can be easily done in linear time. It will actually save a lot of time while processing queries. Factoring is not a problem for this question, any method will work :) As anudeep said, time limit was not strict if algo is right.

My approach was - making 9592 (no of Primes less than 100000) segment trees, each for a single prime. I then inserted the all multiples of the prime in its respective seg tree along with it's index. When a query arrives, find its respective indices in all the seg trees which divides G (at max 6 factors so only 6 query in 6 diff trees). Find sol of respective tree and then combine.

I wonder if its possible to do this sum using sqrt decomposition. I have not implemented this but I think it's possible.

link

answered 18 Mar '14, 23:25

ashish1294's gravatar image

2★ashish1294
18615
accept rate: 7%

edited 18 Mar '14, 23:27

1

Yes. Here is my SQRT-Decomposition solution http://www.codechef.com/viewsolution/3620495

And here is a solution using BIT http://www.codechef.com/viewsolution/3533495

(19 Mar '14, 13:58) anudeep20116★

Much Simpler Solution :)

(19 Mar '14, 17:30) ashish12942★

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

link

answered 20 Mar '14, 22:58

ma5termind's gravatar image

4★ma5termind
1.6k1329
accept rate: 11%

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

link

answered 10 Jul '14, 05:43

rodrigozhou's gravatar image

5★rodrigozhou
162
accept rate: 0%

@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

(10 Jul '14, 11:11) sultanofswing6★
1

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.

(10 Jul '14, 20:50) rodrigozhou5★

In fact, I think this works for any function... I don't see any restriction.

(10 Jul '14, 20:52) rodrigozhou5★

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

(10 Jul '14, 21:49) sultanofswing6★

edited but still getting wa someone plss help heres the modified link: http://ideone.com/5EWVUQ

link

answered 19 Mar '14, 13:15

pawan55's gravatar image

4★pawan55
02
accept rate: 0%

@anudeep2011 :sir plss tell me why im getting wa although the code seems to be working right on all the test cases i can think of http://ideone.com/5EWVUQ

link

answered 19 Mar '14, 14:05

pawan55's gravatar image

4★pawan55
02
accept rate: 0%

1

It is failing on a very large test case (n = 10^5) For the query "63001 54725 59725" while the answer is "63001 11" your code last submission on codechef is giving "63001 22" as answer.

(19 Mar '14, 14:15) anudeep20116★

got AC thnx

(19 Mar '14, 17:09) pawan554★

anudeep sir can you please explain how you handled the prime>350 part in your segment tree(authors) solution

link

answered 20 Mar '14, 12:47

architmittal's gravatar image

2★architmittal
1124
accept rate: 0%

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

link

answered 20 Mar '14, 14:01

codemex's gravatar image

2★codemex
112
accept rate: 0%

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

link

answered 27 Mar '14, 17:13

akshayvats's gravatar image

5★akshayvats
11
accept rate: 0%

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

link

answered 10 Jul '14, 00:54

sultanofswing's gravatar image

6★sultanofswing
30114
accept rate: 0%

edited 10 Jul '14, 01:24

@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

link

answered 06 Oct '15, 14:04

shishirt22's gravatar image

4★shishirt22
11
accept rate: 0%

edited 08 Oct '15, 00:43

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:

×1,812
×1,188
×31
×20

question asked: 18 Mar '14, 20:44

question was seen: 9,629 times

last updated: 08 Oct '15, 00:43