two coins problem in july 2017 long contest

general
, ,
1

Can anyone share their approach to solve Two coins problem in july 2017 contest?

2

I used dynamic programming with states dp[v][coin in v][coin in v's parent][coin in parent of v's parent] where v is a vertex and other variables are boolean and indicate if a coin is placed in the corresponding vertices.

4 Likes
3

Can you please explain more?? How did you filled it up? I tried to think of a dp solution but couldnt fill the table.

4

Take a look at my code here: https://www.codechef.com/viewsolution/14557685 it has some comments

5

@pkacprzak in the case of dp[v][1][0][0] how did you cover the possibility of v's child’s child having the coin which can be brought up to v in 2 moves? For this particular case I had to include a fifth term to the dp.

6

@vijju123 you can reason it out case by case. For example for dp[v][0][1][0] there is no coin at v but the parent has a coin, so you just need 1 child of v to have a coin. Hence you will need dp[x][1][0][1] for one child and min(dp[y][0][0][1], dp[y][1][0][1] for the rest of the children of v. The last 2 terms are [0][1] always because from the child’s perspective the parent v does not have a coin but the v's parent does. The best possible choice of x will give you the value to store at dp[v][0][1][0]. You can similarly solve the rest of the states.

1 Like
7

@meooow Let u be that child of v. I think that this case is covered automatically because we have to be able to move 2 coins to u somehow and at least one of these coins have to be brought from u’s subtree, which means that either u has a coin or at least one child of u has a coins. It follows that this coin can be moved up to the v in at most 2 moves. Does it make sense?

1 Like
8

my solution was a greedy sort of. I filled the nodes at each level starting from the lowest level. At each level when i filled nodes. i marked the nodes surrounding its to indicate they can gate a coin from that node.and whenever need to filled parent of parent.
My solution : https://www.codechef.com/viewsolution/14484060

1 Like
9

Oh yes, I get it, thanks :smiley:

1 Like
10

Thank you, @meooow and @pkacprzak .

11

Can the answer be -1 in some case other than a single node tree

12

No, because for n >=2 you can always place coins in all vertices and then each vertex has a coin and has also at least one adjacent vertex with a coin.

1 Like
13

If a node has no coin then there must be a coin in at least one of its children (from this follows that there must be a coin in every leaf).

Do DFS maintaining the following state for each node:

  • count - the number of coins in the subtree rooted at that node
  • s - whether there is a coin in the node (1, 0 otherwise)
  • d - whether it requires a coin from an ancestor (0 - no, 1 - parent or grandparent, 2 - parent)

Place a coin in the node if there are no children with a coin or if there is a child demanding a coin from its parent (that includes any demand passed from a grandchild).

Here is the


[1].

  [1]: https://www.codechef.com/viewsolution/14566668
2 Likes
14

Nice and simple!

15

I will not say this is good approach and may be I over complicated it but it was clearer approach atleast for me during contest. :slight_smile:

For Two Coins problem, You may see that leaves should definitely have a coin, and after that while moving towards root from leaf I tried to put a coin as late as possible depends on various conditions, During contest I had to insanely commented out my code to handle various conditions explicitly and to apply greedy type approach there. Here is my whole commented out solution, hope this will help:

https://www.codechef.com/viewsolution/14561922

If you see, during recursion my base condition was leaf node, and I used 6 type of variables(Made it little complicated but it was clear for me though):

Help that can be provided from one level children (directly connected)
Help that can be provided from two level children (children of children)
3,4. Flexible Help(That can be delayed to further to above parent of parent) needed by one level children and two level children seperately

5,6. Hard Help(That can not be delayed to further to above parent of parent) needed by one level children and two level children

After this you can see how I used these variables in recursion to pass help and requirement by children.

Hope this will help.