PROBLEM LINK:
Author: admin3
Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
You have a rooted tree of N nodes, you can place at most one coin in each node. Find a strategy with minimum number of coins, such it’s possible to gather 2 coins in each node by performing at most 2 operations. In each operation you can move 1 coin from a node to one of its adjacent neighbors. There is a condition you must follow. If you use your 2 operations on the same coin, then the movement must be done in one direction ,either towards the root or away from the root.
EXPLANATION:
There is always a solution for any tree except trees consisting of a single node.
The problem smells like a Dynamic Programming on tree problem. It can be solved with many different recursive functions (with memorization of course). Let’s tell some observations which lead us to a simple function.
Observation 1: We must place one coin in each leaf (nodes without children). Also, either the parent of a leaf, or the second ancestor (parent of the parent) of a leaf must have a coin. For simplicity, let’s denote nodes with coins by black nodes and nodes without coins by white nodes.
Observation 2: Each white node must have at least 2 adjacent (nodes connected directly by one edge) black nodes.
A function that solves this problem efficiently:
dp[Node][Color][ParentColor][SecAncestorColor]
This function returns the minimum number of coins we need to construct a valid configuration of the subtree rooted at node Node providing that its color must be Color and its parent is colored ParentColor and its second ancestor (parent of the parent) is colored SecAncestorColor. (Please note that we only care about the second’s ancestor color when processing leaves).
Processing black nodes is quite easy, it doesn’t matter how we color the children of a black node. According to our second observation each white node will have a black node within a distance of 1 edge, so gathering 2 coins would be always possible if our assumption is satisfied.
Let’s get to white nodes, if the parent is black we must have at least one child colored, otherwise we must have at least 2. It’s another (sub)-Dynamic Programming problem we should solve for each white node we process. For each child we have 2 choices either to have it black or white (and each choice has its cost) and we want to pick at least two/one black children with minimum total cost.
You can check my implementation for details.
This solution runs in O(N)
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: Can be found here
TESTER’s solution: Can be found here
EDITORIALIST’s solution: Can be found here
