USACO 2020 February Contest, Gold Problem 2. Help Yourself

USACO 2020 February Contest, Gold Problem 2. Help Yourself

Bessie has been given NN segments (1N1051≤N≤105) on a 1D number line. The iith segment contains all reals xx such that lixrili≤x≤ri.

Define the union of a set of segments to be the set of all xx 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 2N2N subsets of the given set of NN segments, modulo 109+7109+7.

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



  • Test cases 2-3 satisfy N16N≤16.
  • Test cases 4-7 satisfy N1000N≤1000.
  • Test cases 8-12 satisfy no additional constraints.



The first line contains NN.Each of the next NN lines contains two integers lili and riri. It is guaranteed that li<rili<ri and all li,rili,ri are distinct integers in the range 12N.1…2N.


OUTPUT FORMAT (file help.out):

Output the answer, modulo 109+7109+7.



1 6
2 3
4 5



The complexity of each nonempty subset is written below.







The answer is 1+1+1+1+1+2+1=81+1+1+1+1+2+1=8.


Problem credits: Benjamin Qi

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



(Analysis by Benjamin Qi)

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

This is true for exactly 2N1(# of intervals that contain(i,i+1))2N−1−(# of intervals that contain(i,i+1)) subsets. The sum of this quantity over all intervals can be computed in O(N)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); 

#define f first
#define s second

const int MOD = 1e9+7;

int N;
int main() {
	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";