# Yet Another minimization problem, codeindiacode gfg finals

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.

2 Likes

Thank you very much @cubefreak777 . that’s a really good explanation.

1 Like

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()