You are not logged in. Please login at www.codechef.com to post your questions!

×

Maximum Magic Walk - Editorial

3
1

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 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.
New Complexity : $O(2 * M * 128)$.

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

sumeet_varma's gravatar image

7★sumeet_varma
1458
accept rate: 20%

edited 26 Nov '15, 12:33

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,214
×1,236
×734
×50
×46

question asked: 25 Nov '15, 05:00

question was seen: 2,262 times

last updated: 26 Nov '15, 12:33