This is the link to my solution:
https://www.codechef.com/viewsolution/45305900
I have commented on print statements. One can uncomment them which helps them debug the code. I’ve tried most of the unique input that came to my mind like multiple cycles in graphs, nodes pointing to themselves, cyclic graphs in an acyclic graph, hybrid of all yet I get WA.
There aren’t any submissions to this problem except mine. It’s an interesting question by isaf27.
Please read the problem before proceeding further.
Levels have been considered as nodes of the map and options to change levels as edges between them as weighted and directed. So it can be converted to a directed weighted map for easy visual
The program uses DFS to traverse all the nodes of the map and update its penalty.
First, dealing with cycles, a temp list is created which contains the path from node 1 to the current node along with the weights of each edge. so if there is a cycle, then comparing the node with the temp list, we’ll find redundancy.
Consider a node starting with node 1 till node n and let the penalty for node 1 be c and p1,p2,p3…on be the penalty for each edge corresponding to 1-2,2-3,3-4,…n-1 in the directed format.
Then it can be proved that the maximum penalty to reach node 1 is (2p1+4p2+8p3+16p4…+(2^n)*pn)/((2^n)-1)
A list of closed is also maintained to prevent traversing closed nodes again in the same manner, it’ll rather compare its current penalty with a new penalty and if new penalty is less, it’ll update its successor’s node with new penalty value which are closed and not updated yet(maintained by updated and closed list)