The Comet-Shards of the Gwendrel Ice-Field
A comet broke apart over the Gwendrel Ice-Field last winter, and its shards now lie strung along a single trail through the snow. The Frostward Expedition has been commissioned to haul every shard back to Bitwick by sledge. The shards must be loaded in the order they lie on the trail. The expedition's master wants the loads balanced so that no sledge is burdened more than it must be.
The data
shardsis a list of positive integers. Each one is the weight of a shard, listed in the order the shards lie along the trail. The list may be empty.sledgesis a positive integer: the number of sledges available.
The rules of loading
- Every shard is loaded onto exactly one sledge. No shard may be split.
- Each sledge carries one consecutive run of shards from the list, so the list is cut into at most
sledgescontiguous pieces without reordering. - A sledge may carry nothing.
- A sledge's load is the sum of the weights of its shards.
The task
Write heaviestLoad(shards, sledges). Over all valid loadings, it returns the smallest possible value of the heaviest sledge's load, as an integer. If shards is empty, return 0.
The trail may hold up to 100,000 shards, so a loading that tries every way to cut the list will not finish before the thaw.
examples
- case 1
shards [7, 2, 5, 10, 8], sledges 218. Load [7, 2, 5] on the first sledge (14) and [10, 8] on the second (18). - case 2
shards [2, 3, 1, 2, 4, 3], sledges 104. Each shard can ride alone and the spare sledges go empty, but the shard weighing 4 still has to ride somewhere. - case 3
shards [], sledges 30. There is nothing to haul.
- reward
- 320 XP
- signature
heaviestLoad
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- classic two-sledge split
- ascending weights two sledges
- one sledge per shard
- empty trail
- single shard single sledge
- one sledge carries everything
- more sledges than shards
- heavy shard dominates
- one to ten across three sledges
- equal shards even split