GIven this problem:
Given $$$n$$$ integer pairs $$$a_i$$$, $$$b_i$$$, pick $$$k$$$ of them so that $$$\frac{\sum_{}^{}a_i}{\sum_{}^{}b_i}$$$ is maximized, output the maximum value.
Constraints:
$$$1 \le k \le n \le 200000$$$
$$$1 \le a_i, b_i \le 10^{6}$$$
I have this scuffed greedy algorithm which does the following:
Assume the result is $$$\ge x$$$, then let $$$u_i = a_i - xb_i$$$
Greedily pick the largest $$$k$$$ values of $$$u_i$$$.
Update $$$x$$$ to the new optimal value, if the new value is not better then stop.
After a lot of random tests, the worst case only made it perform $$$7$$$ iterations.
Are there any tests that makes it TLE, or at least run a lot more than $$$7$$$ iterations? If not, is there a proof? What is the runtime in the worst case?
Actually, this algorithm is known as Dinkelbach algorithm. If you invented it by yourself you must be a genius.
I think I can't prove it, but there are already some proof on the Internet. According to some informations, the worst-case number of iterations of the Dinkelbach algorithm is $$$O(\log(n C D)) \leq O(\log(n M))$$$, where $$$M = \max(C, D)$$$, where $$$C=\max(\max|c_i|,1),D=\max(\max|d_i|,1)$$$. (In this article, the pairs are indicated as $$$c_i, d_i$$$.)
We assume that the Dinkelbach algorithm terminates at the $$$k$$$-th iteration. We can obtain a sequence of parameters $$$(L_1, L_2, \dots, L_k)$$$ and a 0-1 vector $$$(x_1, x_2, \dots, x_k)$$$. The convexity of $$$z(L)$$$ implies the following inequalities:
Since the function $$$z(L)$$$ is strictly decreasing, it is also easy to see that:
Lemma 1: If $$$0 \geq z(L_r) \gt -\frac{1}{n D}$$$ for $$$2 \leq r \leq k$$$, then $$$z(L_r) = 0$$$.
Proof: Since $$$L_r = \frac{c x_{r-1}}{d x_{r-1}}$$$, we have:
Suppose $$$z(L_r) \lt 0$$$. Then $$$(c x_r d x_{r-1} - c x_{r-1} d x_r) \leq -1$$$. Since the inequality $$$0 \lt d x_{r-1} \leq n D$$$ holds, it follows that $$$z(L_r) \leq -\frac{1}{n D}$$$. This is a contradiction!
The above lemma follows from the integrality of the weight vectors $$$c$$$ and $$$d$$$. This lemma implies that if $$$z(L_r) \geq -\frac{1}{n D}$$$, then $$$z(L_r) = 0$$$, and thus the algorithm terminates at the $$$r$$$-th iteration.
Lemma 2: If $$$0 \leq c x_r + n C d x_r \lt 1$$$, then $$$z\left(\frac{c x_r}{d x_r}\right) = 0$$$.
Proof: Since $$$c x_r + n C d x_r$$$ is an integer, if $$$0 \leq c x_r + n C d x_r \lt 1$$$, then $$$c x_r + n C d x_r = 0$$$, and $$$\frac{c x_r}{d x_r} = -n C$$$. Since the optimal value $$$L^* \geq -n C$$$, $$$x_r$$$ is the optimal solution to the fractional programming problem, and $$$L^* = \frac{c x_r}{d x_r} = -n C$$$. Thus, it is clear that $$$z\left(\frac{c x_r}{d x_r}\right) = z(L^*) = 0$$$.
The above lemma proves that if $$$c x_r + n C d x_r \lt 1$$$, the algorithm terminates at the $$$r$$$-th or $$$(r+1)$$$-th iteration.
Now, we present the main lemma:
Lemma 3: For $$$1 \leq r \leq k-1$$$, either $$$|z(L_{r+1})| \leq \frac{1}{2} |z(L_r)|$$$ or $$$c x_{r+1} + n C d x_{r+1} \leq \frac{1}{2} (c x_r + n C d x_r)$$$ holds.
Proof: If $$$L_r + n C \leq 0$$$, then $$$L_r = L^* = -n C$$$, which implies $$$z(L_r) = 0$$$, and thus $$$\frac{1}{2} z(L_{r+1}) = 0$$$.
Now assume $$$L_r + n C \gt 0$$$. There are two cases:
Case (i): First, consider $$$z(L_{r+1}) (L_r + n C) \leq \frac{z(L_r)}{2} (L_{r+1} + n C)$$$. This case is illustrated in Figure 2. In this figure, the line $$$z = c x_r - L d x_r$$$ is denoted as $$$l_r$$$. We use the notation from Figure 2. Let $$$M$$$ be the midpoint of the line segment $$$PR$$$. Then the coordinates of point $$$M$$$ are $$$\left( L_{r+1}, \frac{z(L_r) (L_{r+1} + n C)}{2 (L_r + n C)} \right)$$$. Thus, the condition $$$z(L_{r+1}) (L_r + n C) \leq \frac{z(L_r)}{2} (L_{r+1} + n C)$$$ implies that the point $$$Q = (L_{r+1}, z(L_{r+1}))$$$ lies on the line segment $$$MR$$$. Under this condition, we prove the inequality $$$c x_{r+1} + n C d x_{r+1} \leq \frac{1}{2} (c x_r + n C d x_r)$$$. This means that the line $$$l_{r+1}$$$ intersects the line segment $$$MR$$$, and $$$l_{r+1}$$$ also intersects the line segment $$$M'R'$$$, where $$$M'$$$ is the midpoint of the line segment $$$P'R'$$$. Now we prove this inequality:
Since $$$L_r \gt L_{r+1}$$$, the inequality $$$c x_{r+1} + n C d x_{r+1} \leq \frac{1}{2} (c x_r + n C d x_r)$$$ is proved.
Case (ii): Next, consider $$$z(L_{r+1}) (L_r + n C) \gt \frac{z(L_r)}{2} (L_{r+1} + n C)$$$:
Note that neither $$$|z(L)|$$$ nor $$$c x + n C d x$$$ increases during the process.
In the first iteration, the value of $$$|z(L)|$$$ is at most $$$2 n^2 C D$$$. By Lemma 1, it is clear that if there are $$$O(\log(2 n^2 C D / \frac{1}{n D})) \leq O(\log(n C D))$$$ iterations, each reducing $$$z(L)$$$ by at least 50%, then the optimal solution is obtained. Similarly, Lemma 2 implies that the number of iterations reducing $$$c x + n C d x$$$ by 50% is $$$O(\log(2 n^2 C D)) \leq O(\log(n C D))$$$ in the worst case. Lemma 3 proves that each iteration reduces either $$$|z(L)|$$$ or $$$c x + n C d x$$$ by 50%. Therefore, the total number of iterations is bounded by $$$O(\log(n C D))$$$.
Theorem 4: The worst-case number of iterations of the Dinkelbach algorithm is $$$O(\log(n C D)) \leq O(\log(n M))$$$, where $$$M = \max(C, D)$$$.
The above theorem proves that the worst-case number of iterations of the Dinkelbach algorithm is $$$O(\log(n C D))$$$. This implies that if there exists a strongly polynomial algorithm for $$$Q(L)$$$, the Dinkelbach algorithm can solve the fractional programming problem in polynomial time. However, after solving the subproblem with a polynomial algorithm, we need to estimate the input size of the coefficients of the target function $$$Q(L)$$$. In the next section, we will discuss this by analyzing the optimal ratio spanning tree and fractional allocation problems.
Source: https://blog.csdn.net/pi9nc/article/details/12425723
I am only responsible for bringing these contents over, unfortunately I do not have the ability to verify the correctness of the content.
That's a cool algorithm.
Basically, you have $$$\binom{n}{k}$$$ options for the set of pairs you choose, each set $$$S$$$ will give some fraction $$$\frac{A_S}{B_S}$$$, which you then transform into a function $$$f_S(x) = A_S - B_S \cdot x$$$ which is linear. Then you construct a lower envelope (convex hull) of those lines, and then apply iteration to find a 0 of that lower envelope.
It can actually be shown that the lower envelope has at most $$$O(n^2)$$$ segments (maybe even some better bound is possible, but I don't know how), and it can be constructed in $$$O(n^2)$$$ time, but it is not really relevant to the iteration approach.
The iteration works as follows: we take $$$x_0 = 0$$$, then for $$$x_i$$$ we find the largest $$$f_S(x_i)$$$ and find $$$x_{i+1}$$$ as a 0 of $$$f_S(x)$$$. Let's denote the function we found for $$$x_i$$$ as $$$A_i - B_i \cdot x$$$, and $$$y_i = A_i - B_i \cdot x_i$$$. By the definition of $$$x_{i+1}$$$, $$$A_i - B_i \cdot x_{i+1} = 0$$$. Therefore, $$$y_i = B_i \cdot (x_{i+1} - x_i)$$$. $$$y_i$$$ is the largest value of our linear functions at $$$x_i$$$, so $$$A_{i+1} - B_{i+1} \cdot x_i \le y_i$$$. $$$y_{i+1} = A_{i+1} - B_{i+1} \cdot x_{i+1}$$$, which means $$$y_{i+1} + B_{i+1} \cdot (x_{i+1} - x_i) \le y_i$$$ and then $$$y_{i+1} \le \left( 1 - \frac{B_{i+1}}{B_i} \right) y_i$$$.
From this we can conclude that $$$B_{i+1} \le \frac{1}{2} B_i$$$ or $$$y_{i+1} \le \frac{1}{2} y_i$$$ (or both). $$$y_{i+1} = A_{i+1} - B_{i+1} \cdot x_{i+1} = A_{i+1} - \frac{B_{i+1}}{B_i} A_{i}$$$. $$$B_i$$$ are positive integers, $$$y_i$$$ are non-negative rational numbers with both numerators and denominators bounded by $$$(\max A_i) \cdot (\max B_i)$$$. Therefore, after $$$O(\log ((\max A_i) \cdot (\max B_i)))$$$ iterations we must have $$$y_i = 0$$$.
By the way I think the frac-programming of the binary version is better than the Dinkelbach version. So we should stop learning useless algorithms, go and solve some problems, learn how to use binary search.
What's a frac-programming?
The problem described by the poster in the CNOI community is a template question for "01 分数规划", but I don't know what the English for this thing is, and there is no reasonable dictionary for me to use. So I used the English title of the Chinese OI wiki section.
Well, you could have explained the concept.
Is it the idea that when we want to find the maximum of some fraction (like the weighted average of something), we want to apply binary search, multiply by the denominator and then consider $$$\sum (p_i - \lambda q_i)$$$?
Binary search is just a joke (first mentioned by you several years ago), it should actually be a binary answer to the lambda you mentioned, so that's it.
The Chinese OI Wiki website about this kind of problems is there.
I'm afraid that even a translator may not be able to handle the formulas on the page well, so it's better to ask an AI to translate.
Linear-fractional_programming
I guess it's kind of an application of Newton's iteration to a piecewise linear convex function. I am not proficient in this area, so I can't tell you if it's insightful or not.
Also regarding your code: you don't need to sort the values to find the sum of $$$k$$$ maximums. Use nth_element, it's $$$O(n)$$$.
I just wanted to remark that $$$O(n)$$$ is only guaranteed in the average case (page 905); the worst case of gcc's implementation is $$$O(n\log n)$$$. It uses the quickselect and heapselect combination mentioned on the wiki article for Introselect.
Of course, it is still a better choice over sorting (where possible) runtime-wise in most cases.