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

×

PRMQ Editorial(Unofficial) [Simplicity gauranteed]

9
5

PROBLEM LINK:

Practice Contest

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Segment Trees, Binary Search

PROBLEM:

Given an array a of N integers and Q queries where each query provides you with four integers L, R, X and Y. For each query, output the value of F(L, R, X, Y) as count the number of primes that lie in the range x to y and that divides the number between the range l to r of A[i].

F(L, R, X, Y)

 result := 0
 for( i = X to i = Y )  {
     if( isPrime(i) ) {
         for( j = L to j = R ) {
              number := a[j]
              exponent := 0
              while( number % i == 0 ) {
                 exponent := exponent + 1 
                 number := number/i
              }
              result := result + exponent
          }
     }
 }
 return result

QUICKK EXPLANATION:

If you are new to Segment Trees then THIS will definitely help you get over segment tree.This is by far the best blog i have came across while reading segment trees. But if you still face hard time understanding this then you can refer to This and This videos. This problem basically boils down to count the number of primes that lie in the range x to y and that divides the number between the range l to r of A[i]. So for that we can keep track of the prime factors of every A[i].

EXPLANATION:

As 2<=A[i]<=10^6 so maximum number of prime factors can be 2x3x5x7x11x13x17x19 which exceeds 10^6. So what i did here is calculated the prime factors of all the input numbers and pushed them into an array of vectors named v. Each vector in this array stores the prime factors of the corresponding to A[i]. Now i created a segment tree using this array of vectors. While merging 2 nodes all the prime factors are inserted in sorted order of a leaf node in the segment tree so that  we can do binary search on the prime factors to count them between the numbers x and y. This is my first blog, kindly point out the mistakes if any. Coming to the code here i have taken my node as the array of vectors.

Node of segment Tree

Here each leaf node contains a vector which has all the prime factors of a particular A[i] in sorted order.

Merging of segment nodes

while merging we are just taking the union of 2 sorted vectors.

Querying the segment tree

In each query first i am finding the segment i.e. l to r which is required by that particular query. Now after i have found such a segment i.e. now i have vector that contains the prime factors of all the numbers in the range l to r of A[i]. Now i just need to find x and y in this vector as the difference of their index will give me the count of prime divisors for that query.

ALTERNATIVE SOLUTION:

Please share any other approach which is better then mine or suggest any improvements in my current approach.

EDITORIALIST'S SOLUTIONS:

Can be found here.

This question is marked "community wiki".

asked 16 Jun '17, 21:55

d4dev's gravatar image

3★d4dev
114
accept rate: 0%

edited 17 Jun '17, 11:01

The explanation is shorter than Problem...

No, i dont mean that explanation should be long. You put across the point well enough. Why not discuss some implementation details, like how you made segment tree, the functions, and etc.

