Home » 国际竞赛 » Details

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

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

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? $N$ ?( $2 \leq N \leq 10^{5}$ ) nodes labeled? $1 \dots N$ , each node corresponding to a cow breed. For each? $i \in [2, N]$ , the parent of node? $i$ ?is node? $p_{i}$ ?( $1 \leq p_{i} < i$ ), meaning that breed? $i$ ?evolved from breed? $p_{i}$ . A node? $j$ ?is called an ancestor of node? $i$ ?if? $j = p_{i}$ ?or? $j$ ?is an ancestor of? $p_{i}$ .

Every node? $i$ ?in the tree is associated with a breed having an integer number of spots? $s_{i}$ . The "imbalance" of the tree is defined to be the maximum of? $| s_{i} - s_{j} |$ ?over all pairs of nodes? $(i, j)$ ?such that? $j$ ?is an ancestor of? $i$ .

Farmer John doesn't know the exact value of? $s_{i}$ ?for each breed, but he knows lower and upper bounds on these values. Your job is to assign an integer value of? $s_{i} \in [l_{i}, r_{i}]$ ?( $0 \leq l_{i} \leq r_{i} \leq 10^{9}$ ) to each node such that the imbalance of the tree is minimized.

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

The first line contains? $T$ ?( $1 \leq T \leq 10$ ), the number of independent test cases to be solved, and an integer? $B \in {0, 1}$ .Each test case starts with a line containing? $N$ , followed by? $N - 1$ ?integers? $p_{2}, p_{3}, \dots, p_{N}$ .

The next? $N$ ?lines each contain two integers? $l_{i}$ ?and? $r_{i}$ .

It is guaranteed that the sum of? $N$ ?over all test cases does not exceed? $10^{5}$ .

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

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

If? $B = 1,$ ?then print an additional line with? $N$ ?space-separated integers? $s_{1}, s_{2}, \dots, s_{N}$ ?containing an assignment of spots that achieves the above imbalance. Any valid assignment will be accepted.

SAMPLE INPUT:

SAMPLE OUTPUT:

3
1
4

For the first test case, the minimum imbalance is? $3$ . One way to achieve imbalance? $3$ ?is to set? $[s_{1}, s_{2}, s_{3}] = [4, 1, 7]$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

This input is the same as the first one aside from the value of? $B$ . Another way to achieve imbalance? $3$ ?is to set? $[s_{1}, s_{2}, s_{3}] = [3, 1, 6]$ .

SCORING:

Test cases 3-4 satisfy? $l_{i} = r_{i}$ ?for all? $i$ .
Test cases 5-6 satisfy? $p_{i} = i - 1$ ?for all? $i$ .
Test cases 7-16 satisfy no additional constraints.

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

Problem credits: Andrew Wang

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

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Say that? $i$ ?and? $j$ ?are related if? $i$ ?is an ancestor of? $j$ ?or vice versa. Let? $ans$ ?denote the minimum possible imbalance.

Part 1:? $l_{i} = r_{i}$

Here? $w_{i}$ ?is fixed for all? $i$ . To calculate? $ans$ , we can compute for every node? $i$ ?the minimum? $w_{j}$ ?and maximum? $w_{j}$ ?over all ancestors? $j$ ?of? $i$ ?as well as? $j = i$ . This can be done in? $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 = 0$

Let's start by lower bounding the answer. If? $i$ ?and? $j$ ?are related then the answer must be at least? $l_{i} - r_{j}$ . Furthermore, for any pair of vertices? $i$ ?and? $j$ ?(not necessarily related),? $\frac{l_{i} - r_{j}}{2}$ ?is a lower bound on the answer (consider the path? $i \leftrightarrow 1 \leftrightarrow j$ ).

So we know that

ans \geq max (max i, j ?related (l i ? r j), ? max i l i ? min i r i 2 ?) .

As described in part 3, the? $w_{i}$ ?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 = 1$

Define? $minR = min_{1 \leq i \leq N} r_{i}$ ,? $maxL = max_{1 \leq i \leq N} l_{i}$ , and? $mid = ⌊ \frac{minR + maxL}{2} ⌋$ . Then setting? $w_{i} = max (min (mid, r_{i}), l_{i})$ ?for all? $i$ ?suffices.

Why does this work? If? $minR \geq maxL$ ?then the answer is? $0$ . Otherwise, observe that? $| w_{i} - mid | \leq ⌈ \frac{maxL - minR}{2} ⌉$ ?for all? $i$ . Then for all? $(i, j)$ ?such that? $i$ ?and? $j$ ?are related,

If? $max (w_{i}, w_{j}) \leq mid$ , then? $| w_{i} - w_{j} | \leq ⌈ \frac{maxL - minR}{2} ⌉ \leq ans$ ?by the observation.
Similar reasoning applies when? $min (w_{i}, w_{j}) \geq mid$ .
The final case is when? $w_{i} > mid$ ?and? $w_{j} < mid$ . This means that? $w_{i} = l_{i}$ ?and? $w_{j} = r_{j}$ , so? $| w_{i} - w_{j} | = l_{i} - r_{j} \leq 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]