CNPIIM - Editorial

@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 ?!

//