‹ back to the board

Monday, November 9

Adeptalgorithms & data structures

The Grimoire-Copyists of Vellumhaugh Abbey

The Abbess of Vellumhaugh holds the only surviving copy of the *Codex Ashenward*, a grimoire of binding-rites, and its ink is fading fast. The Guild of Quiet Hands is commissioned to copy it before the codex is lost. The copyists work in parallel at the same pace, so the copying lasts as long as the heaviest share given to any one copyist.

The grimoire's chapters are given in order as pages, a list of positive integers where pages[i] is the page count of chapter i. There are scribes copyists, an integer of at least 1.

The chapters are divided under these rules: - Every chapter is copied whole by exactly one copyist. A chapter is never split. - Each copyist takes one contiguous run of chapters. The order of the chapters is never changed. - A copyist may be given no chapters at all.

A copyist's load is the total number of pages in their chapters.

Write heaviestShare(pages, scribes), which returns an integer: the smallest possible value of the largest load, taken over all valid ways to divide the chapters. If pages is empty, return 0.

  • binary search
  • Adept

examples

  1. case 1pages of [7, 2, 5, 10, 8], scribes of 218 — the first copyist takes 7 + 2 + 5 = 14 pages and the second takes 10 + 8 = 18 pages
  2. case 2pages of [3, 1, 4, 1, 5], scribes of 105 — each chapter gets its own copyist, and the five extra copyists sit idle
  3. case 3pages of [], scribes of 30 — there is nothing to copy
reward
320 XP
signature
heaviestShare
not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…
  • classic two copyists
  • ascending chapters, two copyists
  • uneven tail favours early split
  • empty grimoire
  • single chapter single copyist
  • more copyists than chapters
  • one copyist takes everything
  • giant chapter dominates
  • three copyists mixed chapters
  • ten equal pages three copyists
  • equal chapters fewer copyists
  • exactly one copyist per chapter
The Grimoire-Copyists of Vellumhaugh Abbey · bitwick