Home » 国际竞赛 » Details

USACO 2021 December Contest, Silver Problem 3. Convoluted Intervals

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

USACO 2021 December Contest, Silver Problem 3. Convoluted Intervals

The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of $N$ intervals ( $1 \leq N \leq 2 \cdot 10^{5}$ ), where the $i$ th interval starts at position $a_{i}$ on the number line and ends at position $b_{i} \geq a_{i}$ . Both $a_{i}$ and $b_{i}$ are integers in the range $0 \dots M$ , where $1 \leq M \leq 5000$ .

To play the game, Bessie chooses some interval (say, the $i$ th interval) and her cousin Elsie chooses some interval (say, the $j$ th interval, possibly the same as Bessie's interval). Given some value $k$ , they win if $a_{i} + a_{j} \leq k \leq b_{i} + b_{j}$ .

For every value of $k$ in the range $0 \dots 2 M$ , please count the number of ordered pairs $(i, j)$ for which Bessie and Elsie can win the game.

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

The first line of input contains $N$ and $M$ . Each of the next $N$ lines describes an interval in terms of integers $a_{i}$ and $b_{i}$ .

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

Please print $2 M + 1$ lines as output, one for each value of $k$ in the range $0 \dots 2 M$ .

SAMPLE INPUT:

2 5
1 3
2 5

SAMPLE OUTPUT:

In this example, for just $k = 3$ , there are three ordered pairs that will allow Bessie and Elie to win: $(1, 1)$ , $(1, 2),$ and $(2, 1)$ .

SCORING:

Test cases 1-2 satisfy $N \leq 100, M \leq 100$ .
Test cases 3-5 satisfy $N \leq 5000$ .
Test cases 6-20 satisfy no additional constraints.

Note that output values might be too large to fit into a 32-bit integer, so you may want to use 64-bit integers (e.g., "long long" ints in C or C++).

Problem credits: Benjamin Qi

USACO 2021 December Contest, Silver Problem 3. Convoluted Intervals 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

A direct implementation of the definition in the problem statement to compute the win counts for all $k$ involves a nested loop over all pairs of intervals and all $k$ . This runs in $O (N^{2} M)$ time, and is only sufficient for the first two test cases.

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ivals(N);
	for (auto &ival : ivals)
		cin >> ival.first >> ival.second;
	vector<int64_t> win_counts(2 * M + 1);
	for (auto [a_i, b_i] : ivals)
		for (auto [a_j, b_j] : ivals)
			for (int k = a_i + a_j; k <= b_i + b_j; ++k)
				++win_counts.at(k);
	for (auto win : win_counts)
		cout << win << "\n";
}

Using prefix sums, we can remove the loop over $k$ , reducing the time complexity to $O (N^{2} + M)$ . Ths idea is to add one to $win_count$ just before an interval of wins begins and subtract one from $win_count$ just after an interval of wins ends. This is sufficient for the first five test cases, which all have relatively small $N$ .

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ivals(N);
	for (auto &ival : ivals)
		cin >> ival.first >> ival.second;
	vector<int64_t> win_start(2 * M + 1), win_end(2 * M + 1);
	for (auto [a_i, b_i] : ivals)
		for (auto [a_j, b_j] : ivals) {
			++win_start.at(a_i + a_j);
			++win_end.at(b_i + b_j);
		}
	int64_t win_count = 0;
	for (int i = 0; i <= 2 * M; ++i) {
		win_count += win_start.at(i);
		cout << win_count << "\n";
		win_count -= win_end.at(i);
	}
}

For full credit, we take advantage of $M$ being relatively small. Let's by noting that $win_start$ and $win_end$ may be computed separately.

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ivals(N);
	for (auto &ival : ivals)
		cin >> ival.first >> ival.second;
	vector<int64_t> win_start(2 * M + 1), win_end(2 * M + 1);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			++win_start.at(ivals.at(i).first+ivals.at(j).first);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			++win_end.at(ivals.at(i).second+ivals.at(j).second);
	int64_t win_count = 0;
	for (int i = 0; i <= 2 * M; ++i) {
		win_count += win_start.at(i);
		cout << win_count << "\n";
		win_count -= win_end.at(i);
	}
}

But the first nested loop is doing a lot of repeated work because many intervals will share the same left endpoints (similar reasoning holds for the right endpoints). If we instead iterate over all distinct left endpoints then we may reduce the runtime of each nested for loop to $O (M^{2})$ . We can do this by maintaining a length- $M + 1$ array $a_freq [a]$ that keeps track of the number of occurrences of $a$ over all intervals, and similarly for $b$ . The overall time complexity is $O (N + M^{2})$ .

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ivals(N);
	for (auto &ival : ivals)
		cin >> ival.first >> ival.second;
	vector<int64_t> win_start(2 * M + 1), win_end(2 * M + 1);
	{
		vector<int64_t> a_freq(M + 1);
		for (int i = 0; i < N; ++i)
			++a_freq.at(ivals.at(i).first);
		for (int i = 0; i <= M; ++i)
			for (int j = 0; j <= M; ++j)
				win_start.at(i + j) += a_freq.at(i) * a_freq.at(j);
	}
	{
		vector<int64_t> b_freq(M + 1);
		for (int i = 0; i < N; ++i)
			++b_freq.at(ivals.at(i).second);
		for (int i = 0; i <= M; ++i)
			for (int j = 0; j <= M; ++j)
				win_end.at(i + j) += b_freq.at(i) * b_freq.at(j);
	}
	int64_t win_count = 0;
	for (int i = 0; i <= 2 * M; ++i) {
		win_count += win_start.at(i);
		cout << win_count << "\n";
		win_count -= win_end.at(i);
	}
}

Danny Mittal's (similar) code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class IntervalConvolution {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());
        long totalPairs = ((long) n) * ((long) n);
        long[] aFreq = new long[m + 1];
        long[] bFreq = new long[m + 1];
        for (int j = 1; j <= n; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            aFreq[a]++;
            bFreq[b]++;
        }
        long[] aSumFreq = new long[(2 * m) + 1];
        long[] bSumFreq = new long[(2 * m) + 1];
        for (int x = 0; x <= m; x++) {
            for (int y = 0; y <= m; y++) {
                aSumFreq[x + y] += aFreq[x] * aFreq[y];
                bSumFreq[x + y] += bFreq[x] * bFreq[y];
            }
        }
        long aValid = aSumFreq[0];
        long bValid = totalPairs;
        StringBuilder out = new StringBuilder();
        for (int x = 0; x <= 2 * m; x++) {
            if (x > 0) {
                aValid += aSumFreq[x];
                bValid -= bSumFreq[x - 1];
            }
            long res = aValid + bValid - totalPairs;
            out.append(res).append('\n');
        }
        System.out.print(out);
    }
}

Interestingly, computing $win_start$ from $a_freq$ can be thought of as squaring the degree $M$ -polynomial represented by $a_freq$ (and polynomial multiplication is also known as convolution). Using fast polynomial multiplication would allow us to solve this problem in $O (N + M \log M)$ time.