Sukarna_Paul's blog

By Sukarna_Paul, history, 11 months ago, In English,

I have been trying to solve this problem for last few days . Here is the Problem link SPOJ PTRI .

I have used Linear sieve , but the limit is so high that it is getting TLE in O(N) . I have tried it with sieve of aktin also. But still got TLE . Please help me to solve this one.

I found this problem in -Morass- blog Link . You can visit it , I am confident that you will find it useful.

  • Vote: I like it
  • +11
  • Vote: I do not like it

11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can implement a segmented sieve of Eratosthenes.

11 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

For this problem you can do a lot of optimisation.

  • You can solve the problem offline. You can read all queries, then sort them (by means of radix sort algorithm for example)
  • Inside the sieve after getting sequent prime number you can compare it with current query number. If it is less then the current query number, you go to the next prime number. If it is equal to the current query number, you saved the position for this query and increment the current query index in the sorted list. If it is greater then the current query number, then you simply increment the current query index. So no need in binary search.
  • Because we get the primes sequently we can know the row and column numbers offhand, just keeping two variables r and c. When we get next prime number we increment ++c. If c becomes greater than r we do ++r, c = 1. So no need in sqrt().
  • As for sieve itself. To reduce memory usage you can use bitwise operations (for example) with one bit on any number from interval [1... 108] or 12M in total (and no need in supporting the prime list). Also you can try linear sieve or segmented sieve (the codes can be found in this blog entry).

UPD: One more fast sieve you can find here. I did not test all mentioned sieves on this problem, sorry.

  • »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Alas, it turns out that a solution with $$$sqrt()$$$ and binary search is slightly faster than a solution with above optimizations. The problem can be solved by means of correctly written wheel sieve. Here is the code for the sieve with the base $$$ ( 2, 3, 5, 7 ) $$$ which is fast enough to evade TLE:

    Wheel sieve