You are given $$$n$$$ pairs of positive integers $$$(a_i, b_i)$$$. You are also given two positive integer constants $$$P$$$ and $$$Q$$$. The constraints are $$$n, a_i, b_i, P, Q \le 10^6$$$. You must choose $$$n$$$ non-negative real coefficients $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ so that all of the conditions hold:
- $$$\sum a_i x_i = a_1 x_1 + a_2 x_2 + a_3 x_3 + ... + a_n x_n \ge P$$$
- $$$\sum b_i x_i = b_1 x_1 + b_2 x_2 + b_3 x_3 + ... + b_n x_n \ge Q$$$
- The expression $$$S = \sum x_i = x_1 + x_2 + x_3 + ... + x_n$$$ is minimum.
What is the minimum value of $$$S$$$?
The limits are the usual 2 seconds and 256MB. I couldn't find an online version of this problem, only a plaintext version from some local archive. I'm guessing this is some kind of greedy problem where you only need to "choose" no more than two pairs, but so far I have no luck trying to prove my strategy (nor have I confirmed its correctness).
I have thought about simplifying down to the case of $$$n=2$$$ then hoping some algebra magic will take it all the way to every integer $$$n>2$$$. Again, I'm stuck on the transitioning part.
I would love some help from Codeforces!
This is called a linear program. I don’t know how familiar you are with linear programs, but for this particular one it looks like if you focus on its dual, you’ll have some 2D equations, which you can solve using Halfplane Intersection.
You intuition of ‘focusing on two variables’ is probably correct due to the analysis of the dual. If you want a ‘magic’ solution, focus only on pairs of $$$x_i, x_j$$$ for which points $$$(a_i, b_i)$$$ and ($$$a_j, b_j)$$$ are adjacent on the convex hull. But again, to get such intuitions, I suggest you learn about convex optimization and linear programming.