You are not logged in. Please login at www.codechef.com to post your questions!

×

TWOCOINS - Editorial

3
2

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

This question is marked "community wiki".

asked 18 Jul '17, 10:11

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 22 Jul '17, 20:29

hikarico's gravatar image

5★hikarico
1.9k1515

Solutions of Author and Editorialist are not visible.

(18 Jul '17, 19:30) codedecode01115★

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.

link

answered 18 Jul '17, 15:05

nitksubbu's gravatar image

4★nitksubbu
761
accept rate: 25%

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

(18 Jul '17, 18:07) avi2244★

Haha, it happens :)

(18 Jul '17, 18:48) vijju123 ♦♦5★
link

answered 18 Jul '17, 23:41

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

Can you explain the observations?

link

answered 02 Aug '17, 17:27

mathecodician's gravatar image

6★mathecodician
2.6k11034
accept rate: 7%

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

link

answered 18 Jul '17, 15:52

rj25's gravatar image

4★rj25
2305
accept rate: 0%

edited 18 Jul '17, 15:54

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

link

answered 19 Jul '17, 14:13

dasswapnil96's gravatar image

1★dasswapnil96
1
accept rate: 0%

hahaha lol

(21 Jul '17, 02:57) sonu_6284★

Thanks for pointing it out. Fixed it

(22 Jul '17, 20:31) hikarico5★

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

link

answered 19 Jul '17, 22:17

hotspur's gravatar image

1★hotspur
1
accept rate: 0%

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.

(19 Jul '17, 22:21) vijju123 ♦♦5★

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.

link

answered 20 Jul '17, 05:41

raghavsood98's gravatar image

3★raghavsood98
11
accept rate: 0%

@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])

(20 Jul '17, 17:40) sanket4074★

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.

(20 Jul '17, 17:40) sanket4074★

@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) raghavsood983★

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

(22 Jul '17, 19:48) raghavsood983★

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

link

answered 20 Jul '17, 09:28

kr_abhinav's gravatar image

6★kr_abhinav
1213
accept rate: 20%

edited 20 Jul '17, 09:30

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,214
×1,723
×229
×115
×15

question asked: 18 Jul '17, 10:11

question was seen: 2,326 times

last updated: 02 Aug '17, 17:27