@haccks thank you
Amazing question! Reduction of a step from O(N) -> O(sqrt(N)) complexity was a bit tricky to realize though!
Here’s how i did it for step of finding all pairs(x,y) : x*y < Prod
( Additionally understand Sieve of Eratosthenes so as to how complexity reduction happened )
for a product P lets suppose P=10
we have following pairs valid:
1,1 1,2 1,3 … 1,9
2,1 2,2 2,3 2,4
3,1 3,2 3,3
4,1 4,2
5,1
6,1
7,1
8,1
9,1
now if we use all values in range [1,sqrt(N)]:
1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9
2,1 2,2 2,3 2,4
3,1 3,2 3,3
now we reverse each pair (x,y) in the above to generate all distinct pairs with some repetitions…
Now we remove repetitions:
1- First of all remove all occurrence of (i,i) once from the final count
2- Second for a particular row lets say row 3
3,1 3,2 3,3 3,4 3,5 … 3,n
we have 3,1 3,2 already repeating already in row 1 and row 2 and hence we need to remove this count as well.
For rest left over count multiply by 2 since we need ordered pairs.
Additionally i used hash map to store previously calculated values to avoid repetitive calculations
Here’s the code for the technique. O(Nsqrt(N)) for each query:
http://www.codechef.com/viewsolution/3791652
Thanks darkshadows for the question.
1 Like
edit the editorial
its confusing
sum [over B=1 to P] number of multiples of B less than N+1 != The sequence ⌊ P/i ⌋ has at most 2 * √P distinct values.
correction should be here at end of following line
sum [over B=1 to P] number of multiples of B less than P+1
I found out the solutions using brute force code. Then simulated for about 14 hours using file handling and stored and in an array…
And then ACd answer AC with O(1) time complexity and O(N) space…
@darkshadows Sir, in worst case scenario, time taken by each test file will be O(T * N * N) but not O(N * N). T * N * N = 312500000 (> 3 * 10^8). Even if we consider that 10^8 instructions execute in 1 sec (which may not be the case), the solution in the editorial will give tle. Do correct me if i am wrong. Also please update the editorial with another solution if I am correct. Thanks!
1 Like
sadly the constrains were so low that pre-computing values was possible… D:
1 Like
Does that suppose we must not use brute force ever ?!