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]