PRMQ Editorial(Unofficial) [Simplicity gauranteed]

editorial
, , , ,
21

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).:slight_smile:

22

@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

23

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

24

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

1 Like
25

@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

1 Like
26

@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 :slight_smile: Finally an AC.

27

Good that you got a AC ^^

28

@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 :slight_smile: