Adeptalgorithms & data structures
The Chained Tomes of Halcrest Scriptorium
Deep in the Halcrest Scriptorium, a single long shelf holds a row of cursed tomes, each bound in iron chain. Every tome carries a curse weight, a positive whole number. The Order of the Grey Clasp has sent a company of wardens to carry the tomes out of the Scriptorium. Each tome must be carried by exactly one warden.
The rules of the work:
- Each warden takes one contiguous run of tomes from the shelf, keeping the shelf's order. No warden may take tomes that are separated by a tome carried by someone else.
- A warden's burden is the sum of the curse weights of the tomes they carry.
- There are
kwardens. Not every warden has to carry a tome, and a warden who carries none has a burden of 0.
Write divideTomes(weights, k).
weightsis a list of positive integers, the curse weights in shelf order. It may be empty.kis a positive integer, the number of wardens.
Return the smallest possible value of the largest burden carried by any single warden, taken over every valid way of dividing the shelf. If weights is empty, return 0.
examples
- case 1
weights [7, 2, 5, 10, 8], k = 218. The best split is [7, 2, 5] and [10, 8], with burdens 14 and 18. - case 2
weights [3, 1, 2], k = 53. Each tome gets its own warden and two wardens carry nothing, so the largest burden is the heaviest tome. - case 3
weights [], k = 30
- reward
- 320 XP
- signature
divideTomes
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
loading the editor…
- classic two wardens
- ascending weights two wardens
- one warden per tome
- single tome
- more wardens than tomes
- empty shelf
- lone warden carries everything
- long shelf eight wardens
- uniform weights uneven split
- heavy ends dominate