TREEVERS Editorial

PROBLEM LINK:

Practice
Contest

Author: Erfan AliMohammadi
Tester & Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

You are given a rooted tree with N nodes (numbered 1 through N); the root is node 1. For each valid i, node i has weight w_i, which is either 0 or 1.

We want to traverse the tree using depth-first search. The order in which the nodes are visited is not uniquely defined, since we may visit the children of each node in an arbitrary order. At the moment we enter a node, we immediately append its weight to our special sequence.

Find a DFS order that would yield a special sequence with minimum inversions possible.

DIFFICULTY:

Easy-Medium

CONSTRAINTS

(1 \leq n \leq 10^5)

PREREQUISITES:

Graph Theory

QUICK EXPLANATION:

Let’s solve each subtree and assume that the root of some random subtree is x. Note that we need to solve each child of x separately and find the best value for its subtree. After that for merging them to form the DFS-order of subtree rooted at x, sort them using a comparator that takes 2 roots (P,Q) as arguments and checks if its better to concatenate DFS sequence of P then Q or vice versa and picks the choice with less inversions.

EXPLANATION:

First of all, we need to run a DFS to find the number of zeroes as well the number of ones in each subtree.

The DFS sequence of a subtree rooted at a random node is made of the concatenation of children sequences in some order we need to figure. So note here that the inner inversions inside each of these smaller sequences would remain the same no matter how we order these sequences while forming the sequence of the parent. What we are adding as a penalty is the mutual effect of sequences on each other.

This leads us to a dynamic programming approach (you can call it so actually).
When solving a subtree rooted at x let’s solve all children subtrees and find their optimal sequences and then find a way to order them.

To order children of a subtree’s root, we are going to use a classic greedy comparator. Let’s imagine that we have 2 children of our current root (p,q)
We would put p before q in the sequence if and only if:

ones_p*zeroes_q<zeroes_p*ones_q

which means check inversions if we put p then q and vice-versa and pick the cheapest scenario. This comparator is intuitive and self explanatory.

The proof behind it is that it maintains transitivity (a \leq b \leq c) implies (a \leq c) read here

So we already know the number of zeroes and ones in each subtree, all we need to do when processing a certain subtree root is to sort the children with this comparator and then concatenate them and conclude with final result.

Our final answer would be the dp_1

Check implementation for details.

AUTHOR’S AND TESTER’S SOLUTIONS:

EDITORIALIST’s solution: Can be found here

7 Likes

Is it right to call it a DP problem? For sure, it has the Optimal Substructure but no Overlapping Subproblems. Also, for the comparisons, can’t we simply assume the sequence at each subtree a binary substring, then the result will be the Lexicographically smaller of the two string p + q or q + p?

It doesn’t really matter what do you want to call it. DP on trees problems in general look the same as this one. Solve for each subtree and combine results and still classified as “DP on trees”

1 Like

why was the meaning of inversion not mentioned in the problem statement It thought it was the number of elements such that ai is not equal to a[i+1] for 1<=1<=n-1

Otherwise I knew how to solve this question

2 Likes

Because google search exists and “inversion in array” gives what you want…

Yes, I agree with @kshitij_789 the definition of inversion must be stated by the setter!