Editorial for WC '18 Contest 4 J3 - Inventory


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Each of the C size-3 items requires its very own knapsack. This amounts to C knapsacks.

Each of the B size-2 items cannot fit into a knapsack with any other size-2 items, so this amounts to another B knapsacks. However, each of those knapsacks also has space for a size-1 item, so we should go ahead and dispose of \min(A, B) size-1 items along the way.

Finally, the remaining size-1 items (of which there are \max(0, A-B)) should be packed into knapsacks 3 at a time, with one potentially non-full knapsack remaining at the end. This amounts to another \lceil \frac{\max(0, A-B)}{3} \rceil knapsacks (or, equivalently, \lfloor \frac{\max(0, A-B)+2}{3} \rfloor knapsacks).


Comments

There are no comments at the moment.