Module assignment: leaderboard analysis

Why this assignment

This assignment combines every idea in the module into one program. You will write a merge sort, count inversions while you sort, and answer many questions with binary search. Each part is small on its own. The skill being tested is putting them together so that the whole program is correct, fast enough for large inputs, and easy to read.

The work follows a real pattern. A running club records one score per race. The coach wants three reports from the same data: the scores in order, a measure of how often a faster result came after a slower one, and a quick way to see how many scores beat a given time. You will build a program that prints all three.

Plan on about one to two hours. Start with the sample input, get the first report right, and then add the other two. Test each part before you move to the next.

The brief

The program reads a list of scores in the order they were recorded. A score is a whole number, which can be negative, because some teams use a penalty system. The program then reads a list of queries. Each query is a value x, and the coach wants to know how many recorded scores are strictly greater than x.

The program prints three reports, in this order.

1. Sorted scores. All the scores from smallest to largest, on one line, separated by single spaces. You must sort them with your own merge sort. Do not call std::sort, because the assignment is about the algorithm.
2. Upset count. One number: how many pairs of scores are out of order. A pair is two positions i and j with i < j and score[i] > score[j]. The earlier score is higher than the later one. Count the upsets while you sort, using the merge step from lesson 5.
3. Query answers. One line per query. For each query x, print how many scores are strictly greater than x. Use binary search on the sorted scores. A scan of all scores for each query is too slow for large inputs.

Input and output format

The input has this layout. The first line holds n, the number of scores. The second line holds the n scores, separated by spaces. The third line holds q, the number of queries. The next q lines each hold one query value.

The output has 1 + 1 + q lines. The first line is the sorted scores. The second line is the upset count. The next q lines are the answers to the queries, in the same order as the input.

Here is a sample. Type it into the Input box of your program, or into a file, to check your work.

5
70 40 90 40 60
3
40
65
100

The correct output is:

40 40 60 70 90
5
3
2
0

Check each line by hand before you write code. The sorted line is the five scores in increasing order. The upset count is 5, from the pairs 70 with 40, 70 with 40 again, 70 with 60, 90 with 40, and 90 with 60. The three queries ask how many scores are above 40, above 65 and above 100. The answers are 3 (60, 70 and 90), 2 (70 and 90), and 0.

Notice that the two 40 values do not form an upset with each other. Equal values are not out of order, so the count only uses strict >. Also notice that the query 40 asks for scores strictly greater than 40, so the two copies of 40 are not counted.

Input limits

Your program must handle the following limits. The coach's real data is bigger than the sample, and a slow program fails the club's nightly report.

• 1 <= n <= 100000
• 0 <= q <= 100000, and q may be 0, in which case there are no query lines.
• Each score and each query value is between -1000000000 and 1000000000.

Use the long long type for the scores and for the upset count. The upset count for 100000 scores can be near five billion, which is too big for an int. The score values fit in an int, but using long long everywhere avoids mistakes when you subtract or compare them.

Requirements checklist

Tick each item when you have tested it. Use this list as your own test plan. Each item is something the grader checks.

• The program reads n, then n scores, then q, then q queries, in that order.
• The scores are sorted with a merge sort that you wrote, not std::sort.
• The sorted scores are printed on one line, separated by single spaces, with a newline at the end.
• The upset count is computed with divide and conquer during the merge, not by checking every pair.
• The upset count uses long long, and it does not count equal values as upsets.
• Each query is answered with binary search on the sorted array, in O(log n) time.
• Each query counts values strictly greater than x, not greater than or equal to x.
• The program handles n = 1, where there are no pairs and the upset count is 0.
• The program handles all scores being equal, where the upset count is 0 and every query is answered from one value.
• The program handles queries smaller than every score, and queries bigger than every score.
• The program handles q = 0, printing the first two lines and nothing more.
• The program prints exactly the layout described above, with no extra text or labels.
• A comment near the top of the program states the time complexity, which should be O(n log n) for the sort and count plus O(q log n) for the queries.

Grading rubric

The grader scores the work in three bands. Read the descriptions carefully, because the bands describe what a program does, not how long the code is.

60 percent. The sorted scores are correct on the sample and on simple inputs, and the program compiles and runs. The upset count is either missing or computed by checking every pair. The queries are answered by a linear scan, or they are answered wrongly for some values. The program may be correct on small inputs and too slow on large ones.

80 percent. The sorted scores, the upset count and the query answers are all correct on the sample and on random tests with distinct and repeated values. The upset count uses divide and conquer, and the queries use binary search. Some edge cases are wrong, such as counting equal values as upsets, using greater than or equal for the queries, or failing when q is 0. The program may overflow on large upset counts.