(16 Jun '17, 23:35) vijju123 ♦♦5★

Thanks for the suggestion, I have now added a perfect link to explanation of segment tree, moreover now i have also explained the node structure, merging and querying of the segment tree for this particular problem, hope this helps.

(17 Jun '17, 10:49) d4dev3★

Thanks for the editorial, I was trying to keep the frequency too, but yours approach is simpler(just keeping whatever the prime factor be as many times).:)

(21 Jul '17, 19:30) vishesh_3451★

Very nice work, simplicity at its best. Thanks for this editorial . Hope you will put up more like this :)

link

answered 17 Jun '17, 19:11

deepak_d14's gravatar image

4★deepak_d14
313
accept rate: 0%

edited 17 Jun '17, 23:27

How about this solution

I think everyone is familiar with the brute force solution :

We create a 2D array count of size 100000*78498 and for each arr[i] for (1 <= i <= n) we store the number of times the jth prime number divides it. Then for each j we can calculate contiguous sum for 1 to n and store it in a new array conti_count as shown below.

for(int i = 1; i <= n; i++) { for(int j = 0; j < p.size(); j++) conti_count[i][j] = conti_count[i-1][j] + count[i][j]; }

But now the problem is size of 2D array and complexity of the above code spinet. Can we do something better ?

Alright answer this : How many prime divisor of a number n exists at max which are greater than sqrt(n).

The answer is : 1, because if you divide n with m ( where m >= sqrt(n) ) the result is less than sqrt(n).

Using the above fact we can reduce the code complexity from O(100000*78498) to O(100000*168)` for the pre calculation part. So now what different are we doing from our initial brute force solution ?

We are calculating the above mentioned count only for the prime numbers less than 1000. Now for each query we can iterate from index[max(1,x)] to index[min(1000,y)] and count number of appearance of all prime numbers between 1 to 1000 in range l to r, where index stores the rank of prime number (max value is 168).

What is left is to handle case of calculating number of integers in range l to r with a prime factor greater than max(1000,x) to y. So while doing prime factorisation of each number during precomputation we make an array and for each i in range 1 to n and we store the prime factor of arr[i] which is greater than 1000. Now we can either use trie or merge sort tree to compute number of integers less than equal to y in range l to r and number of integers less than x in range l to r in log(n) each.

You can view my solution for better understanding : PRMQ

link

answered 26 Jun '17, 18:35

priyanshukm's gravatar image

5★priyanshukm
871416
accept rate: 30%

I applied the same approach, but instead of using vector i used map to keep record of prime divisors and their corresponding powers. First i used segment tree but only scored 10 marks. you can check my solution here. but after it i used fenwick tree for optimization but still scored only 30 marks. could anyone suggest me what's wrong in my solutions. here is my solution.

link

answered 17 Jun '17, 00:45

tonny's gravatar image

3★tonny
112
accept rate: 0%

Hi, I viewed your solution but our approaches are different. See instead of calculating all the prime numbers less then 10^6 we can just calculate the prime factors of each corresponding A[i]. Moreover you have used unordered_map which has o(logn) insertion and o(logn) searching in the worst case. Moreover try to use scanf and printf by including <cstdio> header instead of ios_base::sync_with_stdio(false);. And please go through my solution one more time you will surely understand the difference in our approaches, still if you face difficulty let me know.

(17 Jun '17, 10:34) d4dev3★

OK, i will check your solution once again. and thanks for your response.

(17 Jun '17, 18:33) tonny3★
1

After using the ios_base::sync_with_stdio(false); statement, cin and cout works more faster than scanf and printf. so it's not the issue.and by calculating prime factors <10^6 won't affect it much. I applied the same approach of prime factorization as you used. and also i think merging of two unordered_map is faster than merging of two vector, since you are using a comparison function. and yes you are right. your approach is different than mine. As i see you didn't use loop in query function. which gives the advantage to you.

Please tell me if you find anything incorrect in first paragraph.

(17 Jun '17, 19:07) tonny3★
2

@d4dev, your information is not accurate. unordered_map has constant time access and insertion in the average case. Moreover, ios_base::sync_with_stdio(false) significantly improves the performance of cin and cout, which makes it comparable to or even faster than scanf and printf. Check here for details.

(17 Jun '17, 22:52) meooow ♦6★

Hey @meooow , can you please help me at a Q here- https://discuss.codechef.com/questions/101843/regarding-c-stl-set

Its regarding C++ STL.

(17 Jun '17, 23:00) vijju123 ♦♦5★

@meooow yes you are right sorry about that.

(18 Jun '17, 09:43) d4dev3★
2

Indeed, ios_base::sync_with_stdio(false) is fast but if you use endl per query it will go back to being slow because of flushing. Remember to always use \n for multiple queries.

Though that's the case, your solution will still TLE because of other issues, try following what others said :)

(18 Jun '17, 13:24) hikarico5★

@vijju123 sure, I'll take a look!

(18 Jun '17, 15:47) meooow ♦6★

@tonny in your approach you can optimize your prime factorization method. You are using an approach O(sqrt(N)/2). You can have a look at my solution.

https://www.codechef.com/viewsolution/14642454 Also it is good to keep the frequency of every prime factor but it is not needed actually. You see total no. of prime factors all numbers in array is with O(N) space complexity because total no. of prime factors cannot exceed 19 (even if all are same that is). So even if you keep primes as it is there is no problem. Hope it helps :)

(23 Jul '17, 14:20) vishesh_3451★
showing 5 of 9 show all

Very good and simple to understand approach! Great Job!

link

answered 18 Jun '17, 01:38

goku321's gravatar image

2★goku321
1
accept rate: 0%

I used persistent segment tree. https://www.codechef.com/viewsolution/14223288

link

answered 18 Jun '17, 13:36

rishus23's gravatar image

3★rishus23
11
accept rate: 0%

Hi @d4dev . Thanks Because of you i learnt segment trees for the first time. Can you once explain me the query part if you don't mind. Thanks.

link

answered 18 Jun '17, 18:20

saisurya027's gravatar image

4★saisurya027
1666
accept rate: 0%

1

Here segment tree contains a sorted vectors of prime numbers of the elements which falls in the range of L to R. Let me make it clear by an example Problem: suppose my array is like 2 3 4 5 4 Here l=1 and r=3 Here x=2 and y=4 Solution: Now this segment l=1 and r=3 will give a vector like 2 2 2 3 here 1st 2 is for A1 here 2nd and 3rd 2 are because of A[3] here 3 is because of A[2] now we will do binary search on this received vector and find the difference in the index corresponding to x and y which will give 4 for this case. Hope this clears some of your doubts :)

(19 Jun '17, 11:51) d4dev3★

Hi @d4dev, your solution is very well explained without increasing the complexity of any operation. I applied the same approach but was able to score points only for Subtask 1 & 2 only and I was getting WA for all the testcases in the last subtask. Could you have a look at my code and telling me what am I doing wrong. Here is My Code.

Thanks

link

answered 20 Jun '17, 17:15

rohitakaaddy's gravatar image

2★rohitakaaddy
1
accept rate: 0%

can anyone tell if why my solution is not working....here

In a node,i have stored vector of pair where first is prime factor and second is the power.

struct node{
    vector<pair<int,int> >pr;
    int size;
};

i have submitted it around 35 times but no luck.Please help me.

link

answered 24 Jun '17, 00:06

vkstack's gravatar image

2★vkstack
11
accept rate: 0%

@d4dev I tried to do this question as told by you. But I am stuck on this for long. I am getting only 20 points. Tried all things but not getting an AC. Can someone please help me with this. @d4dev my solution is similar to yours ,it won't take much time.

Please Help. Thanks. Link to my solution https://www.codechef.com/viewsolution/14641252

link

answered 23 Jul '17, 00:04

vishesh_345's gravatar image

1★vishesh_345
2567
accept rate: 8%

edited 23 Jul '17, 00:04

@vijju123, @d4dev please have a look at it. It won't take much time.

(23 Jul '17, 00:47) vishesh_3451★
1

Are you sure that the elements in the merged nodes are sorted?

(23 Jul '17, 00:57) vijju123 ♦♦5★
1

@vishesh_345 I have a test case for you but its gonna be very hard for you to debug it.
5
2 45 14 546 475
1
2 5 10 1000
My ac code is giving ans as 2 your code is giving ans as 0.
Actually the problem is that you are applying binary search on an unsorted vector.
Look here: http://ideone.com/XOqxDU

(23 Jul '17, 08:54) siddharthp5384★

@vijju123,@siddhartp538 Thank you so much for pointing this out. I was struggling with it a lot. Actually, the mistake was :

I was trying to maintain an array sieve[] which keeps the smallest prime factor. In this way any number, prime factors can be found in O(logN) (after sieve). But while applying the sieve, By mistake i was keeping the highest prime factor (overwriting everytime as soon as it get a prime factor).

In simple words say 40. Now this no. has smallest prime factor 2 which i intended to store in sieve[40]. But when loop reaches to 5 sieve[40] was changed to 5. The only change i need to do was if(sieve[j]==0) sieve[j]=i; where i is the first and j is the second loop in sieve function. So now only those which are 0 are changed. And there will be no overwriting of prime factors.

And if smallest prime factor is stored you automatically get sorted prime factors of any no. in logN.

Thank you again :) Finally an AC.

link

answered 23 Jul '17, 09:59

vishesh_345's gravatar image

1★vishesh_345
2567
accept rate: 8%

edited 23 Jul '17, 10:01

Good that you got a AC ^^

(23 Jul '17, 11:45) vijju123 ♦♦5★
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:

×15,683
×2,596
×1,755
×1,038
×149

question asked: 16 Jun '17, 21:55

question was seen: 1,996 times

last updated: 23 Jul '17, 14:20