USACO 2026 Third Contest Silver Division - Point Elimination#

Problem link: here

Problem Solution#

Since we may swap \(y\)-coordinates arbitrarily, the \(x\)-coordinates stay attached to the points, while the multiset of \(y\)-coordinates can be reassigned however we want. Every deleted pair is of exactly one type:

\(\textbf{horizontal}\): its \(x\)-coordinates differ by \(1\) and its \(y\)-coordinates are equal;
\(\textbf{vertical}\): its \(x\)-coordinates are equal and its \(y\)-coordinates differ by \(1\).

Therefore we can study the \(x\)-coordinates and \(y\)-coordinates separately.

For the \(x\)-coordinates, suppose exactly \(h\) pairs use two consecutive values. These will become the horizontal pairs; all other pairs must use equal \(x\)-coordinates.

Similarly, for the \(y\)-coordinates, exactly \(v\) pairs must use consecutive values, while the remaining pairs use equal values. Since every deleted pair is either horizontal or vertical, we need \(h+v=\frac N2.\)

Thus, for one multiset of coordinates, we need to determine which numbers of ``consecutive-value pairs'' are possible.

Possible Number of Consecutive Pairs#

Sort the coordinate values and compress equal values. Let the multiplicities of one maximal block of consecutive coordinates be \(c_1,c_2,\ldots,c_m.\)

Different blocks cannot interact, because a gap larger than \(1\) cannot be used by any pair. Hence every block must contain an even total number of points; otherwise pairing everything is impossible. Inside one block, points at coordinate \(i\) may be paired either with the same coordinate, or with coordinate \(i-1\) or \(i+1\).

Minimum#

Scan from left to right. Suppose some points of \(c_i\) were already paired with \(i-1\). The remaining points should preferably be paired among themselves.

If their number is even, no pair with \(i+1\) is necessary. If it is odd, exactly one such pair is necessary. This greedy choice gives the minimum possible number of consecutive-coordinate pairs.

Maximum#

Again scan from left to right. At coordinate \(i\), after accounting for pairs coming from \(i-1\), use as many pairs with \(i+1\) as possible.

However, after choosing these pairs, the number left at coordinate \(i\) must be even so that they can pair among themselves. Thus we take the largest possible number of pairs with \(i+1\) having the required parity.

This gives the maximum possible number of consecutive-coordinate pairs.

An important property is that every feasible value between the minimum and maximum with the same parity is attainable. Therefore, for each coordinate multiset we obtain a range \(L,L+2,L+4,\ldots,R.\)

Combining the Two Coordinates#

Compute \((L_x,R_x)\) for all \(x\)-coordinates and \((L_y,R_y)\) for all \(y\)-coordinates. We need some feasible \(h\) and \(v\) such that \(h+v=N/2\). Hence a solution exists exactly when \(L_x+L_y\le \frac N2\le R_x+R_y\) and the parity matches: \(\frac N2-(L_x+L_y)\) must be even.

If either coordinate multiset itself cannot be completely paired, the answer is immediately \texttt{NO}. Otherwise, the conditions above are sufficient because the \(y\)-coordinates may be permuted arbitrarily, allowing the chosen horizontal and vertical pairings to be matched together.

For each test case, sorting the \(x\)- and \(y\)-coordinates dominates the running time, so the complexity is \(O(N\log N)\) and the memory usage is \(O(N)\).

Source code#

The source code for the solution in C++ can be seen below.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 100000;

struct Result {
    bool possible;
    int minimum_pairs;
    int maximum_pairs;
};

Result get_range(vector<int> values) {
    sort(values.begin(), values.end());

    vector<int> coordinate;
    vector<int> count;

    for (int value : values) {
        if (coordinate.empty() || coordinate.back() != value) {
            coordinate.push_back(value);
            count.push_back(1);
        }
        else {
            count.back()++;
        }
    }

    int minimum_pairs = 0;
    int maximum_pairs = 0;

    int start = 0;

    while (start < (int)coordinate.size()) {
        int finish = start;

        int total = count[start];

        while (finish + 1 < (int)coordinate.size() &&
               coordinate[finish + 1] == coordinate[finish] + 1) {
            finish++;
            total += count[finish];
        }

        if (total % 2 == 1) {
            return {false, 0, 0};
        }

        int incoming = 0;

        for (int i = start; i < finish; i++) {
            int remaining = count[i] - incoming;

            int take = remaining % 2;

            minimum_pairs += take;
            incoming = take;
        }

        if ((count[finish] - incoming) % 2 == 1) {
            return {false, 0, 0};
        }

        incoming = 0;

        for (int i = start; i < finish; i++) {
            int remaining = count[i] - incoming;

            int take = min(remaining, count[i + 1]);

            if (take % 2 != remaining % 2) {
                take--;
            }

            maximum_pairs += take;
            incoming = take;
        }

        start = finish + 1;
    }

    return {true, minimum_pairs, maximum_pairs};
}

void solve() {
    int n;
    cin >> n;

    vector<int> x(n);
    vector<int> y(n);

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }

    Result x_result = get_range(x);
    Result y_result = get_range(y);

    if (!x_result.possible || !y_result.possible) {
        cout << "NO\n";
        return;
    }

    int needed = n / 2;

    int minimum_sum =
        x_result.minimum_pairs + y_result.minimum_pairs;

    int maximum_sum =
        x_result.maximum_pairs + y_result.maximum_pairs;

    if (needed < minimum_sum || needed > maximum_sum) {
        cout << "NO\n";
        return;
    }

    if ((needed - minimum_sum) % 2 != 0) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}