STICNOT - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Abolfazl Soltani
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

DIFFICULTY:
MEDIUM
PREREQUISITES:
Greedy algorithms, binary search
PROBLEM:
You’re given a tree with N vertices. There’s number a_i written on its i-th vertex and number b_j written on its j-th edge for all valid i and j. You want the condition a_v \geq b_e to be satisfied for each vertex v and its adjacent edge e. You may do the following:

  1. Swap a_u and a_v for some vertices u and v,
  2. Swap b_e and b_f for some edge e and f,
  3. Change a_v to x and pay one coin.

You have to make the tree satisfy the condition with least possible amount of coins spent.
QUICK EXPLANATION:
Utilize binary search on the answer. To check if it’s possible to fill the condition with only k coins used, check that b_{i} \leq a_{i+k} holds for every reasonable i, where a_i and b_j are sorted ascendingly.
EXPLANATION:
First observation should be that if we change the value a_v then we obviously should choose it in such a way that it will be surely bigger than any number b_e, which may be achieved, for example, by taking maximum value b_i among all edges, that is, x=\max(b_1, \dots, b_{N-1}).

Thus we may make binary search over number of coins we spend which would reduce the problem to the one in which we only have to determine if we can rearrange a_i and b_j in such a way that needed condition is satisfied. There are several more observations we should do to solve this new version of a problem.

Let’s utilize the fact that we’re given the tree structure. Since it’s a tree we may determine any edge of the tree by some vertex v and its parent p_v. We may consider some topological sort of tree vertices (for example, the one obtained via depth-first search) and rearrange a_i on it in descending order. In this way a_v will always be not greater than a_{p_v} thus the edge between them is only determined by a_v and not a_{p_v}. This appears to deliver optimal constraints on b_j values, which may be rigorously proven by somewhat tedious mathematical induction.

In this way, all values a_i except for the maximum one will put exactly one bound on some b_j value. So, if (a_1, a_2, \dots, a_n) is the sequence a_i sorted in ascending order then actual constraints on b_j may be obtained as b_j \leq a_{j} for any j from 1 to N-1. The other observation we should make here is that if we are to change k values of a_i, we should always change k least values as they are the most binding ones. So, to check if it is enough to change exactly k values of a_i we should simply check that b_j \leq a_{j+k} is satisfied for each reasonable i. That gives us the solution:

void solve() {
	... // reading the input here
	sort(b, b + N - 1);
	sort(a, a + N);
	int L = -1, R = N - 1;
	while(R - L > 1) { // binary search part
		int M = (L + R) / 2;
		bool ok = true;
		for(int i = 0; i + max(1, M) < N; i++) {
			ok &= b[i] <= a[i + M];
		}
		if(ok) {
			R = M;
		} else {
			L = M;
		}
	}
	cout << R << "\n";	
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

1 Like