Red Cut

Every cutting process corresponds to a full binary tree whose leaf order is fixed. An internal node's boundary is red exactly when the interval represented by that node has odd length.

Tracking the number of current odd-length pieces gives the possible number of red cuts:

• If $N=2m$, then $0\leq K\leq m-1$.
• If $N=2m+1$, then $1\leq K\leq m$.

For an odd interval of length $2m+1$, call the following sets certificate blocks:

$$\{1\},\{2,3\},\{4,5\},\cdots,\{2m-2,2m-1\},\{2m\}.$$

Induction shows that every feasible red-boundary set contains a complete certificate block. Conversely, the following conditions are sufficient:

• For length $2m$, every boundary set of size at most $m-1$ is feasible.
• For length $2m+1$, every set of size between $1$ and $m$ that contains a certificate block is feasible.

Sufficiency follows by strong induction, choosing the first cut so the remaining requirements split into smaller even and odd intervals.

If $N$ is even, choose the $K$ cheapest boundaries. If $N$ is odd, enumerate a forced certificate block $B$ and add the cheapest $K-|B|$ boundaries outside . After sorting costs, store prefix sums and each boundary's rank. Since a block has at most two elements, each candidate is evaluated in .

The total time complexity is $O(N\log N)$ and the memory complexity is $O(N)$.

Solution written by GPT5