F. Friendly Rivalry

Updated May 21, 2026

Track ICPC

Year 2024

Statement Text + PDF

TeXC++Statement textStatement PDF

Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

Time limit 2 seconds

The leaders of the International Coalition for Planetary Change (ICPC), a non-profit fighting for envi- ronmental awareness, are worried that their regional chapters are not doing enough to make a real impact on climate change. Inspired by the latest studies that competition is one of the best motivators, they have decided to start a competition between their chapters. At the same time, the ICPC does not want to slow the spread of ideas. To encourage chapters to share effective climate change methods, the ICPC has decided to assign their 2n chapters into two teams, the green team and the blue team. For balance, each team should consist of exactly n chapters. To ensure the teams are not getting in each other’s way, the ICPC wants the two teams to be as far apart as possible. Specifically, the Euclidean distance between the closest pair of chapters belonging to different teams should be as large as possible. Help the ICPC set up the teams according to these rules.

Input

The first line contains an integer n (1 ≤ n ≤ 500), the size of each team. Chapters are numbered from 1 to 2n. Each of the remaining 2n lines contains two integers xi and yi (−109 ≤ xi , yi ≤ 109 ), the Cartesian coordinates of the location of the ith chapter. All chapters are at distinct locations.

Output

Output n + 1 numbers. The first number is the distance between the two closest chapters belonging to different teams. The next n numbers are the chapters belonging to the blue team. If there are multiple ways to divide the teams with the same minimal distance, output any of them. The distance should have an absolute or relative error of at most 10−6 .

Sample Tests

Sample 1

Sample Input

Sample Output

1.000000
1
2

Sample 2

Sample Input

Sample Output

2.236068
4
2

Sample 3

Sample Input

Sample Output

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

Fix a candidate distance $D$. If two chapters are closer than $D$, they cannot be on different teams. Therefore every pair of chapters with distance $< D$ must receive the same color.
Build a graph whose vertices are the chapters and whose edges connect pairs at distance $< D$. Then every connected component of this graph must be monochromatic.
So checking feasibility for $D$ becomes: can we choose some connected components whose total size is exactly $n$? This is a subset-sum problem on component sizes.
As $D$ increases, more edges appear, connected components only merge, and feasibility can only become harder. Thus feasibility is monotone, so binary search works.
The optimal answer is one of the pairwise distances between chapters, because the graph changes only when $D$ passes such a distance.

Algorithm

Let $N=2n$. Compute all $\binom{N}{2}$ squared distances and sort them.
For a candidate squared distance $X$:
1. Build a DSU on the $N$ chapters.
2. Unite every pair whose squared distance is $< X$.
3. Extract the connected-component sizes.
4. Run subset sum on these sizes and check whether sum $n$ is reachable.
5. Because feasibility is monotone, binary search the sorted distinct squared distances and find the largest one that is feasible.
6. Run the same DSU once more for the optimal threshold and rebuild the subset-sum DP with parent information. Backtrack to choose which components form the blue team.
7. Output $\sqrt{X}$ and all chapter indices belonging to the blue team.
Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

For a fixed distance $D$, a team assignment is valid with minimum cross-team distance at least $D$ if and only if every connected component of the graph on edges of length $< D$ is monochromatic.

Proof.

If two chapters are adjacent in that graph, their distance is $< D$, so they cannot be on different teams. Hence adjacent vertices must have the same color, and therefore every connected component must be monochromatic.

Conversely, if every connected component is monochromatic, then any blue-green pair lies in different connected components, so there is no graph edge between them. Hence their distance is not $< D$, i.e. it is at least $D$. □

Lemma 2.

For a fixed distance $D$, there exists a valid assignment if and only if some subset of connected components has total size exactly $n$.

Proof.

By Lemma 1, each connected component must be entirely blue or entirely green. Therefore choosing a valid assignment is exactly choosing which components are blue. Since the blue team must contain exactly $n$ chapters, feasibility is equivalent to selecting component sizes that sum to $n$. □

Lemma 3.

If a distance $D$ is feasible, then every smaller distance is also feasible.

Proof.

When we decrease $D$, the graph keeps only a subset of the previous edges. Connected components can only split, never merge. Any component selection that worked before can be refined by keeping the same color on each new smaller component, so feasibility cannot be lost when $D$ decreases. □

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

By Lemma 2, the feasibility test used by the algorithm is correct. By Lemma 3, this feasibility predicate is monotone, so binary search finds the largest feasible distance among all candidate pairwise distances. Since the graph changes only when $D$ crosses an existing pairwise distance, this largest feasible candidate is exactly the optimum.

Finally, the reconstruction DP chooses a subset of connected components of total size $n$, which by Lemma 2 yields a valid optimal team assignment. Therefore the algorithm outputs both the optimal distance and a corresponding blue team. □

Complexity Analysis

Let $N=2n \le 1000$ and $M=\binom{N}{2} = O(N^2)$.
- Building and sorting all distances costs $O(N^2 \log N)$.
- One feasibility test runs DSU over all edges and one subset-sum over at most $N$ components, so it costs $O(N^2 + Nn)$.
- We perform $O(\log N^2)=O(\log N)$ such tests in the binary search.
- Overall the running time is $O(N^2 \log N + (N^2 + Nn)\log N)$, and the memory usage is $O(N^2)$ for the edge list.
Implementation Notes
- Compare squared distances, not floating-point distances, during the entire search. Take the square root only for the final output.
- The threshold uses ``strictly less than'': edges of length exactly $D$ are allowed to be cross-team, so the DSU must unite only pairs with distance $< D$.
- Coordinates fit in 32-bit integers, but squared distances require long long.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

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

