Merge Alarm

The displayed value of a bundle containing $L$ original pieces is always $L\bmod M$, independently of the merge order.

Let $P$ be the sum of the displayed values of all current bundles. A merge without an alarm leaves $P$ unchanged, while an alarm decreases it by exactly $M$. Initially $P=N$, and finally $P=N\bmod M$. Thus every merge order produces exactly

$$q=\left\lfloor\frac{N}{M}\right\rfloor$$

alarms.

The key sufficiency result is that any set of $q$ boundaries can be the alarm set. For an interval of length $L=qM+r$, its last merge at local boundary $k$ raises an alarm exactly when $k\bmod M>r$. For every target set of size , there is a split such that the left side receives exactly selected boundaries and the membership of agrees with that alarm condition. Splitting there and applying induction to both children realizes all of .

Therefore the feasible alarm sets are exactly all boundary subsets of size $q$. Choose the $q$ smallest costs. Sorting dominates the running time, so the complexity is $O(N\log N)$.

Solution written by GPT5