Rosettes on the bench

Entries at a produce show stand in a line along the bench with the judge's mark chalked beside each one. The secretary prints the rosettes and wants to print as few as she can.

The problem

The bench holds n entries left to right; scores[i] is the mark on entry i. Two rules fix the pile of rosettes in front of each:

• every entry gets at least one rosette;
• an entry that outscores the entry immediately beside it, on either side, gets a strictly larger pile than that neighbour.

Equal marks put no rule on either entry. Report the fewest rosettes that satisfy both rules.

Input. scores — a list of n integers, the judge's mark for each entry in bench order.

Output. The smallest total number of rosettes.

Example.

scores = [4, 7, 5]   ->  4

The 7 outscores both neighbours, so its pile is at least 2 while the outer two hold one each.

A second example, where one walk down the bench is not enough:

scores = [2, 5, 9, 7, 4]   ->  9

The piles are 1, 2, 3, 2, 1. Going left to right alone leaves the 7 holding a single rosette — the same as the 4 it beats — and stops at 8.

Constraints.

• 1 <= len(scores) <= 10^5
• 0 <= scores[i] <= 10^9

Hints

Approach

Brute force

Start every pile at one, sweep the bench raising any pile that breaks a rule, and repeat until a sweep changes nothing. Marks that fall away steadily promote one entry per sweep, so [9, 8, 7, ...] needs n of them: O(n²), or 10¹⁰ comparisons at the top of the constraints.

The insight

Each rule constrains an entry against one neighbour, so the two directions can be settled separately: the smallest legal pile is the larger of what the left-hand rules demand and what the right-hand rules demand.

The forward sweep gives every entry the smallest pile its left-hand rules allow, and the backward sweep does the same for the right-hand ones. The second sweep cannot undo the first: it raises pile i only when scores[i] > scores[i + 1], and the forward rule on that pair needs the opposite comparison, so no rule the first sweep settled is ever touched. Every raise was forced by some rule, so no smaller total is legal.

Algorithm

1. Give every entry one rosette.
2. For i from 1 upwards: if scores[i] > scores[i - 1], set pile i to pile i - 1 plus one.
3. For i from n - 2 downwards: if scores[i] > scores[i + 1], raise pile i to at least pile i + 1 plus one.
4. Return the sum of the piles.

Complexity

Time O(n) — two passes, one comparison each. Space O(n) for the piles: a running total cannot replace them, because the second sweep revises what the first one wrote.

Solution

"""Rosettes on the bench — one sweep per side, then the larger claim wins."""


def solve(scores):
    n = len(scores)
    rosettes = [1] * n                     # the show owes every entry at least one
    for i in range(1, n):
        # left sweep: settle every "beats the entry on its left" claim
        if scores[i] > scores[i - 1]:
            rosettes[i] = rosettes[i - 1] + 1
    for i in range(n - 2, -1, -1):
        # right sweep: raising a pile never breaks a claim the left sweep settled
        if scores[i] > scores[i + 1]:
            rosettes[i] = max(rosettes[i], rosettes[i + 1] + 1)
    return sum(rosettes)

TESTS = [
    (([4, 7, 5],), 4),
    (([2, 5, 9, 7, 4],), 9),
    (([6, 6, 6],), 3),
    (([8],), 1),
    (([1, 2, 3, 4],), 10),
    (([9, 7, 5, 3],), 10),
    (([3, 8, 8, 2],), 6),
]

Pitfalls

• Sweeping in one direction only. The second example then leaves the 7 with the rosette the forward pass gave it and totals 8, one short of legal.
• Adding the two sweeps instead of keeping the larger. The peak of the second example ends up with 5 rosettes where 3 obeys every rule, and the show prints 11.
• Treating equal marks as a rule. Comparing with >= makes the two 8s in [3, 8, 8, 2] outrank each other, and the total comes to 9 where 6 is enough.

Variants

• Water for the whole ring — another linear greedy that never sorts, deciding as it walks the line.
• The exchange argument — why "every raise was forced" is the version of the proof that fits here.