سوال ۶۳ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱

Reformulate the condition

We must count index pairs $(i,j)$ with

$A[i]\cdot A[j] > i\cdot j.$

Divide both sides by the positive quantity $i\cdot j$ (indices are positive). Equivalently, define for each position

$b_k = \frac{A[k]}{k}.$

Then the condition becomes

$b_i\cdot b_j > 1.$

Taking logarithms, with $c_k = \log b_k = \log A[k] - \log k$, this is exactly

$c_i + c_j > 0.$

So the problem reduces to: count the number of pairs whose values sum to more than a threshold (here the threshold is $0$).

Counting pairs with sum above a threshold

This is a standard $O(n\log n)$ task:

1. Compute all $n$ values $c_k$ in $\Theta(n)$.
2. Sort them: $\Theta(n\log n)$.
3. Use a two-pointer sweep (or, for each element, a binary search) over the sorted array to count, in $\Theta(n)$ total, how many pairs satisfy $c_i + c_j > 0$.

The two-pointer step: with pointers $l=0$, $r=n-1$ on the sorted array, if $c_l + c_r > 0$ then all elements between $l$ and $r$ also pair with $r$ to exceed $0$, so add $r-l$ and decrement $r$; otherwise increment $l$. Each pointer moves at most $n$ times, giving $\Theta(n)$.

The dominant cost is the sort, so the whole task is

$\Theta(n\log n) = O(n\log n).$

Why not the others

• $O(n^{2})$ / $O(n^{2}\log n)$ — the brute-force "check every pair" is $\Theta(n^{2})$, but the question asks for the best achievable time, which is faster.
• $O(n\log^{2} n)$ — achievable (e.g., merge-sort-style counting), but not the tightest; a single sort plus a linear two-pointer scan already gives $O(n\log n)$.

Exam trick: "product of two array entries exceeds something" almost always becomes a pair-sum problem after taking a ratio or a logarithm, and counting pairs whose sum beats a threshold is the textbook sort + two-pointer $O(n\log n)$ pattern.