Superbull

This is my solution to Superbull. We need to find the maximum spanning tree of the graph formed by the teams, where the weight of an edge between two teams is the points scored if the two teams play against each other.

Solution 1 - Kruskal's

We can use Kruskal's to find the maximum spanning tree of the graph, which requires finding all the edges and sorting them in decreasing order of edge weight. Connecting two vertices of the graph will eliminate $1$ team, and we can stop after we have eliminated $n - 1$ teams.

Time Complexity: $\mathcal{O}(N^2 \log{N})$

1// USACO 2015 February Silver Problem 3
2#include <iostream>
3#include <cstdio>
4#include <algorithm>
5#include <vector>
6using namespace std;
7void init(int n);
8bool unite(int a, int b);
9
10const int MAX_N = 2000;
11int parent[MAX_N];
12int comp_size[MAX_N];
13struct Edge
14{
15    int from, to, weight;
16};
17int main()
18{
19    freopen("superbull.in", "r", stdin);
20    freopen("superbull.out", "w", stdout);
21    int n;
22    cin >> n;
23    int ids[MAX_N];
24    for (int i = 0; i < n; i++)
25    {
26        cin >> ids[i];
27    }
28    vector<Edge> edges;
29    for (int i = 0; i < n; i++)
30    {
31        for (int j = i + 1; j < n; j++)
32        {
33            edges.push_back({i, j, ids[i] ^ ids[j]});
34        }
35    }
36    init(n);
37    // sort edges in decreasing order of weight
38    sort(edges.begin(), edges.end(), [](Edge a, Edge b){
39        return a.weight > b.weight;
40    });
41    int eliminated = 0;
42    long long ans = 0;
43    for (Edge e : edges)
44    {
45        if (unite(e.from, e.to))
46        {
47            eliminated++;
48            ans += e.weight;
49            // if all but 1 team has been eliminated
50            if (eliminated == n - 1)
51            {
52                cout << ans << endl;
53                return 0;
54            }
55        }
56    }
57    return 0;
58}
59
60void init(int n)
61{
62    for (int i = 0; i < n; i++)
63    {
64        parent[i] = i;
65        comp_size[i] = 1;
66    }
67}
68
69int find(int a)
70{
71    if (a == parent[a])
72    {
73        return a;
74    }
75    return parent[a] = find(parent[a]);
76}
77
78bool unite(int a, int b)
79{
80    int roota = find(a), rootb = find(b);
81    if (roota == rootb)
82    {
83        return false;
84    }
85    if (comp_size[roota] > comp_size[rootb])
86    {
87        swap(roota, rootb);
88    }
89    parent[roota] = rootb;
90    comp_size[rootb] += comp_size[roota];
91    return true;
92}

1// USACO 2015 February Silver Problem 3
2#include <iostream>
3#include <cstdio>
4#include <algorithm>
5#include <vector>
6using namespace std;
7void init(int n);
8bool unite(int a, int b);
9
10const int MAX_N = 2000;
11int parent[MAX_N];
12int comp_size[MAX_N];
13struct Edge
14{
15    int from, to, weight;
16};
17int main()
18{
19    freopen("superbull.in", "r", stdin);
20    freopen("superbull.out", "w", stdout);
21    int n;
22    cin >> n;
23    int ids[MAX_N];
24    for (int i = 0; i < n; i++)
25    {
26        cin >> ids[i];
27    }
28    vector<Edge> edges;
29    for (int i = 0; i < n; i++)
30    {
31        for (int j = i + 1; j < n; j++)
32        {
33            edges.push_back({i, j, ids[i] ^ ids[j]});
34        }
35    }
36    init(n);
37    // sort edges in decreasing order of weight
38    sort(edges.begin(), edges.end(), [](Edge a, Edge b){
39        return a.weight > b.weight;
40    });
41    int eliminated = 0;
42    long long ans = 0;
43    for (Edge e : edges)
44    {
45        if (unite(e.from, e.to))
46        {
47            eliminated++;
48            ans += e.weight;
49            // if all but 1 team has been eliminated
50            if (eliminated == n - 1)
51            {
52                cout << ans << endl;
53                return 0;
54            }
55        }
56    }
57    return 0;
58}
59
60void init(int n)
61{
62    for (int i = 0; i < n; i++)
63    {
64        parent[i] = i;
65        comp_size[i] = 1;
66    }
67}
68
69int find(int a)
70{
71    if (a == parent[a])
72    {
73        return a;
74    }
75    return parent[a] = find(parent[a]);
76}
77
78bool unite(int a, int b)
79{
80    int roota = find(a), rootb = find(b);
81    if (roota == rootb)
82    {
83        return false;
84    }
85    if (comp_size[roota] > comp_size[rootb])
86    {
87        swap(roota, rootb);
88    }
89    parent[roota] = rootb;
90    comp_size[rootb] += comp_size[roota];
91    return true;
92}

