My approach, did a DFS on the tree, and built it from the leaves, assigning coins starting from the leaves as we go up.
- Every leaf gets a coin.
- Parent coins were assigned greedily, such that every alternate node gets a coin (in case of a single chain).
- States were given to see priorities in order of deciding when to give a coin, and states were passed by the children to the parents, not vice-versa.
- State 1 denotes that this node gets a coin.
- State 2 denotes that this is the parent of a node which has a coin, so we can leave out this one and the parent of this node will surely have to have a coin i.e. parent of any node with state 2 gets State 1 automatically.
- If root has state 2, it will only get a coin if it has only 1 child.
- For considering special cases where root might be the parent of a branch containing only 1 node, the parent of every leaf gets State 3 (same rules except State 2, just that if root has State 3, it will get a coin irrespective of how many children it has.)
My solution link : https://www.codechef.com/viewsolution/14524494
My solution gives WA on every single Test case. Can I please know the flaws in my logic, and any counter case which this code fails ? I’d really appreciate the help 