USACO 2021 December Contest, Gold Problem 1. Paired Up

USACO 2021 December Contest, Gold Problem 1. Paired Up

There are a total of NN (1≤N≤1051≤N≤105) cows on the number line. The location of the ii-th cow is given by xixi (0≤xi≤1090≤xi≤109), and the weight of the ii-th cow is given by yiyi (1≤yi≤1041≤yi≤104).

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

 

• Every pair consists of two distinct cows aa and bb whose locations are within KK of each other (1≤K≤1091≤K≤109); that is, |xa−xb|≤K|xa−xb|≤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=1T=1, compute the minimum possible sum of weights of the unpaired cows.
• If T=2T=2, compute the maximum possible sum of weights of the unpaired cows.

 

 

 

SAMPLE INPUT:

2 5 2
1 2
3 2
4 2
5 1
7 2

SAMPLE OUTPUT:

6

In this example, cows 22 and 44 can pair up because they are at distance 22, which is at most K=2K=2. This pairing is maximal, because cows 11 and 33 are at distance 33, cows 33 and 55 are at distance 33, and cows 11 and 55 are at distance 66, all of which are more than K=2K=2. The sum of weights of unpaired cows is 2+2+2=62+2+2=6.

 

SAMPLE INPUT:

1 5 2
1 2
3 2
4 2
5 1
7 2

SAMPLE OUTPUT:

2

Here, cows 11 and 22 can pair up because they are at distance 2≤K=22≤K=2, and cows 44 and 55 can pair up because they are at distance 2≤K=22≤K=2. This pairing is maximal because only cow 33 remains. The weight of the only unpaired cow here is simply 22.

 

SAMPLE INPUT:

2 15 7
3 693
10 196
12 182
14 22
15 587
31 773
38 458
39 58
40 583
41 992
84 565
86 897
92 197
96 146
99 785

SAMPLE OUTPUT:

2470

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

 

 

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 nn be the length of the current chain.

Case 1: T=1T=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)O(N) time.

Case 2: T=2T=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(NlogN)O(Nlog⁡N) time.

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

If it's possible to leave cow ii unpaired with jj unpaired cows, then dp[i][j]=max(dp[i+1][j],dp[ub[i]][j−1]+yi)dp[i][j]=max(dp[i+1][j],dp[ub[i]][j−1]+yi). Otherwise, dp[i][j]=dp[i+1][j]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(NlogN)O(Nlog⁡N) time (which can easily be reduced to O(N)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]