You can just move the lightest half of the boxes each time.
replyA few additional constraints:
reply - the boxes are stacked
- the heavy boxes are at the bottom of a stack, and you can't stack a heavy box on top of a light one
- boxes aren't the same size
- some boxes are open, so must be put on top
- storage space and height are limitedIf you randomly index them and there's enough of them then on average the partitions average out.
replyThis is true, but it probably isn't a box of books that's beeping.
replyI also feel like ordering the moves by lightest box first is reasonable as a real-world optimization.
Typically, the heavy boxes are at the bottom too; to some extent, the piles will already be sorted by weight.
replyLol classic “ignore the constant factor” gotcha when using Big-O.
reply