TWOCOINS - Editorial

PROBLEM LINK:

Practice
Contest

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

3 Likes

Tester’s solution gives 3 for the input

1

3

1 2

2 3

But I think it is enough to place coins at nodes 1 and 3.

5 Likes

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).

More discussion:
https://discuss.codechef.com/questions/105381/two-coins-problem-in-july-2017-long-contest

1 Like

Practice link leads to contest page and contest link points to practice page. @admin you might want to change that.

when would be the output -1? could anyone give a test case?

Can you explain the part where we encounter a white node, what is supposed to be done algorithmically( sub-dp 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.

The problem can be solved using 3-D DP as well, without considering second ancestor except for leaf case. I’ve explained my solution here

Can you explain the observations?

1 Like

@vijju123 my bad, thanks for pointing out. The output is 2.

Haha, it happens :slight_smile:

Solutions of Author and Editorialist are not visible.

When N=1. Since if there is only 1 nodes, you can place at max a total of 1 coin, so its impossible to get 2 coins on it.

@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[i-1][0] + cost of coloring ith child white, dp[i][0])
dp[i][1] = min(dp[i-1][0] + cost of coloring ith child black , dp[i-1][1] + cost of coloring ith child white, dp[i][1])

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 i-1 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.

hahaha lol

@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

I think 3 is for 0- no child filled,1- one child filled, and 2-2 children filled
If you could explain the part with phase a little bit more in detail, it would be helpful

Thanks for pointing it out. Fixed it

How is the output 3 for this test case

1
4
1 2
2 3
3 4