Problem 5: Big Boxes

https://open.kattis.com/problems/bigboxes

Given an integer $w$, we can determine whether it's possible to partition the $n$ items into $k$ boxes of consecutive items such that each box has a weight of at most $w$. This is possible in $O(n)$ time taking a greedy approach. For example, if $w = 12$, $k = 2$:

3   1   1   3   9   5   2            Given


3   1   1   3   9   5   2            Current sum = 3
^

3   1   1   3   9   5   2            Current sum = 4
    ^

3   1   1   3   9   5   2            Current sum = 5
        ^

3   1   1   3   9   5   2            Current sum = 8
            ^

3   1   1   3 | 9   5   2            9 + 8 > 12, add partition
                ^                    Current sum = 9
        
3   1   1   3 | 9 | 5   2            5 + 9 > 12, add partition
                    ^                Current sum = 5
          
3   1   1   3 | 9 | 5   2            Current sum = 7
                        ^            3 groups -> impossible

We want to find the smallest $w$ such that it's possible to partition the $n$ items into $k$ boxes of consecutive items such that each box has a weight of at most $w$.

• If $w$ is a weight where the partitioning is impossible, then all weights less than $w$ are also cases where partitioning is impossible.

• However, if $w$ is a weight where the partitioning is possible, then then all weights greater than $w$ cannot be the smallest weight where partitioning is possible.

Therefore, we can find the smallest $w$ that satisfies the above equation using binary search.