Three weeks ago, I went to the International Collegiate Programming Contest Europe Championship (ICPC EUC). If this is your first time hearing about it, it’s an algorithmic competition for university students, kind of like the International Olympiad in Informatics (IOI), but for teams of three. The first problem in the problem set is closely connected to a field of mathematics that I wouldn’t expect to appear in any ICPC contest: social choice theory (in particular, the well-known Condorcet Paradox).

The problem was as follows: You are given a list of pairs $(a, b)$; each of which means that candidate $a$ is preferred to candidate $b$ by more than half of the voters. Your task is to say if it is even possible (spoiler: it always is) and construct a set of ballots — ranking all candidates — such that the outcome of the election matches the before-given result.

I’ve managed to solve the problem and quickly moved on. I wouldn’t have written this post if not for Codeforces user jtnydv25 and his comment. My solution uses exactly $n(n-1)$ ballots for $n$ candidates (at most $\frac{n(n-1)}{2}$ pairs). It turns out that it can be solved quite easily with only $2n$ ballots, but the asymptotically optimal solution requires only $\mathcal{O}(n / \log n)$, which is very intriguing.

My on-site submission
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    cout << "YES\n";
    cout << n * (n - 1) << '\n';
    set<pair<int, int>> s;
    while (m--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        s.insert({a, b});
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            vector<int> v;
            for (int k = 0; k < n; k++) {
                if (k == i || k == j)
                    continue;
                v.push_back(k);
            }
            if (i > j)
                reverse(v.begin(), v.end());
            if (s.count({j, i})) {
                v.push_back(j);
                v.push_back(i);
            } else {
                v.push_back(i);
                v.push_back(j);
            }

            for (auto x : v)
                cout << x + 1 << ' ';
            cout << '\n';
        }
    }
}

Benq’s solution $\mathcal{O}(n)$#

As a reply to jtnydv25’s comment, you can find Benq’s description of a solution that requires only $2n$ ballots. He suggests dividing all pairs $(a, b)$ into classes based on the result of $(a + b) \bmod{n}$ and then processing each class of pairs independently, which is quite smart in comparison to my solution.

Erdős-Moser solution $\mathcal{O}(n / \log n)$#

This is remarkable $\mathcal{O}(n / \log n)$ bound is possible! I would’ve been shy to propose the problem if I realized it’s solved in 1964’s paper.
~ Alice Sayutina, problem setter

It turns out this problem was already solved by Paul Erdős and Leo Moser in a paper titled On the representation of directed graphs as unions of orderings. I won’t detail the article here, but I encourage you to go and read it. It’s only a couple of pages in which the authors prove not only that $\mathcal{O}(n / \log n)$ solution is possible but also that it’s asymptotically optimal.