1601. How Many Pairs Where One More Than Doubles the Other
Given n integers, count the pairs (i, j) with i < j and
a[i] > 2 * a[j].
6 1 2 7 3 -> 3 6 > 2*1, 6 > 2*2, and 7 > 2*3
1 2 3 4 -> 0 the array is increasing
10 1 -> 1
## What most people try first
Two nested loops, which is correct and O(n^2): at n = 10^5 that is
10^10 pair tests. As in problem 2003, the count itself rules out any method
that inspects pairs one at a time, because a reversed array has about
5 * 10^9 qualifying pairs. The answer has to be accumulated in groups.
## Split the array and count across the cut
Sort the halves as you go, the way merge sort does, and count the pairs that STRADDLE the midpoint while merging:
solve(lo, hi):
if the range has one element: return 0, that element
split at mid
count = solve(left) + solve(right)
count += pairs with i in left and j in right
merge the two sorted halves
Every pair (i, j) with i < j straddles exactly one cut in the recursion,
namely the cut of the smallest range containing both. So summing over all cuts
counts each pair exactly once, with nothing to subtract.
## Counting across the cut in one sweep
Both halves are sorted by the time the counting happens. So walk v through
the left half in increasing order and advance a pointer j over the right half
while 2 * right[j] < v:
j = 0
for v in left (ascending):
while j < len(right) and 2 * right[j] < v: j += 1
count += j
j never moves backwards, because a larger v admits everything a smaller one
did. That is what makes the cross-count linear rather than quadratic, and it is
the same monotone-pointer argument the two-pointer topic is built on.
## Why the halves may be reordered
The condition uses the VALUES, and the index condition i < j is already
guaranteed by which half an element sits in. Once the straddling pairs are
counted, the original order inside each half is no longer needed, so sorting it
destroys nothing the rest of the computation uses. Recognising when a sort is
free is most of the skill here.
## Overflow
The count reaches n (n - 1) / 2, about 5 * 10^9 at n = 10^5, which is past
the 2147483647 a signed 32 bit integer holds, so the counter needs 64 bits.
Separately 2 * a[j] reaches 2 * 10^9, which FITS in 32 bits since the limit
is 2147483647, and -2 * 10^9 fits too. Only the count overflows.
## Cost
O(n log n): the recursion has log n levels and each level does linear work
to merge and count.
Constraints - `1 ≤ n ≤ 100000` - `-10^9 ≤ each value ≤ 10^9` - values may repeat
Input
The first line contains the integer n.
The second line contains n integers.
Output
Print one integer on its own line: the number of pairs (i, j) with i < j and a[i] > 2 * a[j].
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.