rust / LEVEL 3

The backfill rate guessed from averages

EST.40 MIN

THEORY / RETRIEVAL

What to restore

Turn an optimization problem into a monotonic feasibility predicate
Maintain a closed binary-search interval without midpoint overflow
Compute integer ceilings and accumulated work without overflow

Binary search can target an answer value

At a fixed positive rate r, a shard with w rows needs ceil(w/r) ticks. If a rate is feasible, every larger rate is also feasible, creating a false…false, true…true predicate. Binary search returns the first true rate without enumerating every capacity.

Arithmetic is part of the invariant

Use quotient plus a nonzero remainder for ceiling division instead of `(w + r - 1) / r`, which can overflow. Accumulate ticks with `checked_add` and stop as soon as the deadline is exceeded. Compute midpoint as low + (high-low)/2.

CHECKPOINT

Why is the minimum feasible backfill rate searchable with binary search?

Confidence: 3/5

02 / IMPLEMENTATION

Implement the contract

Implement `minimum_rate`. Shards run one after another and shard work w takes ceil(w/rate) ticks. Return the smallest positive rate that finishes within deadline_ticks. Empty/all-zero work returns 0; if deadline is shorter than the number of nonzero shards, return DeadlineTooShort. Handle u64::MAX without overflow.

Initializing editor…

CLOUD SANDBOXnetwork off · 256 MB · 12 s

1 / 64 KB

OUTPUT

Runner is waiting for a submission.