Solution 2 - Prim's

Since the graph is dense, it is faster to use $N^2$ Prim's. For each of the $n$ iterations, we find the farthest unselected node from the current spanning tree and add it to the graph. Then, we update the distances of all the other nodes accordingly.

Time Complexity: $\mathcal{O}(N^2)$

1// USACO 2015 February Silver Problem 3 (using Prim's)
2#include <iostream>
3#include <cstdio>
4using namespace std;
5
6const int MAX_N = 2000;
7int main()
8{
9    freopen("superbull.in", "r", stdin);
10    freopen("superbull.out", "w", stdout);
11    int n;
12    cin >> n;
13    int ids[MAX_N];
14    for (int i = 0; i < n; i++)
15    {
16        cin >> ids[i];
17    }
18    // n^2 prim's
19    bool selected[MAX_N]{};
20    int dist[MAX_N]{};
21    long long ans = 0;
22    for (int i = 0; i < n; i++)
23    {
24        // the farthest node from the spanning tree
25        int curr_vertex = -1;
26        for (int j = 0; j < n; j++)
27        {
28            if (!selected[j] && (curr_vertex == -1 || dist[j] > dist[curr_vertex]))
29            {
30                curr_vertex = j;
31            }
32        }
33        selected[curr_vertex] = true;
34        ans += dist[curr_vertex];
35        for (int to = 0; to < n; to++)
36        {
37            // since curr_vertex was added to the tree
38            // update all other distances accordingly
39            dist[to] = max(dist[to], ids[to] ^ ids[curr_vertex]);
40        }
41    }
42    cout << ans << endl;
43    return 0;
44}

1// USACO 2015 February Silver Problem 3 (using Prim's)
2#include <iostream>
3#include <cstdio>
4using namespace std;
5
6const int MAX_N = 2000;
7int main()
8{
9    freopen("superbull.in", "r", stdin);
10    freopen("superbull.out", "w", stdout);
11    int n;
12    cin >> n;
13    int ids[MAX_N];
14    for (int i = 0; i < n; i++)
15    {
16        cin >> ids[i];
17    }
18    // n^2 prim's
19    bool selected[MAX_N]{};
20    int dist[MAX_N]{};
21    long long ans = 0;
22    for (int i = 0; i < n; i++)
23    {
24        // the farthest node from the spanning tree
25        int curr_vertex = -1;
26        for (int j = 0; j < n; j++)
27        {
28            if (!selected[j] && (curr_vertex == -1 || dist[j] > dist[curr_vertex]))
29            {
30                curr_vertex = j;
31            }
32        }
33        selected[curr_vertex] = true;
34        ans += dist[curr_vertex];
35        for (int to = 0; to < n; to++)
36        {
37            // since curr_vertex was added to the tree
38            // update all other distances accordingly
39            dist[to] = max(dist[to], ids[to] ^ ids[curr_vertex]);
40        }
41    }
42    cout << ans << endl;
43    return 0;
44}