1121. Joining k Ropes at a Time

n piles of sand sit in a yard. One MOVE takes exactly k piles, ANY k of them, and merges them into a single pile at a cost equal to their combined size. Repeat until one pile remains.

Print the smallest total cost, or -1 when one pile can never be reached.

piles 1 2 3 4 5, k = 3 -> 21 piles 3 2 4 1, k = 3 -> -1 piles 1 2 3, k = 3 -> 6 piles 9, k = 5 -> 0

Trace the first line. Merge 1, 2 and 3 for a cost of 6, leaving 6 4 5. Merge all three for a cost of 15. The total is 21.

## When it is impossible, and why that must be checked first

Each move turns k piles into 1, lowering the count by k - 1. Starting at n and ending at 1 needs n - 1 to be divisible by k - 1.

3 2 4 1 with k = 3 has n - 1 = 3 and k - 1 = 2, and 3 is not divisible by 2, so no sequence of moves ends at one pile and the answer is -1.

This has to be tested BEFORE the loop, because a greedy loop that merges the k smallest will happily run out of piles mid-move and produce a number.

## What most people try first

Merging the k smallest without checking divisibility. That answers a number on impossible inputs.

Padding the pile list with zeros until the count works out, which is the textbook trick for building a k-ary Huffman code. It is the right move THERE, where a code word may be shorter than the others, and it is wrong HERE, because the statement says every move takes exactly k piles and a pile of size 0 does not exist in the yard. A solution that pads answers a number where -1 is correct.

Trying every sequence of moves costs about (n choose k) per move.

## The method

if n == 1: answer 0 if (n - 1) mod (k - 1) != 0: answer -1 put every size into a min-heap total = 0 while more than one pile remains: s = the sum of k pops total = total + s push s

O(n log n) with k pops per move.

## Why the k smallest

The same accounting as for pairs: every move charges the combined size of what it merges, so an original pile pays its size once for every move it takes part in, which is its DEPTH in the merge tree. The total is sum over piles of size * depth, and the tree is a k-ary tree whose leaves are the piles.

To make the total small, the LARGEST piles must sit shallowest. Suppose a tree has a pile x at depth dx and a pile y at depth dy with x > y and dx > dy. Swapping them changes the total by (dy - dx) * (x - y), which is negative, so the tree was not optimal. Depths must therefore decrease as sizes increase.

Now look at the DEEPEST level of an optimal tree. Every internal node at the level above it has exactly k children, since the divisibility condition means no move is ever short, and the k smallest piles can be placed as the children of one such node without increasing the total, by the swap just described. Merging them first is exactly that placement, and after the merge the problem is the same one with k - 1 fewer piles.

## The boundary that breaks a careless implementation

n = 1 answers 0 for every k, and the divisibility test must not be applied to it: n - 1 = 0 is divisible by everything, so the general test happens to agree, but a version that computes (n - 1) / (k - 1) before checking n divides by zero when k = 1. The constraints forbid k = 1, and it is worth knowing why: with k = 1 a move merges one pile into itself, the count never falls, and the process never ends.

k > n with n > 1 is impossible and the divisibility test catches it, since 0 < n - 1 < k - 1 leaves a non-zero remainder.

## Sizes

n reaches 1000 and a size reaches 10^9, so the total of all piles reaches 10^12 and the answer reaches about 10^15. That is far past the 2147483647 limit of a signed 32-bit integer, and the ninth test costs 1.8 * 10^10.

## Related problems

Problem #596 is k = 2, where the divisibility test is vacuous because n - 1 is always divisible by 1. Problem #562 is the same k-way merge restricted to ADJACENT piles, which destroys the greedy entirely and needs an interval table costing O(n^3 / k); comparing the two shows that "any k" is doing all the work here.

Constraints - `1 ≤ n ≤ 1000` - `2 ≤ k ≤ 1000` - `0 ≤ size ≤ 1000000000`