CLOSEST PRIME question in LOCMAY18

Hello Everyone, in the third question on LOCMAY 18 on codechef…please someone help me with using a segment tree or fenwick tree on updating discontinous values like subtracting nearest smallest prime number in a given range?

Okay so running a code you can easily see that each number lasts for <5 steps before it reduces to 1 or 2. So what you can do is, check the maximum value in the range of update and if it is >2 then you start visting each element, updating the element only if it is >2. The next challenging part is finding the nearest smaller prime efficiently. If the value a[i] is under 1e6 or somewhat in that range you can easily find it using binary search on the generated primes array(using Seive of Eranthoses). This can be used to solve Subtask 1. Now for Subtask 2 things get ugly as A[i]<=1e9+1e6. So surely we have to do better than that. Running another code you can easily see that maximum distance between 2 consecutive prime numbers in that range is <200. So distance between the number and its nearest prime is also <200. So we just need to precalculate the number formed after first change and for later changes we can just use the generated primes array. Also it is given max Ai-min Ai<=1e5+200. So if we just find the closest prime nearest to min Ai and then iterate over all numbers between max Ai and min Ai to check if it is a prime number or not we are done. To generate the nearest prime less than min Ai we can loop backwards from min Ai and locate the nearest prime number before it. It will take atmax 200 iterations. Also checking if a number is prime or not can be done using miller-rabin primality check.
here is the implementation of the above logic. Also you can try this as a warmup challenge.

2 Likes

Thank you @soham1234

So you use a segment tree? BTW for locating the primes in the range I guess we can use a sieve it should be faster.

Read my comment. I did mention sieve but for Ai<=1e9 we cant afford nlogn. Maybe something like Segmented Seive can be helpful but maximum difference being <200 we can afford that

Yes I mean a segmented sieve but only over 1 segment. We can create the segment over the range of numbers which is ~1e5. Then the time for computing all the primes in the range would be nloglogn which should be quite a bit faster than running Milller-Rabin on every number in the range I guess.

I havent used Miller Rabin on each number. Just to find the nearest prime to min Ai. Then ran a O(max Ai- min Ai) loop to check which numbers are prime. If pr is a prime number and pr2 is the next prime number all numbers between them has pr as nearest prime. I used this fact. And its better than segmented seive as in segmented seive again you had to incur a logn cost per number in array for finding nearest prime but my approach for only first reduction has complexity of O(max Ai- min Ai + 200) . Check my implementation for understanding better