677. Applying a Quadratic and Keeping It Sorted
A non-decreasing list is given, along with three numbers A, B and C. Apply
f(x) = A*x*x + B*x + C to every value and print the results in non-decreasing order.
-4 -2 2 4 with A=1 B=3 C=5 -> 3 9 15 33
-4 -2 2 4 with A=-1 B=3 C=5 -> -23 -5 1 7
1 2 3 with A=1 B=0 C=0 -> 1 4 9
## Why the results are not already sorted
A quadratic is not monotone. With A > 0 it falls then rises, so the SMALLEST results come
from the middle of the input and the largest from the two ends. With A < 0 it is the other
way round.
Applying f and sorting afterwards is correct and costs O(n log n). The structure above
gives O(n).
## The shape of the answer
With A > 0, the largest result is at one of the two ENDS of the input, because f grows as
you move away from the vertex and the ends are furthest from it.
So: evaluate f at both ends, take the larger, write it at the BACK of the output, and move
that pointer inward. Repeat. The output fills from the back downwards.
i = 0, j = n-1, k = n-1
while i <= j:
if f(a[i]) >= f(a[j]): out[k] = f(a[i]); i += 1
else: out[k] = f(a[j]); j -= 1
k -= 1
With A < 0 the smallest result is at an end instead, so take the SMALLER and fill from the
front upwards.
## Why the ends really are the extremes
For A > 0, f is decreasing to the left of its vertex and increasing to the right. The input
is sorted, so a[i] is the furthest remaining value on the left and a[j] the furthest on the
right. Every value between them is closer to the vertex and so has a smaller f.
That is what licenses taking the maximum of just two candidates instead of scanning.
## Why A = 0 needs no special case
With A = 0 the function is linear, so it is monotone and one end is the maximum and the other
the minimum. Comparing the two ends still picks correctly, whichever direction the line runs.
So the A >= 0 branch covers it, and A = 0, B = 1 is a test.
## Overflow
With values up to 10^9 and A up to 100, A*x*x reaches 10^20, which is past 64 bits.
The constraints keep values to 10^4 and coefficients to 100, so f stays within about
10^10 and 64 bits is enough.
## Cost
Time O(n). Space O(n) for the output.
Constraints - `1 ≤ n ≤ 200000` - `-10^4 ≤ each value ≤ 10^4` - `-100 ≤ A, B, C ≤ 100` - the list is non-decreasing
Input
The first line contains four integers n, A, B and C.
The second line contains n integers in non-decreasing order.
Output
Print the n results in non-decreasing order on one line, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.