1
$\begingroup$

Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last generated list.

By "splitting" a number $x$ I mean deleting $x$ from $L$ and adding to $L$ two positive numbers $\alpha,\beta$ verifying $\alpha+\beta=x$. We can only do this $n$ times.

My try was taking the two greatest elements of $L$, $\alpha$ (the maximum) and $\beta$ (the other), then I split $\alpha$ into $c=\min(\alpha/\beta+1,n+1)$ equal parts (the last part will be $\frac{\alpha}{(\alpha/\beta+1)}+\alpha\text{mod}(\alpha/\beta+1)$). So I spend $c$ of the hability.

Then I repeat the process until I run out of the hability or $\beta=1$, so then y take $c=\min(\alpha/\beta+1,n+1)-1$.

I know my try is not correct, as the list $(10, 4, 9)$ for $n=4$ is a counterexample. Any idea?

I'm not looking for efficiency details (it can be achieved working with heaps), only for correctness.

$\endgroup$
  • $\begingroup$ By "splitting" a number $\alpha$ I mean deleting $\alpha$ from $L$ and adding to $L$ two positive numbers $\alpha,\beta$ verifying $\alpha+\beta=x$. I assume you meant splitting a number $x$ by deleting $x$? $\endgroup$ – orlp Oct 29 '17 at 21:17
  • $\begingroup$ Yes, you're right $\endgroup$ – Álvaro G. Tenorio Oct 29 '17 at 21:18
3
$\begingroup$

If we use $k$ splits on a single element $x$ of the list, the lowest value we can reach is $\dfrac{x}{k+1}$. In turn, we need $\displaystyle k = \left \lceil\frac{x}{v}\right\rceil - 1$ splits for $x$ to reach a certain value $v$.

Elements do not affect each other, after all to reach some maximum $v$ after splitting each element must reach it individually.

So you simply want to find the smallest possible $v$ such that $$\sum_{x \in L}\left\lceil\frac{x}{v}\right\rceil \leq n + |L|$$

You can find $v$ to arbitrary precision by using a binary search using the above check, starting with range $[0, \max L]$. Finding an exact answer is somewhat trickier though.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.