namespace {

struct DSU {
    vector<int> parent;
    vector<int> size;

    explicit DSU(const int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(const int x) {
        if (parent[x] == x) {
            return x;
        }
        parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        if (size[a] < size[b]) {
            swap(a, b);
        }
        parent[b] = a;
        size[a] += size[b];
    }
};

struct Point {
    long long x = 0;
    long long y = 0;
};

struct Edge {
    long long dist2 = 0;
    int u = 0;
    int v = 0;

    bool operator<(const Edge& other) const {
        return dist2 < other.dist2;
    }
};

long long squared_distance(const Point& a, const Point& b) {
    const long long dx = a.x - b.x;
    const long long dy = a.y - b.y;
    return dx * dx + dy * dy;
}

bool is_feasible(const int team_size,
                 const int total_points,
                 const vector<Edge>& edges,
                 const long long threshold) {
    DSU dsu(total_points);
    for (const Edge& edge : edges) {
        if (edge.dist2 >= threshold) {
            break;
        }
        dsu.unite(edge.u, edge.v);
    }

    vector<int> component_sizes;
    vector<int> seen(total_points, -1);
    for (int i = 0; i < total_points; ++i) {
        const int root = dsu.find(i);
        if (seen[root] != -1) {
            continue;
        }
        seen[root] = static_cast<int>(component_sizes.size());
        component_sizes.push_back(dsu.size[root]);
    }

    bitset<501> dp;
    dp[0] = 1;
    for (const int size : component_sizes) {
        dp |= (dp << size);
    }
    return dp[team_size];
}

vector<int> build_solution(const int team_size,
                           const int total_points,
                           const vector<Edge>& edges,
                           const long long threshold) {
    DSU dsu(total_points);
    for (const Edge& edge : edges) {
        if (edge.dist2 >= threshold) {
            break;
        }
        dsu.unite(edge.u, edge.v);
    }

    vector<int> component_index(total_points, -1);
    vector<int> component_sizes;
    vector<vector<int>> component_members;
    for (int i = 0; i < total_points; ++i) {
        const int root = dsu.find(i);
        if (component_index[root] == -1) {
            component_index[root] = static_cast<int>(component_sizes.size());
            component_sizes.push_back(0);
            component_members.push_back({});
        }
        const int id = component_index[root];
        ++component_sizes[id];
        component_members[id].push_back(i + 1);
    }

    const int component_count = static_cast<int>(component_sizes.size());
    vector<vector<char>> can(component_count + 1,
                             vector<char>(team_size + 1, 0));
    vector<vector<char>> parent_take(component_count + 1,
                                     vector<char>(team_size + 1, -1));
    can[0][0] = 1;

    for (int i = 0; i < component_count; ++i) {
        for (int sum = 0; sum <= team_size; ++sum) {
            if (!can[i][sum]) {
                continue;
            }
            if (!can[i + 1][sum]) {
                can[i + 1][sum] = 1;
                parent_take[i + 1][sum] = 0;
            }
            const int next_sum = sum + component_sizes[i];
            if (next_sum <= team_size && !can[i + 1][next_sum]) {
                can[i + 1][next_sum] = 1;
                parent_take[i + 1][next_sum] = 1;
            }
        }
    }

    vector<int> blue_team;
    int sum = team_size;
    for (int i = component_count; i >= 1; --i) {
        if (parent_take[i][sum] == 1) {
            for (const int member : component_members[i - 1]) {
                blue_team.push_back(member);
            }
            sum -= component_sizes[i - 1];
        }
    }
    sort(blue_team.begin(), blue_team.end());
    return blue_team;
}

void solve() {
    int team_size;
    cin >> team_size;
    const int total_points = 2 * team_size;

    vector<Point> points(total_points);
    for (Point& point : points) {
        cin >> point.x >> point.y;
    }

    vector<Edge> edges;
    edges.reserve(total_points * (total_points - 1) / 2);
    for (int i = 0; i < total_points; ++i) {
        for (int j = i + 1; j < total_points; ++j) {
            edges.push_back({squared_distance(points[i], points[j]), i, j});
        }
    }
    sort(edges.begin(), edges.end());

    vector<long long> distances;
    distances.reserve(edges.size());
    for (const Edge& edge : edges) {
        if (distances.empty() || distances.back() != edge.dist2) {
            distances.push_back(edge.dist2);
        }
    }

    int low = 0;
    int high = static_cast<int>(distances.size()) - 1;
    int best_index = 0;
    while (low <= high) {
        const int mid = low + (high - low) / 2;
        if (is_feasible(team_size, total_points, edges, distances[mid])) {
            best_index = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    const long long best_dist2 = distances[best_index];
    const vector<int> blue_team =
        build_solution(team_size, total_points, edges, best_dist2);

    cout << fixed << setprecision(6)
         << sqrt(static_cast<long double>(best_dist2)) << '\n';
    for (const int member : blue_team) {
        cout << member << '\n';
    }
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/icpc/2024/F-friendly-rivalry/solution.texC++ implementationcompetitive_programming/icpc/2024/F-friendly-rivalry/solution.cppStatement textcompetitive_programming/icpc/2024/F-friendly-rivalry/statement.txtStatement PDFcompetitive_programming/icpc/2024/F-friendly-rivalry/statement.pdfMetadatacompetitive_programming/icpc/2024/F-friendly-rivalry/meta.jsonYear packetcompetitive_programming/icpc/2024/contest_problems.pdf

F. Friendly Rivalry

Problem Statement

Input

Output

Sample Tests

Editorial

Key Observations

Algorithm

Correctness Proof

Complexity Analysis

Implementation Notes

Code

Source Files and Assets