906. Hiring a Crew of k
You must hire exactly k of n workers. Worker i has a quality q[i] and a
minimum wage w[i]. Whatever crew you hire, two rules apply:
1. everyone in the crew is paid in proportion to their quality,
at one rate R rupees per unit of quality, the same R for all of them
2. nobody is paid below their own minimum wage: R * q[i] >= w[i]
The crew costs R times the total quality. Print the smallest possible cost as
an exact fraction in lowest terms.
``` (q 10, w 70) (q 20, w 50) (q 5, w 30), k = 2 -> 105 1 hire the second and third: R must be at least 50/20 and 30/5, so R = 6, and the cost is 6 * 25 = 105
(q 1, w 1), k = 1 -> 1 1
(q 3, w 4) (q 1, w 8) (q 10, w 2), k = 3 -> 112 1 ```
## What most people try first
Sorting by minimum wage and taking the k cheapest is wrong: a worker with a
tiny wage demand but a huge quality drags the total up, because the cost is a
rate times the SUM of qualities, not a sum of wages.
Sorting by quality and taking the k smallest is wrong for the mirror reason:
one worker with a low quality and an enormous wage demand forces a rate that
everyone else is then paid at.
Trying every crew is C(n, k) combinations. At n = 30 and k = 15 that is
155117520, and n here reaches 10^5.
## The derived key, which is the whole problem
Each worker demands R >= w[i] / q[i]. For a chosen crew the rate is forced:
R = max over the crew of ( w[i] / q[i] )
cost = R * (total quality of the crew)
So order the workers not by wage and not by quality but by the RATIO
w[i] / q[i]. Sweep them in increasing ratio. When worker j is the one being
considered, every worker before j has a ratio at most j's, so if the crew is
drawn from the first j workers and includes j, the rate is exactly
w[j] / q[j]. With the rate pinned, the only thing left to minimise is the
total quality, so keep the k SMALLEST qualities seen so far.
sort workers by w/q ascending
h = empty max-heap of qualities, s = 0, best = infinity
for each worker (q, w) in that order:
push q onto h; s = s + q
if size(h) > k: s = s - pop the largest quality
if size(h) == k: best = min(best, (s * w) / q)
print best as a reduced fraction
A max-heap of qualities, so that the WORST member of the current crew is the
one evicted. That is the same shape as #869 keeping the k nearest points, with
a key that had to be worked out rather than read off.
## Why it is correct
Every optimal crew has some member with the largest ratio; call it j. That
crew is a subset of the first j workers in ratio order, it contains j, and
its cost is (w[j] / q[j]) * (its total quality). The sweep considers exactly
one candidate for each possible j, namely the k smallest qualities among the
first j workers, which minimises the total quality over all such crews. So
the best crew for each j is examined, and the optimum is among them.
The subtle point is that the heap's crew might not contain worker j itself. It
cannot be better than the true best crew for j, and it is a legal crew drawn
from the first j workers whose rate is at most w[j] / q[j], so the value
computed is an upper bound on some achievable cost and a lower bound is never
reported. It therefore never produces an answer below the true minimum.
## Comparing without floating point
Never compare w1 / q1 against w2 / q2 as doubles here. Cross-multiply:
w1 / q1 < w2 / q2 is w1 * q2 < w2 * q1
with all four values positive. Those products reach 10^4 * 10^4 = 10^8, well
inside 32 bits, and the comparison is exact. Two workers whose ratios agree
only in the eleventh decimal place are ordered correctly; with doubles they may
not be.
The answer is (s * w) / q. Reduce by the greatest common divisor of s * w
and q and print the two parts.
## Overflow
s is a total of at most 10^5 qualities of at most 10^4, so s <= 10^9, and
s * w reaches 10^13. That is past 32 bits, so the numerator needs 64 bits.
Comparing two candidate fractions a1/b1 and a2/b2 by cross-multiplying gives
10^13 * 10^4 = 10^17, which still fits in a signed 64-bit integer with room to
spare, since that holds up to about 9.2 * 10^18.
## Related problems
Problem #807 also maximises a ratio of sums, and it does so by binary searching the ratio and testing it, because there the denominator is chosen too. Here one worker's ratio PINS the rate for everyone, which is what makes a single sorted sweep enough and a search unnecessary.
## Cost
Time O(n log n). Space O(n).
Constraints - `1 ≤ k ≤ n ≤ 100000` - `1 ≤ q[i] ≤ 10000` - `1 ≤ w[i] ≤ 10000`
Input
The first line contains two integers n and k.
Each of the next n lines contains two integers: the quality and the minimum wage of one worker.
Output
Print two integers on one line, separated by a single space: the numerator and the denominator of the least cost, in lowest terms with a positive denominator. Print 105 1 rather than 105 when the cost is a whole number.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.