Home » 国际竞赛 » Details

USACO 2021 December Contest, Platinum Problem 2. Paired Up

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

USACO 2021 December Contest, Platinum Problem 2. Paired Up

There are a total of $N$ ( $1 \leq N \leq 5000$ ) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the $i$ -th cow is given by $b_{i} \in {H, G}$ , 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^{5}$ ).

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

Every pair consists of a Holstein $h$ and a Guernsey $g$ whose locations are within $K$ of each other ( $1 \leq K \leq 10^{9}$ ); that is, $| x_{h} - x_{g} | \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 input line contains $T$ , $N$ , and $K$ .Following this are $N$ lines, the $i$ -th of which contains $b_{i}, x_{i}, 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):

The minimum or maximum possible sum of weights of the unpaired cows.

SAMPLE INPUT:

SAMPLE OUTPUT:

Cows $2$ and $3$ can pair up because they are at distance $1$ , which is at most $K = 4$ . This pairing is maximal, because cow $1$ , the only remaining Guernsey, is at distance $5$ from cow $4$ and distance $7$ from cow $5$ , which are more than $K = 4$ . The sum of weights of unpaired cows is $1 + 6 + 9 = 16$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

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

SAMPLE INPUT:

SAMPLE OUTPUT:

The answer to this example is $18 + 465 + 870 + 540 = 1893$ .

SCORING:

Test cases 4-7 satisfy $T = 1$ .
Test cases 8-14 satisfy $T = 2$ and $N \leq 300$ .
Test cases 15-22 satisfy $T = 2$ .

**Note: the memory limit for this problem is 512MB, twice the default.**

Problem credits: Benjamin Qi

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

题解请注册或登录查看

[/hide]

(Analysis by Danny Mittal)

It's first important to observe that for any valid pairing, we can sort the Guernseys in the pairing, then sort the Holsteins in the pairing, and then pair up the first Guernsey with the first Holstein, the second Guernsey with the second Holstein, and so on, and that will also be a valid pairing.

This idea means that we can attain any valid set of paired cows using a DP where the first parameter is how many of the first Guernseys we've already used, and the second parameter is how many of the first Holsteins we've already used, since it's optimal to pair the next Guernsey we pair with the next Holstein we pair from the above idea. We will use this DP to solve the problem.

Subtask 1: $T = 1$ , $N \leq 5000$

Minimizing the sums of weights of the unpaired cows is the same as maximizing the sums of weights of paired cows. Furthermore, the pairing of cows with the highest sum of weights will clearly be maximal, because otherwise we could add the pair of unpaired cows to increase the sum of weights. Therefore, this subtask is equivalent to finding the pairing of cows with maximum sum of weight of the paired cows.

We can do this using the exact DP idea explained above. Define $d p_{x, y}$ to be the maximum weight of paired cows where we've only considered the first $x$ Guernseys and the first $y$ Holsteins. There are three ways to transition to a state $(x, y)$ : by choosing not to pair the $x$ -th Guernsey, by choosing not to pair the $y$ -th Holstein, or by pairing up the $x$ -th Guernsey with the $y$ -th Holstein.

There are $O (N^{2})$ states and the transitions can be computed in constant time, so the runtime is $O (N^{2})$ , which is fast enough for the given constraints.

Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class PairedUpHarderMin {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int t = Integer.parseInt(tokenizer.nextToken());
        if (t != 1) {
            throw new IllegalArgumentException();
        }
        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());
        int[] guernseyLocations = new int[n + 1];
        long[] guernseyWeights = new long[n + 1];
        int[] holsteinLocations = new int[n + 1];
        long[] holsteinWeights = new long[n + 1];
        boolean[] isGuernsey = new boolean[n + 1];
        int g = 0;
        int h = 0;
        long totalImportance = 0;
        for (int j = 1; j <= n; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            isGuernsey[j] = tokenizer.nextToken().equals("G");
            int location = Integer.parseInt(tokenizer.nextToken());
            int weight = Integer.parseInt(tokenizer.nextToken());
            if (isGuernsey[j]) {
                g++;
                guernseyLocations[g] = location;
                guernseyWeights[g] = weight;
            } else {
                h++;
                holsteinLocations[h] = location;
                holsteinWeights[h] = weight;
            }
            totalImportance += weight;
        }
        long[][] dp = new long[g + 1][h + 1];
        for (int j1 = 1; j1 <= g; j1++) {
            for (int j2 = 1; j2 <= h; j2++) {
                dp[j1][j2] = Math.max(dp[j1 - 1][j2], dp[j1][j2 - 1]);
                if (Math.abs(guernseyLocations[j1] - holsteinLocations[j2]) <= k) {
                    dp[j1][j2] = Math.max(dp[j1][j2], dp[j1 - 1][j2 - 1] + guernseyWeights[j1] + holsteinWeights[j2]);
                }
            }
        }
        long answer = totalImportance - dp[g][h];
        System.out.println(answer);
    }
}

Subtask 2: $T = 2$ , $N \leq 300$

