Problem Link: Author: sumeetvarma Difficulty: Prerequisites:  Dynamic Programming, Graphs Problem: Find a walk in the graph for which following magic function is maximized. Quick Explanation: Build a directed graph on DP states Explanation: Constrains are low enough to think of a DP solution.
Let’s think about a possible DP solution. Let's define, DP[i][prevEdge][currMagic] = maximum magic which can be achieved if we are currently at vertex u with previous edge = prevEdge and magic on path till now = currMagic DP[u][prevEdge][currMagic] = currMagic; // if we decide to end ‘walk’ here, magic we get = currMagic And for all edges (u,v,c), DP transition is, Final Ans = for ‘i’ in 1 to n: max DP[i][0][0]. We may think that we have a possible DP solution but it isn’t the case. Think Why? Because this DP has cycles in it. So we can’t compute this DP in a simple way. If we do, it will end up in infinite loop or wrong answer depending on implementation. Note: This DP is just a memoized version of an infinite recursive code. We have a DP recurrence, but it can’t be computed. Let’s look at DP from a completely different point of view. Let’s build a directed graph on DP states. Vertices in this graph would represent DP states. Edges in this graph would represent DP transitions. There would also be cycles in this graph. Now for any edge (u,v,c) in input, We add 'directed unweighted’ edge from vertex (u, prevEdge, currMagic) to vertx (v,c,currMagic ^ (prevEdge & c)) for all prevEdge = 0 to 100 and curr = 0 to 127. Similarly, we add directed edge from (v,prevEdge,currMagic) to (u,c,currMagic ^ (prevEdge & c)) for prev = 0 to 100 and all curr = 0 to 127. This edges show DP transitions. Number of nodes in this new graph = n * 101 * 128 We have to stop our walk somewhere. We can say that if our finalAns = ans, then we would end our DP transistions at DP[j][x][ans] for some j and x. Hence in this new graph, for each i from 1 to n, we need maximum ‘ans’ value such that DP[j][x][ans] is reachable from DP[i][0][0] for some j and x. It means that there is a walk from vertex i to vertex j with last edge = x and magic on that path = ans. Final Ans = max of all those ‘ans’ values. To accomplish this we can do a multisource dfs/bfs from all DP(i,0,0) vertex where i = 1 to n. Then final ans would be maximum magic such that vertex DP(j,x,magic) is visited during dfs/bfs for arbitrary j and x. Complexity: $O(100 * 128 * (N + M))$ This was allowed to pass but we can still do better. DP[u][pevEdge][currMagic] is our DP state. Now there are only M edges in input. Each pair (u,prevEdge) belongs to atleast one of those m edges. Hence, we can optimize our DP to be DP2[indexOfLastEdge][currMagic] where 2 comes to distinguish between (u,prevEdge) and (v,prevEdge) where, (u,v) are connected by edge with index = 'indexOfLastEdge'. After this we can use the same directed graph and dfs conecept to find answer. In Short: Build a directed graph on DP states to compute them without getting stuck in infinite loop.
This question is marked "community wiki".
asked 25 Nov '15, 05:00
