Kattis Problem 'Mali'

Question

I wrote a solution to the Mali problem on Kattis:

Given inputs a₁, a₂, a₃, …, a_n and b₁, b₂, b₃, …, b_n, determine n pairings (a_i, b_j) such that each number in the A sequence is used in exactly one pairing, each number in the B sequence is used in exactly one pairing, and the maximum of all sums a_i + b_j is minimal.

Input

The first line of input contains a single integer N (1 ≤ N ≤ 100000), the number of rounds.

The next N lines contain two integers A and B (1 ≤ A, B ≤ 100), the numbers given in that round.

Output

The output consists of N lines, one for each round. Each line should contain the smallest maximal sum for that round.

I'm fairly sure I can get the right answer 100% of the time, but the code exceeds the time limit of one second. I was wondering if you could help me optimize my code to help it run in time, or if you could explain why my code is inefficient.

#include <iostream>
#include <vector>

int main() {
    int x, c = 0, big = 0;
    std::cin >> x;
    std::vector<int> as, bs;
    for (int i = 0; i < x; i++) {
        bool founda = false, foundb = false;
        int a, b;
        std::cin >> a >> b;
        c++;
        if (c == 1) {
            as.push_back(a);
            bs.push_back(b);
        }
        else {
            for (int i = 0; i < c; i++) {
                if (as[i] < a || i == c-1) {
                    as.insert(as.begin()+i, a);
                    founda = true;
                }
                if (bs[i] < b || i == c-1) {
                    bs.insert(bs.begin()+i, b);
                    foundb = true;
                }
                if (founda == true && foundb == true) 
                    break;
            }
        }
        for (int i = 0; i < c; i++) {
            if (as[i] + bs[c-1-i] > big)
                big = as[i] + bs[c-1-i];
        }
        std::cout << big << std::endl;
    }
}

Answer 1

You are storing all of the A and B inputs in sorted vectors, basically doing an insertion sort. A few observations (two minor, one major):

1. The if (c == 1) special case should be eliminated.
2. Flag variables (founda and foundb) suck. You would be better off writing two separate for loops.

3. Each time you insert a value, all values beyond the insertion point need to be shifted over to make room for the insertion. That means that constructing as and bs takes O(N²) time altogether — which is unacceptable, since N can be very large.

   However, there are only 100 possible values of A and B. So, do a counting sort instead, building a histogram with 100 buckets. That would be a much more efficient way to represent the same information, using O(N) time and a fixed amount of space.