shubhinanugullu's blog

Efficiently find maximum XOR on a graph
By shubhinanugullu, history, 10 years ago, In English

We are given an undirected graph G = (V, E), |V| ≤ 50. We are also given a starting vertex s. Each vertex v of the graph is associated with a natural number Nv. Initiall our profit is R = Ns.

Now we have to traverse the graph beginning from s in an order. We can visit each vertex or edge an number of times.Whenever we reach a vertex v, R = R XOR Nv. (Note that if we visit a vertex v k times, then we will XOR with Nv k times.

Find the maximum value of R that can be obtained while traversing G.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

Try this one: https://csacademy.com/contest/beta-round-6/#task/xor_cycle

What does a "traversal" mean in this context?

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This one http://codeforces.com/contest/724/problem/G is also similar to what you ask. Only in this you have to find sum of all possible values, not the maximal one.

→ Reply