PROBLEM LINK:Author: admin3 DIFFICULTY:EasyMedium 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
This question is marked "community wiki".
asked 18 Jul '17, 10:11

More discussion: https://discuss.codechef.com/questions/105381/twocoinsprobleminjuly2017longcontest answered 18 Jul '17, 23:41

I might be not understanding problem correctly, but I think question was not explained properly. It was not given that for a "particular coin we can move it at most 2 times" either away or towards root. Question seemed ambiguous (atleast for me). answered 18 Jul '17, 15:52

Can you explain the part where we encounter a white node, what is supposed to be done algorithmically( subdp part). I saw the editorialists' solution and there is an array dp[2][3] along with the variables cur and take. I don't understand how this array has been used to calculate the answer for a white node. answered 20 Jul '17, 05:41
@raghavsood Consider the foll. dp[N][k] = min. cost of coloring k black nodes from first N children of curr node. for each i from 1 to No. of children, dp[i][0] = min(dp[i1][0] + cost of coloring ith child white, dp[i][0]) dp[i][1] = min(dp[i1][0] + cost of coloring ith child black , dp[i1][1] + cost of coloring ith child white, dp[i][1])
(20 Jul '17, 17:40)
All these dp subproblems are solved by double for loop. Looking at editorialist solution, 'cur' stands for no. of black nodes selected till prev child and 'take' stand for color choice of curr child. Note that at ith child iteration we use only i1 th child dp values. So we can optimize memory requirements by alternately filling in dp[0][i] and dp[1][i]. Phase is used for just that.
(20 Jul '17, 17:40)
@sanket407 Thanks for explaining the part of coloring children.Thats what I had also thought earlier,but I thought it would take more time than necessary. But I still didnt get how is phase used and also why is the size of array used 2*3
(22 Jul '17, 19:45)
I think 3 is for 0 no child filled,1 one child filled, and 22 children filled If you could explain the part with phase a little bit more in detail, it would be helpful
(22 Jul '17, 19:48)

The problem can be solved using 3D DP as well, without considering second ancestor except for leaf case. I've explained my solution here answered 20 Jul '17, 09:28

Solutions of Author and Editorialist are not visible.