1090. Taking the Biggest House First
A row of n houses holds a known amount each. You may take from any set of
houses provided NO TWO ARE NEIGHBOURS.
Compare two methods and print both totals, separated by a space.
The GREEDY method: repeatedly take the largest amount among the houses that are still available, where a house is available when it has not been taken and neither of its neighbours has been taken. Break ties by taking the leftmost such house. Stop when nothing is available.
The TRUE method: the largest total achievable by any legal set.
4 5 4 -> 5 8 greedy takes the 5 and is then blocked; 4 + 4 is better
1 2 3 1 -> 4 4 both find 1 + 3
2 7 9 3 1 -> 12 12
3 2 5 10 7 1 4 -> 17 19
## Why the greedy is tempting
"Take the biggest thing you can" is the instinct every greedy problem starts from, and on most inputs it is right. It agrees on three of the four rows above. What it cannot see is that a single large value sitting between two nearly-as-large ones costs you BOTH of them.
4 5 4 is the smallest counterexample. Taking the 5 blocks the houses on either side and
leaves 5. Skipping it takes 4 and 4 for 8.
The gap can be made as large as you like: k, k+1, k, k+1, k with k large has the greedy
taking a k+1, blocking two ks, and the loss compounds.
## Computing the greedy exactly as described
The rule has to be simulated, because "largest available" changes as houses are blocked.
sort the indices by amount descending, tie-break by index ascending
mark nothing taken or blocked
repeat:
walk that sorted order and take the first index that is neither taken nor blocked
if none exists, stop
add its amount, mark it taken, mark both neighbours blocked
Written naively that is O(n^2), which is fine at n = 2000. Keeping a pointer into the
sorted order that only moves forward makes it O(n log n), since an index is skipped
permanently once it is blocked.
## Computing the true answer
The standard two-state sweep, which is problem #451's recurrence:
take = 0, skip = 0
for each amount v:
take, skip = skip + v, max(skip, take)
answer = max(take, skip)
take is the best total ending with this house taken and skip the best ending with it
left alone.
## What the comparison is for
Producing the counterexample is the skill. Anyone can say "greedy might be wrong"; being able
to hand over 4 5 4 and the two numbers it gives is what settles the argument.
Note also that the greedy is not merely sometimes wrong, it can be wrong by an unbounded amount, which rules out using it even as an approximation.
## Overflow
n reaches 2000 and an amount reaches 10^9, so a total reaches 10^12. The signed
32 bit limit is 2147483647, and the short test with three houses of 10^9 separated by
zeros already totals 3 * 10^9 on both sides.
## Cost
Time O(n^2) for the simulation as written, O(n) for the true answer. Space O(n).
Constraints - `1 ≤ n ≤ 2000` - `0 ≤ amount[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers, the amounts.
Output
Print two integers on one line separated by a single space: the total the largest-first greedy collects, then the true maximum. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.