Home » 国际竞赛 » Details

USACO 2021 December Contest, Gold Problem 1. Paired Up

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午12:55

USACO 2021 December Contest, Gold Problem 1. Paired Up

There are a total of? $N$ ?( $1 \leq N \leq 10^{5}$ ) cows on the number line. The location of the? $i$ -th cow is given by? $x_{i}$ ?( $0 \leq x_{i} \leq 10^{9}$ ), and the weight of the? $i$ -th cow is given by? $y_{i}$ ?( $1 \leq y_{i} \leq 10^{4}$ ).

At Farmer John's signal, some of the cows will form pairs such that

Every pair consists of two distinct cows? $a$ ?and? $b$ ?whose locations are within? $K$ ?of each other ( $1 \leq K \leq 10^{9}$ ); that is,? $| x_{a} - x_{b} | \leq K$ .
Every cow is either part of a single pair or not part of a pair.
The pairing is?maximal;?that is, no two unpaired cows can form a pair.

It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,

If? $T = 1$ , compute the minimum possible sum of weights of the unpaired cows.
If? $T = 2$ , compute the maximum possible sum of weights of the unpaired cows.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains? $T$ ,? $N$ , and? $K$ .In each of the following? $N$ ?lines, the? $i$ -th contains? $x_{i}$ ?and? $y_{i}$ . It is guaranteed that? $0 \leq x_{1} < x_{2} < \dots < x_{N} \leq 10^{9}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

Please print out the minimum or maximum possible sum of weights of the unpaired cows.

SAMPLE INPUT:

SAMPLE OUTPUT:

In this example, cows? $2$ ?and? $4$ ?can pair up because they are at distance? $2$ , which is at most? $K = 2$ . This pairing is maximal, because cows? $1$ ?and? $3$ ?are at distance? $3$ , cows? $3$ ?and? $5$ ?are at distance? $3$ , and cows? $1$ ?and? $5$ ?are at distance? $6$ , all of which are more than? $K = 2$ . The sum of weights of unpaired cows is? $2 + 2 + 2 = 6$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

Here, cows? $1$ ?and? $2$ ?can pair up because they are at distance? $2 \leq K = 2$ , and cows? $4$ ?and? $5$ ?can pair up because they are at distance? $2 \leq K = 2$ . This pairing is maximal because only cow? $3$ ?remains. The weight of the only unpaired cow here is simply? $2$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

The answer for this example is? $693 + 992 + 785 = 2470$ .

SCORING:

Test cases 4-8 satisfy? $T = 1$ .
Test cases 9-14 satisfy? $T = 2$ ?and? $N \leq 5000$ .
Test cases 15-20 satisfy? $T = 2$ .

Problem credits: Benjamin Qi

USACO 2021 December Contest, Gold Problem 1. Paired Up 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Andi Qu)

Let's call two adjacent cows "linked" if they are able to pair up with each other. We can split the cows up into chains where each pair of adjacent cows in a chain are linked, and no two cows in different chains are linked.

In each case below, we process each chain independently – let? $n$ ?be the length of the current chain.

Case 1:? $T = 1$

For chains with an even number of cows, we can pair up all of them. For chains with an odd number of cows, we want to have exactly 1 unpaired cow. If we leave more than 1 cow unpaired, then we can split the chain into an odd-length suffix with 1 unpaired cow and an even-length prefix with all the other unpaired cows. Since the prefix has an even length, we can pair up all of its cows, which would result in a smaller sum of weights of unpaired cows.

We can thus iterate through each cow in odd-length chains, check whether it can be unpaired (removing it should not result in two odd-length chains), and finally, leave the least valuable cow unpaired.

This case can thus be solved in? $O (N)$ ?time.

Case 2:? $T = 2$

In this case, we should try to leave unpaired cows in both even- and odd-length chains. We can use dynamic programming to solve this in? $O (N \log N)$ ?time.

Let? $dp [i] [j]$ ?be the maximum sum of values of unpaired cows if we only consider? $i$ ?to? $n$ ?cows in the current chain and there are? $j$ ?unpaired ones. Let? $ub [i]$ ?be the index of the leftmost cow to the right of cow? $i$ ?that can be unpaired if cow? $i$ ?is unpaired (or? $n + 1$ ?if it doesn't exist). We can compute? $ub [i]$ ?using binary search.

If it's possible to leave cow? $i$ ?unpaired with? $j$ ?unpaired cows, then? $dp [i] [j] = max (dp [i + 1] [j], dp [ub [i]] [j - 1] + y_{i})$ . Otherwise,? $dp [i] [j] = dp [i + 1] [j]$ .

Since we only care about the parity of the number of unpaired cows, we can drop the second dimension of the DP array. This allows us to compute the whole DP array in? $O (N \log N)$ ?time (which can easily be reduced to? $O (N)$ ).

Andi's code:

#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

const int INF = 1e9;

int min_span_cost(vector<pair<int, int>>& span, int k) {
    int mn = INF;
    for (int i = 0; i < span.size(); i++) {
        if (!(i & 1) || span[i + 1].first - span[i - 1].first <= k)
            mn = min(mn, span[i].second);
    }
    return mn;
}

int max_span_cost(vector<pair<int, int>>& span, int k) {
    int n = span.size();
    if (!n) return 0;
    vector<pair<int, int>> dp(n + 1);
    dp[n] = {0, -INF};
    for (int i = n - 1; ~i; i--) {
        dp[i] = dp[i + 1];
        int ub = upper_bound(span.begin(), span.end(),
                             make_pair(span[i].first + k, INF)) -
                 span.begin();
        if (i == 0 || i == n - 1 ||
            span[i + 1].first - span[i - 1].first <= k || !(n - i & 1))
            dp[i].first = max(dp[i].first, dp[ub].second + span[i].second);
        if (i == 0 || i == n - 1 ||
            span[i + 1].first - span[i - 1].first <= k || (n - i & 1))
            dp[i].second = max(dp[i].second, dp[ub].first + span[i].second);
    }
    return (n & 1 ? dp[0].second : dp[0].first);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t, n, k;
    cin >> t >> n >> k;
    int prev_x = 0, ans = 0;
    vector<pair<int, int>> curr_span;
    while (n--) {
        int x, y;
        cin >> x >> y;
        if (x - prev_x > k) {
            if (t == 1) {
                if (curr_span.size() & 1) ans += min_span_cost(curr_span, k);
            } else
                ans += max_span_cost(curr_span, k);
            curr_span.clear();
        }
        curr_span.push_back({x, y});
        prev_x = x;
    }
    if (t == 1) {
        if (curr_span.size() & 1) ans += min_span_cost(curr_span, k);
    } else
        ans += max_span_cost(curr_span, k);
    cout << ans;
    return 0;
}

[/hide]