Maximum Magic Walk - Editorial

Problem Link:

Author: sumeet-varma

Tester: amankedia1994

Editorialist: sumeet-varma



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


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.