For $T = 2$ we will solve the problem directly. We can use the same DP states as we did for $T = 1$ , but when choosing not to pair a Guernsey, we need to make sure that it is more than $K$ distance to the right from the last Holstein we chose not to pair, and vice versa.

To account for this, we could augment our DP state to also include the last Guernsey we chose not to pair and the last Holstein we chose not to pair. This DP has $O (N^{4})$ states, and the transitions are essentially the same as before, so $O (1)$ . Unfortunately, no subtask had constraints low enough for $O (N^{4})$ to pass (though it would pass the samples).

We can improve this by noting that we don't actually need to know the last Holstein and the last Guernsey that we chose not to pair -- we only need to know the last cow that we chose not to pair. This is because if the last cow we chose not to pair was a Guernsey, then it was clearly more than $K$ distance to the right from the last Holstein that we chose not to pair, so it's valid to choose not to pair an additional Guernsey (and vice versa).

Formally, we compute a DP $d p_{x, y, j}$ equal to the maximum sum of weights of unpaired cows where we've considered the first $x$ Guernseys and the first $y$ Holsteins, and the last cow we chose not to pair was cow $j$ . This improves the amount of states to $O (N^{3})$ , while keeping the transitions basically the same. A runtime of $O (N^{3})$ is sufficient to pass this subtask.

Ben's code:

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

template <class T> using V = vector<T>;

int main() {
	int T, N, K;
	cin >> T >> N >> K;
	assert(T == 2);
	V<pair<int, int>> cows[2];
	for (int i = 0; i < N; ++i) {
		char b;
		int x, y;
		cin >> b >> x >> y;
		cows[b == 'H'].push_back({x, y});
	}
	const int A = (int)cows[0].size();
	const int B = (int)cows[1].size();
	V<V<V<int>>> dp(A + 1, V<V<int>>(B + 1, V<int>(N + 1, -1)));
	// dp[i][j][k] = i Guernseys processed, j Holsteins processed,
	// index of last unpaired (or N if none)
	dp[0][0][N] = 0;
	auto ckmax = [&](int &a, int b) { a = max(a, b); };
	for (int i = 0; i <= A; ++i)
		for (int j = 0; j <= B; ++j)
			for (int k = 0; k <= N; ++k) {
				if (dp[i][j][k] == -1)
					continue;
				if (i < A && j < B &&
					abs(cows[0][i].first - cows[1][j].first) <= K)
					ckmax(dp[i + 1][j + 1][k], dp[i][j][k]);
				if (i < A)
					if (!(A <= k && k < A + B &&
						  cows[0].at(i).first <= cows[1].at(k - A).first + K))
						ckmax(dp[i + 1][j][i],
							  dp[i][j][k] + cows[0].at(i).second);
				if (j < B)
					if (!(k < A &&
						  cows[1].at(j).first <= cows[0].at(k).first + K))
						ckmax(dp[i][j + 1][A + j],
							  dp[i][j][k] + cows[1].at(j).second);
			}
	int ans = INT_MIN;
	for (int i = 0; i <= N; ++i)
		ans = max(ans, dp[A][B][i]);
	cout << ans;
}

Subtask 3: $T = 2$ , $N \leq 5000$

We will solve the final subtask using the same general DP idea as before, but with a slightly different DP than in the previous subtask. Rather than including the last cow that we chose not to pair in the DP state, we will include an indicator variable saying either that we are only allowed to not pair Guernseys right now, or that we are only allowed to not pair Holsteins right now.

Formally, define $d p_{x, y, b}$ to be the maximum sum of weights of unpaired cows where we've considered the first $x$ Guernseys and the first $y$ Holsteins, and the next cow that we choose not to pair must be of breed $b$ . This DP has $O (N^{2})$ states. The motivation for this DP idea is similar to for the previous subtask: if we choose not to pair a cow of breed $b$ , then we are also free not to pair the next cow of breed $b$ , or any following cow of that breed until we at some point choose not to pair a cow of the opposite breed.

This means that at a state $(x, y, G)$ , choosing not to pair the next Guernsey simply transitions to the state $(x + 1, y, G)$ , because we're still free to choose not to pair a Guernsey again. Similarly, from a state $(x, y, H)$ , choosing not to pair a Holstein transitions to a state $(x, y + 1, H)$ .

Choosing to pair two cows is as simple as before: we simply transition from the state $(x, y, b)$ to the state $(x + 1, y + 1, b)$ .

The complication comes when we consider the fact that we don't want to be forced to only not pair Guernseys or only not pair Holsteins. At a state $(x, y, b)$ , we may want to start not pairing cows of the other breed. This introduces another transition. Assume that $b = G$ . If we're being forced right now to only not pair Guernseys, then in the worst case the last unpaired cow was the Guernsey we considered, which was the $x$ -th Guernsey.

This means that if we want to switch to not pairing Holsteins, then we need to repeatedly pair cows until the next available Holstein is more than $K$ distance to the right from the $x$ -th Guernsey. If the next Holstein more than $K$ distance to the right from the $x$ -th Guernsey is the $y^{'} + 1$ -th Holstein, then we need to pair the next $y^{'} - y$ pairs of Guernseys and Holsteins, arriving at the state $(y^{'} - y + x, y^{'})$ .