100 percent. Every requirement in the checklist is met, and the output matches a brute-force program on many random tests, including n = 1, duplicates, and queries below the smallest and above the largest score. The program runs well within a second on 100000 scores and 100000 queries. The code is clear, uses names that describe the values, and has a comment that explains the complexity. A reviewer could explain every line without running the program.

Work in this order

Doing the parts in order keeps each bug small. Here is a plan that works.

1. Read the input into a vector<long long> and print it back. Check that the sample reads correctly.
2. Write the merge sort, first without counting. Print the sorted scores and compare them with the sample line.
3. Add the upset count to the merge step. Print the count and compare it with the sample value of 5.
4. Write the binary search that finds the first score greater than x. Test it on the sample queries, and check that 40 gives 3, 65 gives 2 and 100 gives 0.
5. Put the three reports together, and test the full sample.
6. Write a brute-force program in any language you like. It should check every pair for upsets, sort with a library call, and answer each query with a loop. Generate small random inputs, run both programs, and compare the outputs.
7. Time the program on the largest input you can generate, with 100000 scores and 100000 queries.

Hints

Use these hints only after you have tried each step yourself. They show the structure, not the code.

Reference solution

Compare your program with this solution only after you have a working version. It is short on purpose. The merge sort and the count are the same code as in lesson 5, extended to sort the scores as well. The queries use the upper bound pattern from lesson 1.

#include <iostream>
#include <vector>
using namespace std;
 
// Merge sort that also counts upsets (pairs i < j with a[i] > a[j]).
// Time O(n log n). Extra memory O(n). The array a[lo..hi] ends up sorted.
long long sortAndCount(vector<long long>& a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long long left = sortAndCount(a, lo, mid);
    long long right = sortAndCount(a, mid + 1, hi);
    long long cross = 0;
    vector<long long> tmp;
    tmp.reserve(hi - lo + 1);
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) {
            tmp.push_back(a[i++]);
        } else {
            tmp.push_back(a[j++]);
            cross += mid - i + 1;      // every left value from i to mid is bigger
        }
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= hi) tmp.push_back(a[j++]);
    for (int k = 0; k < (int)tmp.size(); k++) a[lo + k] = tmp[k];
    return left + right + cross;
}
 
// First index whose value is bigger than x. Time O(log n).
int firstBigger(const vector<long long>& a, long long x) {
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
 
int main() {
    // Total time: O(n log n) to sort and count, plus O(q log n) for the queries.
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    long long upsets = (n > 0) ? sortAndCount(a, 0, n - 1) : 0;
    for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
    cout << upsets << "\n";
    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        long long x;
        cin >> x;
        cout << n - firstBigger(a, x) << "\n";
    }
    return 0;
}

Testing your work

Test in this order, and keep a record of every input that fails.

• The sample, which must match exactly.
• 1 followed by one score and 0 queries. The output has the score, then 0, then nothing.
• Five equal scores, such as 5 / 7 7 7 7 7 / 2 / 7 / 6. The upset count is 0, the sorted line is five 7s, the query 7 gives 0, and the query 6 gives 5.
• A reversed list of scores, such as 4 / 4 3 2 1. The upset count is 6, which is every pair.
• A list with negative scores, such as 3 / -5 0 -5 / 1 / -6. The sorted line is -5 -5 0, the upset count is 1 (the 0 before the second -5), and the query -6 gives 3.
• The largest input, with 100000 scores and 100000 queries. The program should finish quickly.

When a test fails, print the internal state. For the sort, print the array after each merge. For the upset count, print the cross value at each merge and compare it with the brute-force count for the same two halves. Most bugs in this assignment come from one of three places: the merge tie rule, the half-open range in the binary search, or an int where a long long was needed.

Stretch extension

When the core program is correct and fast, try one extension. The coach also wants to know the median score. Answer that by printing the element at the middle of the sorted array, using the index n / 2 for an odd count and the average of the two middle values for an even count. The average may be a fraction, so print it with one decimal place, or use integer arithmetic and print the two values separately. Explain your choice in a comment. Do not call a library median function, because the point of the extension is to use the sorted array you already have.

What the assignment tests

The sorted report tests the merge sort you wrote in lesson 2. The upset report tests the counting change from lesson 5, which is the most demanding part because it needs both the right count and the right type. The query report tests the binary search from lesson 1, in its half-open form. The edge cases test whether you understood the rules for equal values, empty input and negative numbers, which were the subjects of each lesson's common mistakes section.

A correct program does not need to be long. Typical solutions are under 60 lines of code. The best programs are the ones where each part can be checked on its own, and where the comments explain the complexity and the reason for each choice.