The problem is from geeksforgeeks codeindiacode finals. I tried some things like changing the function to x.y| Ay/y - Ax/x| so if we sort them according to Ai/i then check for near pairs but that doesn’t work, tried sorting them according to Ai but that too doesn’t work. Can someone help me out.
this is the link for problem if anyone wants to give it a try.
Analyze the number of different values possible for \displaystyle \frac{A_i}{i}.
There’s a constraint on array values that, A_i \le 10^6 hence for all indices i \ge 10^3, \displaystyle \frac{A_i}{i}\le \frac{10^6}{10^3}=10^3 .
Hence for all indices 10^3 \le i \le N there are at most 10^3 different values of \displaystyle \frac{A_i}{i}. And for indices 1\le i \le 10^3 there are at most 10^3 different values of \displaystyle \frac{A_i}{i}. So in total over all indices 1 \le i \le N we can have at most 2 \times 10^3 different values of \displaystyle \frac{A_i}{i}. Now if the value of N > 2 \times 10^3 from pigeon hole principle we’ll have at least one pair of indices i,j such that \displaystyle \frac{A_i}{i}=\frac{A_j}{j}. Cost for this pair will be \displaystyle \left |ij \times \left (\frac{A_i}{i}-\frac{A_j}{j}\right) \right|=0 which is the minimum possible cost.
Hence if N>2000 then the answer is 0 otherwise just brute force the answer in \mathcal{O}(N^2) time.
The way you deduce the division part of finding the different combinations. Can you tell us what part of mathematics that is? I am not sure if i understood well
Will be great if someone can explain in more simple terms or resources. I think I am missing the basics
that is the pigeonhole principle and it is part of discrete mathematics. I will try to make it further easy, its simple if you have n+1 distinct objects and n distinct holes then of course there will be a hole that has 2 distinct objects. the same principle we can compute by brute force:
limit = 1e6;
n = 1e5;
unordered_set< int > st;
for( int i = 1; i <= n; i++ ) st.insert(limit/i)
cout<<st.size()
answer : close to 2000
when you print the size of the set here it will be close to 2000 so we can say we say 2000 distinct objects. But since i that is index range is (1 - 100000) so we are sure that there will be duplicates value of (limit/i) and if there is duplicate then our result is zero. Else we make N*N BRUTE FORCE search which is feasible because N will be less than 2000.
Thank you so much. I knew about pigeon hole principle but what I was missing is the reason to apply pigeon hole which you had clearly explained with the help of set.
Now it makes sense and avoid TLE error a lot when you are able to understand the constraints.
Thanks a lot
