If I have a constraint like $y_1 + y_2 +\dots + y_n = k$ for positive integers $y_i$, how would I minimize $$\quad\frac{x_1 }{ y_1} + \frac{x_2 }{ y_2} + \frac{x_3 }{ y_3} + \dots + \frac{x_n }{ y_n}$$ if all of the $x_i$ are given?

One can assume that $n\le5\cdot10^5$ and $k\le10^{12}$.

  • 2
    $\begingroup$ Welcome to CS.SE! 1. Can you provide the source of this question? You mentioned elsewhere it is from a competitive programming contest; I encourage you to credit the source. 2. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving contest problems for you is unlikely to achieve that. You might find this page helpful in improving your question. 3. Please take some time to improve the title; we have collected some advice here. Thank you! $\endgroup$ – D.W. Jan 16 '17 at 5:52
  • $\begingroup$ Hi, I couldn't dig out this problem from SPOJ for the life of me :(, but I do somewhat remember the bounds: a rough estimate would be n<=5*10^5 and k<=10^12, so my first thought was binary searching on an upper bound or lower bound. If k were smaller pushing into a priority queue would workin k log n, I would think. $\endgroup$ – qt. Jan 16 '17 at 6:19
  • $\begingroup$ Can you edit the question to incorporate what you've learned from the comments and attempted answers? (e.g., for each approach considered so far, give a concise counterexample or argument to show why that approach doesn't work). $\endgroup$ – D.W. Jan 17 '17 at 5:44

For $n=2$ there is a solution:

Minimize $f(y) = x_1/y_1 + x_2/(k-y_1)$, it is convex for $y_1 >0$ so you can find derivative, solve it for $=0$ and get the solution in reals, then check floor and ceil.

For general $n$ rounding needs more investigation. The only thing I'll mention that the real solution is something like $y_i = k \cdot \frac{\sqrt{x_i}}{\sum\limits_i {\sqrt{x_i}}}$, from the lagrangian. Then you do the $\max (1, \lfloor y_i \rfloor)$ and use other deeper results or greedy discussed to reach the sun to be exactly $k$.

UPD: Using greedy after this step, it will take time at most $n$ steps, resulting in $O(n)$ time. Reminder: add 1 to the $y_i$ where the difference $ \frac{x_i}{y_i} - \frac{x_i}{y_i+1}$ is maximized. Store this differences using priority queue to reuse calculations.

| cite | improve this answer | |
  • 1
    $\begingroup$ No evidence shows generally the best options can be obtained rounding up and down when $n>2$. For instance consider minimizing $1/y_1+1/y_2+400/y_3$ with $y_1+y_2+y_3=32$. Fractional solution is $(1.45\ldots,1.45\ldots,29.09\ldots)$, but the integer solution is $(2,2,28)$. $\endgroup$ – Willard Zhan Jan 17 '17 at 5:34
  • 1
    $\begingroup$ Thanks, @WillardZhan! So that proves that this answer does not give a correct algorithm (i.e., it does not yield a global minimum). $\endgroup$ – D.W. Jan 17 '17 at 5:40

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.