Solve Balanced Permutations and Tree Reversals

You have 90 minutes to solve the following two independent coding problems.

Problem 1: Balanced Prefix Values in a Permutation

You are given a permutation p of the integers 1 through N.

For each k from 1 to N, consider the positions in p of the values 1, 2, ..., k. Determine whether these k elements occupy one contiguous segment of the original array.

Return a binary string ans of length N, where:

• ans[k - 1] = '1' if the positions of values 1 through k are contiguous in p.
• ans[k - 1] = '0' otherwise.

Example

If p = [4, 1, 3, 2]:

• For k = 1, value {1} appears contiguously, so output 1.
• For k = 2, values {1, 2} are at positions 2 and 4, not contiguous, so output 0.
• For k = 3, values {1, 2, 3} are at positions 2, 3, 4, contiguous, so output 1.
• For k = 4, all values occupy the whole array, so output 1.

The result is 1011.

Problem 2: Minimum Edge Reversals to Root a Directed Tree

You are given a directed graph with N nodes and N - 1 directed edges. If edge directions are ignored, the graph forms a tree.

You may choose any node as the root. After choosing the root, every edge must point away from the root, meaning every directed edge should go from a parent to a child in the rooted tree.

If an edge points in the wrong direction, you may reverse it. Find the minimum possible number of edge reversals over all choices of the root.

Example

Suppose the directed edges are:

1 -> 2
3 -> 2
3 -> 4

If node 3 is chosen as the root, the edges should point away from 3:

3 -> 2
3 -> 4
2 -> 1

Only edge 1 -> 2 must be reversed, so the answer is 1.

Part 1: Balanced Prefix Values in a Permutation

You are given a permutation p of the integers 1 through N. For every k from 1 to N, look at the positions of the values 1, 2, ..., k inside p. If those positions form exactly one contiguous segment of the array, then the k-th answer bit is '1'; otherwise it is '0'. Return the full binary string of length N.

Constraints

• 1 <= N <= 2 * 10^5
• p is a permutation of 1..N
• The solution should run in linear time

Examples

Example 1

Input: [4, 1, 3, 2]
Output: '1011'

Explanation: Positions of 1,2,3,4 are 2,4,3,1 in 1-based indexing. The sets for k=1,2,3,4 are contiguous, not contiguous, contiguous, contiguous.

Example 2

Input: [1, 2, 3, 4]
Output: '1111'

Explanation: Each prefix of values already occupies the first k positions.

Hints

1. Instead of scanning the permutation for each k, first compute where each value appears.
2. For values 1..k, they are contiguous exactly when max_position - min_position + 1 == k.

Part 2: Minimum Edge Reversals to Root a Directed Tree

You are given N nodes and N - 1 directed edges. If edge directions are ignored, the graph is a tree. You may choose any node as the root. After choosing a root, every edge must point away from the root, from parent to child. You may reverse edges that point the wrong way. Return the minimum number of reversals needed over all possible root choices.

Constraints

• 1 <= n <= 2 * 10^5
• len(edges) == n - 1
• If directions are ignored, the graph formed by edges is a tree
• Node labels are integers from 1 to n

Examples

Example 1

Input: (4, [(1, 2), (3, 2), (3, 4)])
Output: 1

Explanation: Choosing node 3 as root requires only reversing edge 1 -> 2 into 2 -> 1.

Example 2

Input: (1, [])
Output: 0

Explanation: Edge case: a single node has no edges, so no reversals are needed.

Hints

1. First, fix an arbitrary root such as node 1 and count how many edges are wrong for that root.
2. When you move the root across one edge, the total answer changes by exactly +1 or -1 depending on that edge's original direction.