Home » 国际竞赛 » Details

USACO 2020 February Contest, Gold Problem 2. Help Yourself

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

USACO 2020 February Contest, Gold Problem 2. Help Yourself

Bessie has been given? $N$ ?segments ( $1 \leq N \leq 10^{5}$ ) on a 1D number line. The? $i$ th segment contains all reals? $x$ ?such that? $l_{i} \leq x \leq r_{i}$ .

Define the?union?of a set of segments to be the set of all? $x$ ?that are contained within at least one segment. Define the?complexity?of a set of segments to be the number of connected regions represented in its union.

Bessie wants to compute the sum of the complexities over all? $2^{N}$ ?subsets of the given set of? $N$ ?segments, modulo? $10^{9} + 7$ .

Normally, your job is to help Bessie. But this time, you are Bessie, and there's no one to help you. Help yourself!

SCORING:

Test cases 2-3 satisfy? $N \leq 16$ .
Test cases 4-7 satisfy? $N \leq 1000$ .
Test cases 8-12 satisfy no additional constraints.

INPUT FORMAT (file help.in):

The first line contains? $N$ .Each of the next? $N$ ?lines contains two integers? $l_{i}$ ?and? $r_{i}$ . It is guaranteed that? $l_{i} < r_{i}$ ?and all? $l_{i}, r_{i}$ ?are distinct integers in the range? $1 \dots 2 N .$

OUTPUT FORMAT (file help.out):

Output the answer, modulo? $10^{9} + 7$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

The complexity of each nonempty subset is written below.

{[1, 6]} ? 1, {[2, 3]} ? 1, {[4, 5]} ? 1

{[1, 6], [2, 3]} ? 1, {[1, 6], [4, 5]} ? 1, {[2, 3], [4, 5]} ? 2

{[1, 6], [2, 3], [4, 5]} ? 1

The answer is? $1 + 1 + 1 + 1 + 1 + 2 + 1 = 8$ .

Problem credits: Benjamin Qi

USACO 2020 February Contest, Gold Problem 3. Delegation 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

We'll use linearity of expectation. The complexity of a subset is equal to the number of integers? $i$ ?such that the interval? $(i, i + 1)$ ?is contained within one of the segments in the subset but? $(i - 1, i)$ ?isn't (informally, the number of "start" points). In other words, the segment with left endpoint? $i$ ?contributes one to the complexity as long as it is part of the subset and no other segment in the subset contains? $(i - 1, i)$ .

This is true for exactly? $2^{N - 1 - (# of intervals that contain (i, i + 1))}$ ?subsets. The sum of this quantity over all intervals can be computed in? $O (N)$ ?time with prefix sums and precalculation of powers of 2.

#include "bits/stdc++.h"

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

#define f first
#define s second

const int MOD = 1e9+7;

int N;
 
int main() {
	setIO("help");
	cin >> N; vector<pair<int,int>> v(N);
	for (auto& a: v) cin >> a.f >> a.s;
	vector<int> over(2*N+1), po2(N);
	po2[0] = 1; for (int i = 1; i < N; ++i) po2[i] = 2*po2[i-1]%MOD;
	for (auto& t: v) over[t.f] ++, over[t.s] --; 
	for (int i = 1; i <= 2*N; ++i) over[i] += over[i-1];
	int ans = 0; for (auto& t: v) ans = (ans+po2[N-1-over[t.f-1]])%MOD;
	cout << ans << "\n";
}

[/hide]