[Solved]: Cutting equal sticks from different sticks

ignougroup
Problem Detail: You have $n$ sticks of arbitrary lengths, not necessarily integral. By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get $k<n$ sticks such that:

  • All these $k$ sticks have the same length;
  • All $k$ sticks are at least as long as all other sticks.

Note that we obtain $n + C$ sticks after performing $C$ cuts. What algorithm would you use such that the number of necessary cuts is minimal? And what is that number? As an example, take $k=2$ and any $ngeq 2$. The following algorithm can be used:

  • Order the sticks by descending order of length such that $L_1geq L_2 geq ldots geq L_n$.
  • If $L_1geq 2 L_2$ then cut stick #1 to two equal pieces. There are now two sticks of length $L_1 / 2$, which are at least as long as the remaining sticks $2 ldots n$.
  • Otherwise ($L_1 < 2 L_2$), cut stick #1 to two unequal pieces of sizes $L_2$ and $L_1-L_2$. There are now two sticks of length $L_2$, which is longer than $L_1-L_2$ and the other sticks $3 ldots n$.

In both cases, a single cut is sufficient. I tried to generalize this to larger $k$, but there seem to be a lot of cases to consider. Can you find an elegant solution?

Asked By : Erel Segal-Halevi

Answered By : Raphael

The first core observation to solving this problem is that the feasibility of a cutting length $l$, $qquaddisplaystyle operatorname{Feasible}(l) = biggl[, sum_{i=1}^n Bigllfloorfrac{L_i}{l} Bigrrfloor geq k ,biggr]$, is piecewise-constant, left-continuous and non-increasing in $l$. Since the number of necessary cuts behaves similarly, finding the optimal length is just $qquaddisplaystyle l^{star} = max { l mid operatorname{Feasible}(l) }$. Furthermore, as the other answers have proposed, all jump discontinuities have the form $L_i/j$. This leaves us with a discrete, one-dimensional search problem amenable to binary search (after sorting a finite set of candidates). Note furthermore that we only need to consider the $L_i$ that are shorter than the $k$-largest one, since that one is always feasible. Then, different bounds on $j$ lead to algorithms of different efficiency.

  • $1 leq j leq k$ results in a search space of quadratic size (in $k$),
  • $1 leq j leq lceil k/i rceil$ in a linearithmic one (assuming the $L_i$ are sorted by decreasing size), and
  • slightly more involved bounds in a linear one.

Using this, we can solve the proposed problem in time $Theta(n + k log k)$ and space $Theta(n + k)$. One further observation is that the sum in $mathrm{Feasible}$ grows in $l$ by $1$ for each candidate $L_i/j$ “passed”, counting duplicates. Using this, we can use rank selection instead of binar search and obtain an algorithm that runs in time and space $Theta(n)$, which is optimal. Find the details in our article Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts (by Reitzig and Wild, 2015).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30073

Leave a Reply