← All solutions

This problem can be solved with dynamic programming. A good state is the following: given a subset S ⊆ [n] of friends and a desired width w, is it possible to split some chocolate bar of width w among the friends in S? Note that the height h of such a chocolate bar must necessarily be the sum of the demands of the friends in S divided by w (and if this is not an integer the answer must be “No”).

To compute whether a state (S, w) has answer yes, we iterate over all non-empty proper subsets ∅ ≠ T ⊂ S. For each such T, we try cutting the w × h bar either vertically or horizontally, putting T in one part and S \ T in the other part. The position to cut the bar is determined by the set T (and some T can make the cut impossible, e.g., if the sum of demands in T is not a multiple of w then no horizontal cut can be made).