We can compute this transition in constant time by precomputing $y^{'}$ for each $x$ . We also need to make sure that those $y^{'} - y$ pairs are actually valid pairs; this can also be checked in constant time using precomputation.

We also perform a similar transition for the case where $b = H$ . All of the necessary transitions can therefore be computed in constant time, so since we have $O (N^{2})$ states, the runtime is $O (N^{2})$ which is sufficient to pass the final subtask.

Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class PairedUpHarderMaxSimpler {
    public static final long SMALL = -1000000000;
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int t = Integer.parseInt(tokenizer.nextToken());
        if (t != 2) {
            throw new IllegalArgumentException();
        }
        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());
        int[] guernseyLocations = new int[n + 1];
        long[] guernseyWeights = new long[n + 1];
        int[] holsteinLocations = new int[n + 1];
        long[] holsteinWeights = new long[n + 1];
        boolean[] isGuernsey = new boolean[n + 1];
        int g = 0;
        int h = 0;
        for (int j = 1; j <= n; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            isGuernsey[j] = tokenizer.nextToken().equals("G");
            int location = Integer.parseInt(tokenizer.nextToken());
            int weight = Integer.parseInt(tokenizer.nextToken());
            if (isGuernsey[j]) {
                g++;
                guernseyLocations[g] = location;
                guernseyWeights[g] = weight;
            } else {
                h++;
                holsteinLocations[h] = location;
                holsteinWeights[h] = weight;
            }
        }
 
        int[][] lastValidPairStartingFrom = new int[g + 1][h + 1];
        for (int x = g; x >= 0; x--) {
            for (int y = h; y >= 0; y--) {
                if (x < g && y < h && Math.abs(guernseyLocations[x + 1] - holsteinLocations[y + 1]) <= k) {
                    lastValidPairStartingFrom[x][y] = lastValidPairStartingFrom[x + 1][y + 1];
                } else {
                    lastValidPairStartingFrom[x][y] = x;
                }
            }
        }
        int[] lastTooCloseHolstein = new int[g + 1];
        for (int x = 1; x <= g; x++) {
            while (lastTooCloseHolstein[x] <= h && holsteinLocations[lastTooCloseHolstein[x]] <= guernseyLocations[x] + k) {
                lastTooCloseHolstein[x]++;
            }
            lastTooCloseHolstein[x]--;
        }
        int[] lastTooCloseGuernsey = new int[h + 1];
        for (int y = 1; y <= h; y++) {
            while (lastTooCloseGuernsey[y] <= g && guernseyLocations[lastTooCloseGuernsey[y]] <= holsteinLocations[y] + k) {
                lastTooCloseGuernsey[y]++;
            }
            lastTooCloseGuernsey[y]--;
        }
        long[][][] dp = new long[2][g + 1][h + 1];
        for (int b = 0; b <= 1; b++) {
            for (int x = 0; x <= g; x++) {
                for (int y = 0; y <= h; y++) {
                    dp[b][x][y] = SMALL;
                }
            }
        }
        dp[0][0][0] = 0;
        dp[1][0][0] = 0;
        for (int x = 0; x <= g; x++) {
            for (int y = 0; y <= h; y++) {
                int nextY = Math.max(y, lastTooCloseHolstein[x]);
                if (lastValidPairStartingFrom[x][y] - x + y >= nextY) {
                    dp[1][nextY - y + x][nextY] = Math.max(dp[1][nextY - y + x][nextY], dp[0][x][y]);
                }
                int nextX = Math.max(x, lastTooCloseGuernsey[y]);
                if (lastValidPairStartingFrom[x][y] >= nextX) {
                    dp[0][nextX][nextX - x + y] = Math.max(dp[0][nextX][nextX - x + y], dp[1][x][y]);
                }
 
                if (lastValidPairStartingFrom[x][y] >= x + 1) {
                    dp[0][x + 1][y + 1] = Math.max(dp[0][x + 1][y + 1], dp[0][x][y]);
                    dp[1][x + 1][y + 1] = Math.max(dp[1][x + 1][y + 1], dp[1][x][y]);
                }
 
                if (x < g) {
                    dp[0][x + 1][y] = Math.max(dp[0][x + 1][y], dp[0][x][y] + guernseyWeights[x + 1]);
                }
                if (y < h) {
                    dp[1][x][y + 1] = Math.max(dp[1][x][y + 1], dp[1][x][y] + holsteinWeights[y + 1]);
                }
            }
        }
        System.out.println(Math.max(dp[0][g][h], dp[1][g][h]));
    }
}

Open(?) Problem: Can you solve $T = 1$ in $o (N^{2})$ time?

Author's Note: This was inspired by a task from 21M.387. Given a song, a list of estimated boundary locations, and a list of ground truth boundary locations, we can define the number of "true positives" to be the maximum number of $(estimated location, ground truth location)$ pairs one can form such that $estimated location$ is within $τ$ seconds of $ground truth location$ for some choice of $τ$ .
[/hide]