Problem Detail: Take a number i. You need to split it in two pieces as many times as necessary so that all splits are less than or equal to j. How does one obtain this with the minimum number of splits? Examples: Splitting it in half is optimal here:
i = 4, j = 2 4 -> 2, 2 // (1 split)
However, splitting in half is not optimal here:
i = 9, j = 3 9 -> 5, 4 // Split nine in half 5 -> 3, 2 // Then you have to split the 5 4 -> 2, 2 // and the 4 (3 splits)
The optimal solution here would be:
i = 9, j = 3 9 -> 6, 3 6 -> 3, 3 // (2 splits)
Is there some straightforward way to obtain the optimal split without brute-force iteration?
Asked By : dthree
Answered By : Yuval Filmus
The optimal strategy is the greedy one: repeatedly split chunks of size $j$. This strategy results in $lceil frac{i}{j} rceil – 1$ splits. We can prove that this strategy is optimal by induction on $i$. The strategy is clearly optimal for $i leq j$. Now suppose that we split $i > j$ as $i = i_1 + i_2$. In total, this choice will use up at least this many splits: $$ 1 + lceil tfrac{i_1}{j} rceil – 1 + lceil tfrac{i_2}{j} rceil – 1 = lceil tfrac{i_1}{j} rceil + lceil tfrac{i_2}{j} rceil – 1. $$ Let $alpha = i/j$, $alpha_1 = i_1/j$, $alpha_2 = i_2/j$, so that $alpha = alpha_1 + alpha_2$. To complete the proof, notice that $lceil alpha_1 rceil + lceil alpha_2 rceil geq lceil alpha rceil$, and so the quantity above is always at least $lceil tfrac{i}{j} rceil – 1$, as claimed. I have described one optimal strategy. Using the proof above, we can actually describe all optimal strategies. Splitting $i$ to $i_1+i_2$ is optimal iff $lceil frac{i_1}{j} rceil + lceil frac{i_2}{j} rceil = lceil frac{i}{j} rceil$. When does that happen? Define $$ i = aj-b, quad i_1 = a_1j-b_1, quad i_2 = a_2j-b_2, $$ where $0 leq b,b_1,b_2 < j$. A splitting is optimal iff $a_1 + a_2 = a$. Notice that $$ i_2 + i_2 = (a_1+a_2)j – b_1 – b_2. $$ This shows that the splitting is optimal iff $b_1 + b_2 = b$ (rather than $b + j$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41262
