PROBLEM LINK:
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