USACO 2022 US Open Contest, Gold Problem 3. Balancing a Tree

USACO 2022 US Open Contest, Gold Problem 3. Balancing a Tree

Farmer John has conducted an extensive study of the evolution of different cow breeds. The result is a rooted tree with NN (2N1052≤N≤105) nodes labeled 1N1…N, each node corresponding to a cow breed. For each i[2,N]i∈[2,N], the parent of node ii is node pipi (1pi<i1≤pi<i), meaning that breed ii evolved from breed pipi. A node jj is called an ancestor of node ii if j=pij=pi or jj is an ancestor of pipi.

Every node ii in the tree is associated with a breed having an integer number of spots sisi. The "imbalance" of the tree is defined to be the maximum of |sisj||si−sj| over all pairs of nodes (i,j)(i,j) such that jj is an ancestor of ii.

Farmer John doesn't know the exact value of sisi for each breed, but he knows lower and upper bounds on these values. Your job is to assign an integer value of si[li,ri]si∈[li,ri] (0liri1090≤li≤ri≤109) to each node such that the imbalance of the tree is minimized.

 

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

The first line contains TT (1T101≤T≤10), the number of independent test cases to be solved, and an integer B{0,1}B∈{0,1}.Each test case starts with a line containing NN, followed by N1N−1 integers p2,p3,,pNp2,p3,…,pN.

The next NN lines each contain two integers lili and riri.

It is guaranteed that the sum of NN over all test cases does not exceed 105105.

 

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

For each test case, output one or two lines, depending on the value of BB.The first line for each test case should contain the minimum imbalance.

If B=1,B=1, then print an additional line with NN space-separated integers s1,s2,,sNs1,s2,…,sN containing an assignment of spots that achieves the above imbalance. Any valid assignment will be accepted.

 

SAMPLE INPUT:

3 0
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

SAMPLE OUTPUT:

3
1
4

For the first test case, the minimum imbalance is 33. One way to achieve imbalance 33 is to set [s1,s2,s3]=[4,1,7][s1,s2,s3]=[4,1,7].

 

SAMPLE INPUT:

3 1
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

SAMPLE OUTPUT:

3
3 1 6
1
6 5 5 5 5
4
5 1 9

This input is the same as the first one aside from the value of BB. Another way to achieve imbalance 33 is to set [s1,s2,s3]=[3,1,6][s1,s2,s3]=[3,1,6].

SCORING:

  • Test cases 3-4 satisfy li=rili=ri for all ii.
  • Test cases 5-6 satisfy pi=i1pi=i−1 for all ii.
  • Test cases 7-16 satisfy no additional constraints.

Within each subtask, the first half of the test cases will satisfy B=0B=0, and the rest will satisfy B=1B=1.

Problem credits: Andrew Wang

 USACO 2022 US Open Contest, Gold Problem 3. Balancing a Tree 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

Say that ii and jj are related if ii is an ancestor of jj or vice versa. Let ansans denote the minimum possible imbalance.

Part 1: li=rili=ri

Here wiwi is fixed for all ii. To calculate ansans, we can compute for every node ii the minimum wjwj and maximum wjwj over all ancestors jj of ii as well as j=ij=i. This can be done in O(N)O(N) time.

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T, B;
	cin >> T >> B;
	while (T--) {
		int N;
		cin >> N;
		vector<int> P(N + 1), L(N + 1), R(N + 1);
		for (int i = 2; i <= N; ++i) {
			cin >> P[i];
		}
		int ans = 0;
		vector<pair<int, int>> bounds(N + 1);
		for (int i = 1; i <= N; ++i) {
			cin >> L[i] >> R[i];
			assert(L[i] == R[i]);
			bounds[i] = {L[i], L[i]};
			if (i > 1) {
				bounds[i].first = min(bounds[i].first, bounds[P[i]].first);
				bounds[i].second = max(bounds[i].second, bounds[P[i]].second);
			}
			ans = max(ans, bounds[i].second - bounds[i].first);
		}
		cout << ans << "\n";
		if (B == 1) {
			for (int i = 1; i <= N; ++i) {
				if (i > 1) cout << " ";
				cout << L[i];
			}
			cout << "\n";
		}
	}
}

Part 2: B=0B=0

Let's start by lower bounding the answer. If ii and jj are related then the answer must be at least lirjli−rj. Furthermore, for any pair of vertices ii and jj (not necessarily related), lirj2li−rj2 is a lower bound on the answer (consider the path i1ji↔1↔j).

So we know that

 

ansmax(maxi,j related(lirj),maxiliminiri2).ans≥max(maxi,j related(li−rj),⌈maxili−miniri2⌉).

