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.