821. The Tallest Tent in the Row
A row of n tents is being pitched. Every tent is a whole number of metres tall and at least
1 metre. Neighbouring tents may differ in height by at most 1 metre, so the row never steps by
more than a metre. The total canvas available is S metres, and the sum of all the heights may
not exceed it.
Tent number idx, counting from 0, is the one on show. Print the greatest height it can be
given, or -1 if the canvas cannot cover even a row of all ones.
n=4, idx=2, S=6 -> 2 heights 1 1 2 2
n=6, idx=1, S=10 -> 3 heights 2 3 2 1 1 1
n=5, idx=0, S=4 -> -1 five tents need at least 5 metres
## The cheapest row for a given peak
Fix a candidate height v for the show tent. To make v affordable, every other tent should be
as short as the rules allow, which means dropping away from idx by exactly one metre per step
until the floor of 1 metre is reached, and staying at 1 after that. That shape is legal and no
legal shape with the same peak is cheaper, so the question "can the show tent be v metres?"
becomes "does that cheapest row fit in S?".
The cost of one side with k tents on it is the sum of v-1, v-2, v-3 and so on, clipped at 1:
k <= v - 1 the side never reaches the floor
sum = (v-1 + v-k) * k / 2
k > v - 1 the side reaches the floor and then flattens
sum = (v-1) * v / 2 + (k - (v-1))
The left side has idx tents and the right side has n - 1 - idx, so the whole row costs
v + side(v, idx) + side(v, n - 1 - idx).
This is the composite part: the predicate is not a single comparison, it is a two-case closed
form evaluated twice. Getting the split wrong, or writing the triangular number as v * v / 2,
gives a check that is monotone but wrong, and a binary search on a wrong check returns a
confident wrong answer.
## Why the predicate is monotone
Raising v by one raises the show tent by one and raises every other tent by at most one, never
lowering any of them, so the total cost is strictly increasing in v. Affordable heights
therefore form a PREFIX 1, 2, ..., answer and the answer is the last one.
## The bounds
lo = 1, the minimum legal height.
hi = S - (n - 1). Every other tent costs at least 1 metre, so at most that much canvas can
ever reach the show tent. Using S itself as hi is not wrong, only wasteful; using
max(S / n, 1) IS wrong, and the second example shows why, since 3 is larger than 10 / 6.
## Searching for the LAST true instead of the first
Every other problem in this block searches for the first true. Here the good values come
first, so the loop flips, and so does the midpoint:
mid = hi - (hi - lo) / 2 round UP, not down
if affordable(mid) lo = mid keep mid, it is a candidate
else hi = mid - 1
Rounding down here is an infinite loop, not a wrong answer. With lo = 3 and hi = 4 the
downward midpoint is 3, and if 3 is affordable the assignment lo = 3 changes nothing and the
loop spins forever. The upward midpoint gives 4 and the range always shrinks. Writing it as
hi - (hi - lo) / 2 also keeps it safe from the overflow that (lo + hi + 1) / 2 invites.
## When the answer does not exist
If S < n then even the all-ones row does not fit and nothing is legal, so print -1. Check
that before the search, because hi would otherwise come out below lo.
## Overflow
With v near 10^9 and a side of 10^5 tents, (v-1 + v-k) * k is about 2 * 10^14.
That needs 64 bits before the division by two, and a 32-bit product wraps to a small or negative
number, which reads as "affordable" and pushes the search far too high.
## Cost
Time O(log S), since each check is closed form. Space O(1).
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ idx < n` - `1 ≤ S ≤ 1000000000`
Input
A single line with three integers n, idx and S: the number of tents, the 0-based position of the tent on show, and the total metres of canvas.
Output
Print one integer, the greatest whole height the tent at position idx can be given, or -1 if no legal row fits the canvas. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.