Can someone discuss the solution of Tree Expectancy , Pishty and tree and Two Coins ?
3 Likes
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):
- 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.
3 Likes
expression tree editorial is here @tihorsharma123 https://discuss.codechef.com/questions/105248/exptree-editorial 
4 Likes
@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?
Editorial for Phisty and Trees anyone ?
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.
2 Likes