Optimal Bucket Batching to Minimize Padding (DP)

You have K documents with lengths len[i] (positive integers) and G GPUs. You must split all documents into exactly G batches (one per GPU). For any batch: Let Lmax be the maximum document length in that batch. Padding cost of the batch is batch_size * Lmax - (sum of lengths in the batch), i.e., pad every doc to Lmax and count total padded tokens. Task: find a partition minimizing total padding cost. Rules: Each document belongs to exactly one batch. Each batch must contain at least one document. You may sort documents by length before batching. Constraints: 1 <= G <= K <= 2000 (if K < G appears, treat as infeasible or define empty batches with zero cost; typical interview constraint is G <= K). Output: The minimum total padding cost. One optimal batching (print each batch as a list of lengths). Input (stdin) Line 1: K G Line 2: K integers len[0..K-1] Output (stdout) Line 1: minimum total padding cost Next G lines: one batch per line (space-separated lengths) Example Input: 5 2 2 3 3 10 10 One optimal output (one of many): 1 2 3 3 10 10 Example Input 5 2 2 3 3 10 10 Output 1 2 3 3 10 10