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

×

JULY LONG CHALLENGE 2017 PROBLEM DISCUSSION

Can someone discuss the solution of Tree Expectancy , Pishty and tree and Two Coins ?

asked 17 Jul '17, 18:23

tihorsharma123's gravatar image

2★tihorsharma123
49718
accept rate: 15%


link

answered 17 Jul '17, 23:00

saumyadip's gravatar image

3★saumyadip
662
accept rate: 50%

For Two Coins problem, You may see that leaves should definitely have a coin, and after that while moving towars 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):

  1. Help that can be provided from one level children (directly connected)
  2. 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.

link

answered 17 Jul '17, 22:51

kauts_kanu's gravatar image

5★kauts_kanu
1.1k110
accept rate: 19%

edited 18 Jul '17, 17:59

@tihorsharma123 Editorial for TWOCOINS.

link

answered 18 Jul '17, 14:52

nitksubbu's gravatar image

4★nitksubbu
761
accept rate: 25%

@kauts_kanu In this problem (TWO COINS), will a node with a lower number will always be the parent of the node with a higher number?

link

answered 18 Jul '17, 12:18

vis_24_hal's gravatar image

3★vis_24_hal
123
accept rate: 20%

edited 18 Jul '17, 12:19

2

Nope, That's not necessary.. I will say, Don't assume anything until it's mentioned in question specifically.. Btw, Why are you asking this? It will not be required anywhere as we are using dfs using recursion and using node numbers just to identify root node specifically and to track visited nodes.

(18 Jul '17, 17:57) kauts_kanu5★

Editorial for Phisty and Trees anyone ?

link

answered 18 Jul '17, 17:30

arghya_tiger's gravatar image

3★arghya_tiger
1
accept rate: 0%

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:

×158

question asked: 17 Jul '17, 18:23

question was seen: 828 times

last updated: 18 Jul '17, 19:05