Problem Link: contest, practice
Difficulty: Easy-Medium
Pre-requisites: DFS, BFS, Bipartite Graphs, Graph Traversal
Problem:
Given a graph G with non-negative values Yj assigned to the edges.
Your task is to find the K’th lexicographically valid sequence (X1, X2, …, XN) that satisfies to the following condition:
Let’s suppose that the j’th edge of G connects vertices Uj and Vj. Then, a non-negative integer Yj equals to XUj xor XVj.
Explanation:
Let’s assume, that all the values of Xi and Yj belong to {0, 1}. If it’s not true, then we can consider all the bits seperately(since we are working with XOR operation) and reduce the problem to the case, when all the values of Xi and Yj belong to {0, 1}. Let’s also assume, that G is connected(otherwise, we can solve the problem in each connected component seperately).
Let’s consider some valid sequence (X1, X2, …, XN). The given graph G is bipartite and divided into two parts: if Xi = 0, then i’th vertex of G belongs to the first part of G, otherwise it belongs to the second part.
What about edges? Let’s suppose that the j’th edge of G connects vertices Uj and Vj. Then, if Yj = 0, then Uj and Vj belong to the same part of G, otherwise they belong to different parts. It means, that if we know the value XUj, then XVj = XUj xor Yj.
So, let’s build up an algorithm of finding the least lexicographically valid sequence (X1, X2, …, XN):
- Assigning X1 = 0;
- Starting BFS(or DFS) from the first vertex;
- Calculating the values of Xi while moving along the edges( Xconnected with known = Xknown xor Ythe edge between the current vertices ).
If we have faced some contradictions during the algorithm(i.e. XV should be both 0 and 1 for some vertex V), then there is no valid sequence (X1, X2, …, XN) at all, otherwise it’s found by our algorithm.
As was said before, we can run this algorithm for every bit of Yj’s( there are at most 31 of them ) and then merge the results. It’s important to note, that for different bits there could be different partitions of G(i.e. the same vertex V could belong to the first part of G while processing the first bit of Yj’s and belong the second part of G while processing the second bit of Yj’s), but that’s OK since there’s no limits for that.
Ok, we have just considered an O( (N + M) × log2Y ) algorithm of finding the least lexicographically valid sequence (X1, X2, …, XN), but we can do better.
Let’s solve the problem for all the bits simultaneously, doing exactly the same algorithm as described above. If we have faced some contradictions during the algorithm(i.e. XV should be equal to different values at the same time for some vertex V), then there is no valid sequence (X1, X2, …, XN) at all, otherwise the least lexicographically valid sequence of X’s is found by our algorithm.
That’s nice, but we are asked to find the K’th lexicographically valid sequence.
Let’s suppose, that (X1, X2, …, XN) is the least lexicographically valid sequence of X’s. Then we can just assign each Xi = Xi xor (K - 1) and get the K’th lexicographically valid sequence of X’s. This little trick works because ( XUj xor (K - 1) ) xor ( XVj xor (K - 1) ) = XUj xor XVj = Yj.
Let’s denote the minimal vertex of a connected component as a vertex with the minimal index among vertices from the component. If G is not connected, then let’s find the least lexicographically valid sequence of X’s in every connected component separately. After that, let’s find the K’th lexicographically valid sequence in the connected component with the maximal possible minimal vertex. It’s not hard to prove, that it’s the K’th lexicographically valid sequence for the whole graph G.
The total complexity of the solution is O(N + M).
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link
firstly. I coded the same solution as mentioned in the editorial except for this part please help me in getting this…