PARTMIN - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Binary search

PROBLEM:

You’re given a tree with N vertices, and vertex values in [0, N].
You must fill in the 0's of A to obtain a permutation of [1, N].

The score of a permutation is defined as follows:

  • Let S denote the set of all path minimums of the tree, when considering only paths with at least two vertices.
  • The score of the permutation is then the smallest positive integer that’s not in S.

Find the minimum possible score of A.

EXPLANATION:

To begin, we need to figure out how to compute the score of a tree with all its values fixed (after all, we’ll need to do exactly this if there are no zeros in A).

This begs the question: when exactly can there exist a path with its minimum being the value x?

This turns out to have a pretty simple answer.

First, note that each value appears exactly once in the tree.
So, let’s look at the single occurrence of value x, say at vertex u so that A_u = x.
Now,

  • If u has some neighbor v such that A_v \gt A_u, the path (u, v) already has a minimum of x.
  • If the first case doesn’t happen, it means every neighbor of u has a smaller value than x.
    In this case, it’s impossible for any path to have a minimum of x: after all, any path (of length at least 2) including vertex u must include at least one neighbor of u as well, so that the minimum on the path will surely be \lt x.

This gives us a very simple criterion.

x can be a path minimum (of a non-trivial path) if and only if at least one neighbor of the vertex having value x, has a value larger than x.

So, the score of an array is the smallest integer x for which this condition is not true, that is, the smallest x for which every neighbor of value x is smaller than x.

Let’s use this observation to solve the problem.

Our goal now is to obtain the smallest possible value x such that we can place x at some vertex, and make all the neighbors of this vertex be \lt x.

Consider some vertex u. We’ll try to figure out the optimal x for this u.
There are two possibilities: either A_u = 0 or A_u is already assigned.

First, suppose A_u is already assigned.
Then, our only choice for this vertex is to try and make all its neighbors have values \lt A_u.
For this to be possible:

  1. There should not be an existing neighbor with value \gt A_u.
  2. Suppose there are K neighbors of A_u which don’t have values yet.
    Then, our best hope is to fill these K neighbors with the smallest K missing values.
    So, the K-th missing value must be \lt A_u as well.
    If both conditions are satisfied, A_u is a candidate for the answer, otherwise it isn’t.

Next, suppose A_u = 0.
Just as before, let there be K neighbors of u that don’t have values yet.
Then,

  1. We place the K smallest missing values in A at the neighbors of u.
    u itself must receive the next smallest value possible - which is the (K+1)-th missing value.
  2. However, A_u must also be larger than all its existing neighbors.
    So, we instead take the maximum of the (K+1)-th missing value, and whichever missing value is strictly greater than the largest neighboring value of u.
    The latter can be found using binary search.

This way, we’re able to find the best answer for each vertex.
The final answer is the minimum of the answers for each vertex; obviously this is achievable and we cannot do better.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
import bisect
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    adj = [ [] for _ in range(n) ]
    for i in range(n-1):
        u, v = map(int, input().split())
        adj[u-1].append(v-1)
        adj[v-1].append(u-1)
    
    mark = [0]*(n+1)
    for x in a: mark[x] = 1
    missing = [0]
    for i in range(1, n+1):
        if not mark[i]: missing.append(i)
    
    ans = n
    for u in range(n):
        mx, k = 0, 0
        for v in adj[u]:
            mx = max(mx, a[v])
            k += a[v] == 0
        if a[u] > 0:
            # if mx < a[u] and k-th missing number is < a[u], yes
            if mx < a[u] and missing[k] < a[u]: ans = min(ans, a[u])
        else:
            # place k smallest missing numbers on neighbors
            # either (k+1)-th missing number, or smallest missing number > mx is the best we can do
            if missing[-1] < mx: continue

            lo = bisect.bisect_left(missing, mx + 1)
            ans = min(ans, max(missing[lo], missing[k+1]))
    print(ans)
1 Like