660. Selections Whose Smallest and Largest Stay Within a Limit
Count the non-empty SELECTIONS of values, chosen by position, whose smallest value plus
largest value is at most the target. Print the count modulo 1000000007.
Two selections differing in which positions they use are different, even when the values match.
3 5 6 7, target 9 -> 4
3 3 6 8, target 10 -> 6
1, target 1 -> 0
## Order does not matter, so sort
A selection is judged only by its smallest and largest value, and neither depends on the order the values sat in. So the array may be sorted freely, and the count is unchanged.
That is the observation that unlocks the whole problem, and it is worth checking rather than
assuming: it holds here because the condition mentions only min and max, and would NOT hold
if the condition mentioned adjacency or order.
## Count by the smallest value
After sorting, fix i as the position of the smallest chosen value. The largest may be any
position j >= i with a[i] + a[j] <= target, and everything strictly between i and j is
free to be in or out.
So for the largest legal j, the number of selections with minimum at i is
2^(j - i)
which counts every subset of the positions between them, and includes the single-element
selection when j = i.
## The sweep
i = 0, j = n-1
while i <= j:
if a[i] + a[j] <= target: answer += 2^(j - i); i += 1
else: j -= 1
When the pair fits, every j' <= j also fits with this i, and they are all already counted
by the power of two. So i is finished. When it does not fit, a[j] is too large for even the
smallest remaining value, so it can be retired.
## Why i <= j, not i < j
A selection of a single value has its minimum and maximum equal, and is legal when
2 * a[i] <= target. That case is found only when the pointers meet, so the loop must allow
it, exactly as in problem 647.
1 with target 1 answers 0 and with target 2 answers 1, and those two inputs pin it.
## Precompute the powers
2^(j-i) is needed for many pairs, so build a table of powers up to n once. Recomputing the
power inside the loop turns a linear sweep into O(n log n) for no reason.
## Cost
Time O(n log n) for the sort. Space O(n) for the powers.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 10^9` - `1 ≤ target ≤ 2 * 10^9`
Input
The first line contains two integers n and target.
The second line contains n integers.
Output
Print one integer, the number of valid selections, modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.