0522HardArrayMathSorting

Tallest Silo in the Stacking Row

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A grain yard has silos silos standing in a straight row, numbered 1 through silos. Each silo is built up from identical rings, so its size is a whole number of rings, never negative. Silo 1 is the loading silo and holds exactly 0 rings.

A shared walkway runs along the row, and it can only span one ring of difference, so two silos standing next to each other differ by at most one ring.

Some silos sit under overhead cables. Each entry caps[i] = [pos, limit] says silo pos may hold at most limit rings. Every listed pos is different, and a silo with no entry has no limit of its own beyond the walkway rule.

The yard wants one silo as tall as the rules allow. Return the largest number of rings a single silo can hold in any arrangement that obeys every rule above.

Examples

Example 1

Input: silos = 6, caps = [[6, 2]]
Output: 3

The row 0, 1, 2, 3, 3, 2 obeys every rule: silo 1 holds 0 rings, neighbours never differ by more than one ring, and silo 6 stays within its limit of 2. Its tallest silo holds 3 rings.

Example 2

Input: silos = 10, caps = [[10, 0], [5, 8]]
Output: 4

The row 0, 1, 2, 3, 4, 3, 2, 2, 1, 0 keeps silo 5 under its limit of 8 and silo 10 at its limit of 0, and its tallest silo holds 4 rings.

Example 3

Input: silos = 5, caps = []
Output: 4

With no cables the row 0, 1, 2, 3, 4 is allowed, and its tallest silo holds 4 rings.

Constraints

2 <= silos <= 10^9
0 <= caps.length <= min(silos - 1, 10^5)
caps[i].length == 2
2 <= caps[i][0] <= silos
The values caps[i][0] are all different.
0 <= caps[i][1] <= 10^9
The answer is at most silos - 1, so it stays below 10^9.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def tallest_silo(silos: int, caps: list[list[int]]) -> int:

Java

public int tallestSilo(int silos, int[][] caps)

The intended approach

Time O(m log m) for m capped silos, dominated by the sort.Space O(m) for the sorted list of capped silos.

Sort the capped silos by position and treat silo 1 with its 0 rings as the first of them. Walk left to right replacing each limit by the smaller of the limit and what the previous capped silo permits across the gap, then walk right to left doing the same from the other side; after both walks each capped silo carries the true largest size it can reach. Inside a gap between two neighbouring capped silos the row can climb from one end and descend to the other, so the peak there is fixed by the two end sizes and the gap width, and the stretch past the last capped silo simply climbs by one ring per silo. Report the largest of those peaks.

Pythonentry point: tallest_silo

def tallest_silo(silos, caps):
    # O(m log m) for m caps: sort them, tighten each height from the left, then
    # from the right, then read the peak allowed inside every gap.
    anchors = [(1, 0)]
    for pos, lim in sorted((c[0], c[1]) for c in caps):
        prev_pos, prev_h = anchors[-1]
        reach = prev_h + (pos - prev_pos)
        anchors.append((pos, lim if lim < reach else reach))
    for i in range(len(anchors) - 2, -1, -1):
        pos, h = anchors[i]
        npos, nh = anchors[i + 1]
        room = nh + (npos - pos)
        if h > room:
            anchors[i] = (pos, room)
    best = 0
    for i in range(len(anchors) - 1):
        pos, h = anchors[i]
        npos, nh = anchors[i + 1]
        peak = (h + nh + (npos - pos)) // 2
        if peak > best:
            best = peak
    last_pos, last_h = anchors[-1]
    tail = last_h + (silos - last_pos)
    return tail if tail > best else best

The obvious version

Give every silo an array slot, start each uncapped silo at an impossibly large size and each capped silo at its limit, then sweep the whole row back and forth lowering any silo that exceeds a neighbour by more than one ring until nothing changes. Report the largest slot.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_tallest_silo(silos, caps):
    top = silos
    heights = [0] * (silos + 1)
    for i in range(2, silos + 1):
        heights[i] = top
    for c in caps:
        if c[1] < heights[c[0]]:
            heights[c[0]] = c[1]
    heights[1] = 0
    for _ in range(silos):
        for i in range(2, silos + 1):
            if heights[i] > heights[i - 1] + 1:
                heights[i] = heights[i - 1] + 1
        for i in range(silos - 1, 1, -1):
            if heights[i] > heights[i + 1] + 1:
                heights[i] = heights[i + 1] + 1
    return max(heights[1:])

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in