The Wyvern Lift of Hask Ridge
The Ridgewardens of Hask Ridge are hauling an expedition's supply crates up the sheer north face to the eyrie camp, and they will do it by wyvern. The crates are lashed together in one long chain. The chain may be cut between any two neighbouring crates, but it may never be reordered. Each wyvern then lifts one unbroken stretch of the chain. The Wardens post this contract for whoever can tell them how light the heaviest wyvern's burden can be made.
Write heaviestLoad(weights, wyverns).
weightsis a non-empty list of positive integers: the weight of each crate, in chain order.wyvernsis a positive integer: the greatest number of wyverns that may fly.
A valid division gives every crate to exactly one wyvern. Each wyvern takes a contiguous run of crates in their original order. No more than wyverns wyverns may be used, and any wyvern may stay roosted and carry nothing. A wyvern's load is the sum of the weights of the crates it carries.
Return an integer: the smallest possible value, over all valid divisions, of the largest load carried by any single wyvern.
examples
- case 1
weights of [7, 2, 5, 10, 8], 2 wyverns18 — one wyvern takes 7 + 2 + 5 = 14 and the other takes 10 + 8 = 18 - case 2
weights of [4, 9, 2], 10 wyverns9 — each crate flies alone, so the 9-weight crate sets the load, and seven wyverns stay roosted - case 3
weights of [4, 9, 2], 1 wyvern15 — the lone wyvern carries the whole chain
- reward
- 360 XP
- signature
heaviestLoad
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- classic two-way split
- ascending chain split in two
- single wyvern carries everything
- more wyverns than crates
- single crate
- exactly one wyvern per crate
- equal crates, uneven grouping
- alternating chain, four wyverns
- long chain, one boulder in the middle
- long chain, boulder at the end