Halfway
This problem asks if we are performing comparisons between all pairs in a set using a double for loop, at what point are we halfway done?
The input size is too large (10^9) to explicitly simulate this (10^9^2), or likely to even go one iteration of the outer loop at a time (10^9).
We can, however, trivially calculate the total number of comparisons (n/2*(n+1)...be sure to use longs...we'll call this n+), and thus the sum of the numbers from n->m (just m+ - n+). We can use this to determine the comparisons needed for first so many iterations of the outer loop
- first loop takes n-1 comparisons ((n-1)+ - (n-2)+)
- first two loops take (n-1)+ - (n-3)+
- first k loops take (n-1)+ - (n-k-1)+
We can binary search over all N<n to find the last count which is smaller than half the number of comparisons.
Note: we may also be able to do this by directly solving for the height of the triangle which has half the area of the total area Note: be sure to use longs