773. The Cautious Burglar
n houses stand in a row. House i contains a[i] worth of goods. A burglar must rob at
least k houses, and may never rob two houses that stand next to each other.
The risk of a night's work is the value of the SINGLE most valuable house robbed. Print the
smallest risk with which at least k houses can be robbed.
a = 2 7 9 3 1, k = 2 answer 2 rob houses 1 and 5, worth 2 and 1
a = 2 3 5 9 1 4, k = 3 answer 5 rob houses 1, 3 and 5, worth 2, 5 and 1
a = 9 1 9 1 9, k = 3 answer 9 three non-adjacent houses must include two nines
a = 17, k = 1 answer 17 one house, and it must be robbed
## Why the usual house-robber machinery does not apply
The classic non-adjacent problem maximises the TOTAL taken, and a dynamic program over prefixes solves it. Here the objective is a maximum rather than a sum, and there is a count requirement rather than a free choice of how many to take. A DP carrying both "how many robbed so far" and "largest so far" is possible but quadratic.
The objective being a MAXIMUM is the signal. Whenever an answer is "the largest thing you are forced to accept", guessing that value and testing it turns the problem into a counting question.
## Testing a candidate
Say the burglar will not touch any house worth more than m. Which houses remain available?
Exactly those with a[i] <= m. So the question becomes: how many non-adjacent houses can be
chosen from that set?
count = 0, i = 0
while i < n:
if a[i] <= m:
count += 1
i += 2 # skip the neighbour, it is now off limits
else:
i += 1
feasible(m) = (count >= k)
## Why taking the leftmost available house is optimal
Let S be any valid selection of non-adjacent houses, all worth at most m, and let i be the
leftmost available house. Claim: there is a selection of the same size that includes i.
If S already contains i, done. Otherwise, let j be the smallest index in S. Every house
before i is unavailable, so j > i. Replace j by i. The result is still valid: i is
available by assumption, and the next chosen house after j is at index j + 2 or later, which
is more than one away from i because i < j. The size is unchanged.
So some maximum selection starts at i, and after taking i the same argument applies to the
sub-row starting at i + 2. The sweep therefore reaches the maximum possible count, which is
exactly what the feasibility test needs.
Note what the argument does NOT need: it never compares values. Once the threshold has filtered the houses, only positions matter, and that is why a value-based greedy (rob the cheapest houses first) is unnecessary here and in fact wrong.
## Why the predicate is monotone
Raising m only adds houses to the available set, and adding houses never reduces the maximum
number of non-adjacent choices. So the feasible thresholds form a suffix and the answer is the
FIRST true value.
## The bounds
lo = min(a) and hi = max(a). The answer is the value of some actual house, so it lies
between the smallest and largest. Searching 0 .. max(a) also works and simply wastes probes on
thresholds that admit exactly the same set of houses.
The constraint k <= ceil(n / 2) guarantees the answer exists, because ceil(n / 2) is the most
non-adjacent houses a row of n can hold.
## The boundary that breaks a careless implementation
The skip must be i += 2 on a TAKE and i += 1 on a SKIP. Advancing by two after rejecting a
house discards its neighbour for no reason: on 9 1 9 1 9 with m = 1 the correct count is 2,
and the buggy version reports 0, because stepping two at a time from index 0 lands on 0, 2 and
4, every one of them a nine, and it never sees either 1. That pushes the answer up to 9 on
inputs where it should be 1.
Stopping the sweep as soon as count reaches k is a legitimate shortcut, since the predicate
only asks whether the count REACHES k, never what it actually is. Break after the increment,
not before it, or the last house is counted and then discarded.
## Relationship with problem 756
756 runs the identical two-stage check. A candidate day turns every flower into open or not open, a candidate value here turns every house into robbable or not, and in both cases the sweep that follows never looks at a number again: it counts positions under an adjacency rule and compares that count with a required total.
The adjacency rules are mirror images. 756 needs its chosen flowers CONSECUTIVE, k in a row per
bouquet, so one closed flower wastes the partial run around it; this one needs its chosen houses
NON-adjacent, so every house taken costs its neighbour. Both answer the FIRST true threshold.
## Overflow
Values reach 10^9, which fits a signed 32-bit integer with room to spare, and nothing here is
summed. This is the problem in the block where 64-bit is NOT required, which is worth noticing:
the habit is good, but knowing why it is needed elsewhere matters more than applying it
everywhere.
## Cost
O(n log(max a)). Sorting the values and binary searching over the sorted array instead gives
O(n log n), which is the same order and no simpler.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k` and `2k ≤ n + 1` - `1 ≤ a[i] ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n house values, left to right.
Output
Print one integer on its own line: the smallest possible value of the most valuable house robbed. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.