G - Infinite Knapsack Editorial by en_translator
In this problem, you need to find the lower convex hull. For more details on lower hull and algorithms to find it, refer to Monotone Chain.
Instead of considering the limit, let us rephrase the problem as follows:
There are \(N\) kinds of items, the \(i\)-th of which of weight \(A_i\), volume \(B_i\), and value \(C_i\). You may choose non-negative real-valued number of each kind of item. Find the minimum \(\mathrm{max}\)(sum of weight, sum of volume) of the chosen items.
If the answer to the rephrased problem is \(\mathrm{ans}\), then the answer to the original problem coincides with \(\frac{1}{\mathrm{ans}}\).
Since the number of each kind of item can be non-negative real value, we may further rephrase to make the value of each kind of item exactly \(1\):
There are \(N\) kinds of items, the \(i\)-th of which of weight \(A'_i=\frac{A_i}{C_i}\), volume \(B'_i=\frac{B_i}{C_i}\), and value \(1\). You may choose non-negative real-valued number of each kind of item. Find the minimum \(\mathrm{max}\)(sum of weight, sum of volume) of the chosen items.
Let us plot each kind of item at coordinates \((A'_i,B'_i)\) on a two-dimensional plane. Then, we can show that we don’t need to choose points not contained in the lower hull of the plotted points:
Outline of proof
First, the $i$-th item doesn't need to be chosen if there exists $j$ such that $A'_i > A'_j$ and $B'_i > B'_j$. In other words, you need to choose a point if it has another on its lower left.
Next, we can say that we can regard a point contained in a segment connecting two plotted points as an item. This is because such point is represented by a linear combination of two segments where coefficients are non-negative and have a sum of $1$.
After all, if a vertex is not contained in the lower hull, there is another vertex or segment of the lower hull in its lower left, so it does not need to be chosen.
Moreover, by the same discussion, we can say that we don’t need to choose three or more kinds of points in the lower hull, and you don’t need to choose non-adjacent two vertices in the lower hull.
By these fact, we can answer the problem by finding the minimum value of \(\mathrm{max}(x,y)\) for each vertex and edge in the lower hull.
For vertices, we may inspect them exhaustively. For segments, we can find the minimum value of \(\mathrm{max}(x,y)\) in an \(\mathrm{O}(1)\) time because \(x-y\) is a linear function. For more details, please refer to the sample code.
Finding the convex hull costs \(\mathrm{O}(N\log N)\) time, and finding the minimum value of \(\mathrm{max}(x,y)\) costs \(\mathrm{O}(N)\) time, so the problem can be solved in a total of \(\mathrm{O}(N\log N)\) time.
posted:
last update: