Problem:

Given a $$$2*N$$$ matrix contains of positive integers with value not greater than $$$10^6$$$. Given an integer $$$K$$$.

Chooses $$$K$$$ column(s) from the matrix, call $$$P$$$ is the sum of all of the top integers from chosen columns, call $$$Q$$$ is the sum of all of the bottom integers from the chosen columns.

Your task is to maximizes $$$P/Q$$$ and print $$$P$$$ and $$$Q$$$ out in its reduced fraction form.

Constraint: $$$1 \leq K \leq N \leq 5*10^4$$$

Time limit: 1s

Input:

• First line contains: $$$N$$$, $$$K$$$

• Next $$$N$$$ lines contain two integers, first integer belongs in the top row of the matrix, second integer belongs in the bottom row.

Output:

• Two space-separated integers $$$P$$$ and $$$Q$$$.

Example

3 2
3 1
1 2
1 1

2 1

Attempts:

It was from our school's training contest that I first saw it. I blindly submitted a greedy sort sol (ratio of $$$top/bot$$$) but got WA. Next I tried to make it TLE, $$$K$$$ iterations with everytime choose a col. that maximizes $$$(currentP + top)/(currentQ + bot)$$$ and it did get a TLE.

But after that I was stumped.

I aksed my coach for the solution code and let the explaination be an excercise but I couldn't figure it out.

Please help me understand the math/intuition behind the idea of the solution.

I apologize that I can't provide submit link.

Solution:

#include \
using namespace std;
const double EPS = 1e-12;
long long GCD(long long a, long long b) {
    return (b == 0) ? a : GCD(b, a%b);
}
void reduce(long long &p, long long &q) {
    long long d = GCD(p, q);
    p /= d; q /= d;
}
int main() {
    ios :: sync_with_stdio (0);
    cin.tie (0); cout.tie (0);
    int n, k;
    scanf("%d%d", &n, &k);
    vector a(n), b(n);
    for(int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]);
    long long p = -1, q = 1;
    double lo = 0, hi = 1000000;
    for(int i = 0; i < 100; ++i) {
        double mid = (lo+hi)/2;
        vector > val(n);
        for(int i = 0; i < n; ++i) val[i] = make_pair(a[i]-mid*b[i], i);
        sort(val.begin(), val.end());
        double sum = 0;
        for(int i = n-k; i < n; ++i) sum += val[i].first;
        if (sum > -EPS) {
            p = 0, q = 0;
            for(int i = n-k; i < n; ++i) {
                p += a[val[i].second]; q += b[val[i].second];
            }
            lo = mid;
        } else hi = mid;
    }
    reduce(p, q);
    cout << p << " " << q;
}