As described in part 3, the wiwi can be chosen in such a way that equality holds, so printing the right-hand side of the above inequality is sufficient for half credit.

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T, B;
	cin >> T >> B;
	while (T--) {
		int N;
		cin >> N;
		vector<int> P(N + 1), L(N + 1), R(N + 1);
		for (int i = 2; i <= N; ++i) {
			cin >> P[i];
		}
		int ans = 0;
		vector<pair<int, int>> bounds(N + 1);
		pair<int, int> all_bounds{INT_MAX, INT_MIN};
		for (int i = 1; i <= N; ++i) {
			cin >> L[i] >> R[i];
			bounds[i] = {R[i], L[i]};
			all_bounds.first = min(all_bounds.first, bounds[i].first);
			all_bounds.second = max(all_bounds.second, bounds[i].second);
			if (i > 1) {
				bounds[i].first = min(bounds[i].first, bounds[P[i]].first);
				bounds[i].second = max(bounds[i].second, bounds[P[i]].second);
			}
			ans = max(ans, bounds[i].second - bounds[i].first);
		}
		ans = max(ans, (all_bounds.second - all_bounds.first + 1) / 2);
		cout << ans << "\n";
		if (B == 1) {
			for (int i = 1; i <= N; ++i) {
				if (i > 1) cout << " ";
				cout << L[i];
			}
			cout << "\n";
		}
	}
}

Part 3: B=1B=1

Define minR=min1iNriminR=min1≤i≤NrimaxL=max1iNlimaxL=max1≤i≤Nli, and mid=minR+maxL2mid=⌊minR+maxL2⌋. Then setting wi=max(min(mid,ri),li)wi=max(min(mid,ri),li) for all ii suffices.

Why does this work? If minRmaxLminR≥maxL then the answer is 00. Otherwise, observe that |wimid|maxLminR2|wi−mid|≤⌈maxL−minR2⌉ for all ii. Then for all (i,j)(i,j) such that ii and jj are related,

 

  • If max(wi,wj)midmax(wi,wj)≤mid, then |wiwj|maxLminR2ans|wi−wj|≤⌈maxL−minR2⌉≤ans by the observation.
  • Similar reasoning applies when min(wi,wj)midmin(wi,wj)≥mid.
  • The final case is when wi>midwi>mid and wj<midwj<mid. This means that wi=liwi=li and wj=rjwj=rj, so |wiwj|=lirjans|wi−wj|=li−rj≤ans.

Surprisingly, the complete solution ends up being only a few lines longer than the solution for part 1.

My code:

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T, B;
	cin >> T >> B;
	while (T--) {
		int N;
		cin >> N;
		vector<int> P(N + 1), L(N + 1), R(N + 1);
		for (int i = 2; i <= N; ++i) {
			cin >> P[i];
		}
		int ans = 0;
		vector<pair<int, int>> bounds(N + 1);
		pair<int, int> all_bounds{INT_MAX, INT_MIN};
		for (int i = 1; i <= N; ++i) {
			cin >> L[i] >> R[i];
			bounds[i] = {R[i], L[i]};
			all_bounds.first = min(all_bounds.first, bounds[i].first);
			all_bounds.second = max(all_bounds.second, bounds[i].second);
			if (i > 1) {
				bounds[i].first = min(bounds[i].first, bounds[P[i]].first);
				bounds[i].second = max(bounds[i].second, bounds[P[i]].second);
			}
			ans = max(ans, bounds[i].second - bounds[i].first);
		}
		ans = max(ans, (all_bounds.second - all_bounds.first + 1) / 2);
		int mid = (all_bounds.first + all_bounds.second) / 2;
		cout << ans << "\n";
		if (B == 1) {
			for (int i = 1; i <= N; ++i) {
				if (i > 1) cout << " ";
				cout << max(min(mid, R[i]), L[i]);
			}
			cout << "\n";
		}
	}
}

Danny Mittal's code:

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringJoiner;
import java.util.StringTokenizer;
 
public class BalancingARootedTreeSimpler {
 
    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());
        boolean needConstruction = tokenizer.nextToken().equals("1");
        while (t > 0) {
            --t;
            tokenizer = new StringTokenizer(in.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int[] parent = new int[n + 1];
            tokenizer = new StringTokenizer(in.readLine());
            for (int a = 2; a <= n; a++) {
                parent[a] = Integer.parseInt(tokenizer.nextToken());
            }
            int[] l = new int[n + 1];
            int[] r = new int[n + 1];
            int minR = Integer.MAX_VALUE;
            int maxL = 0;
            for (int a = 1; a <= n; a++) {
                tokenizer = new StringTokenizer(in.readLine());
                l[a] = Integer.parseInt(tokenizer.nextToken());
                r[a] = Integer.parseInt(tokenizer.nextToken());
                minR = Math.min(minR, r[a]);
                maxL = Math.max(maxL, l[a]);
            }
            int answer = 0;
            StringJoiner joiner = new StringJoiner(" ");
            int[] minChoice = new int[n + 1];
            int[] maxChoice = new int[n + 1];
            for (int a = 1; a <= n; a++) {
                int choice = Math.min(r[a], Math.max(l[a], (minR + maxL) / 2));
                minChoice[a] = a == 1 ? choice : Math.min(minChoice[parent[a]], choice);
                maxChoice[a] = a == 1 ? choice : Math.max(maxChoice[parent[a]], choice);
                answer = Math.max(answer, maxChoice[a] - minChoice[a]);
                joiner.add("" + choice);
            }
            System.out.println(answer);
            if (needConstruction) {
                System.out.println(joiner);
            }
 
        }
    }
}

[/hide]

翰林国际教育资讯二维码