Problem Link:
Contest
Practice
Author: sumeet-varma
Tester: amankedia1994
Editorialist: sumeet-varma
Difficulty:
Medium
Pre-requisites: - Dynamic Programming, Graphs
Problem: Find a walk in the graph for which following magic function is maximized.
Magic (path) = (C1 & C2) ^ (C2 & C3) ^ … ^ (C3 & C4) ^ (Cn-1 & Cn).
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.
If we move from kth edge to k+1th edge, new magic = magic ^ (kth edge & k+1th edge). Thus we need to remember last edge as well as curr magic in our walk for DP to work correctly.
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,
DP[u][prevEdge][currMagic] = max( DP[u][prevEdge][currMagic] , DP[v][c][currMagic ^ (prev & c) ] );
// last edge in the walk becomes c now
// currMagic = currMagic ^ (prev & c)
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
Number of edges = m * 2 * 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 multi-source 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 DP[2][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.
New Complexity : O(2 * M * 128).
In Short: Build a directed graph on DP states to compute them without getting stuck in infinite loop.