LSTGRPH - Editorial

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):

  1. Assigning X1 = 0;
  2. Starting BFS(or DFS) from the first vertex;
  3. 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

4 Likes

Hello Kostya_by,

Nice problem set :smiley: firstly. I coded the same solution as mentioned in the editorial except for this part please help me in getting this…

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.

To look out if there was “less than K valid labellings” was just another trick question, because if there is one valid labelling then there are 2^32 valid labellings (which is greater than K <= 10^9).

Nice problem.

2 Likes

Hello Everyone,

I coded the same as mentioned in the editorial during the contest … (Except the part that i used recursion in my code ) … Then i coded it only using BFS and got AC for now but i want to know why my previous code giving WA … It should produce some veridict link Rumtime error or something … So, please can anyone of you look at this code and tell me where it is going wrong…

http://www.codechef.com/viewsolution/5453920

I think at least my code is easily understandable …

if g doesnt contain loops , why will there be any contradictions

1 Like

How do we prove that assigning Xi = Xi XOR (K-1) will produce Kth lexicographically smallest sequence? I understand that Xi < Xi+1 < Xi+2 < … but how XOR with K-1 will produce Kth lexicographically smallest sequence?

1 Like

Can someone give an example input where contradictions would arise? I don’t see how it’s possible if there are no loops in G.

EDIT

Wiki definition of a loop: “In graph theory, a loop (also called a self-loop or a “buckle”) is an edge that connects a vertex to itself.” http://en.wikipedia.org/wiki/Loop_(graph_theory)

Not synonymous with a cycle: “In graph theory, there are two different types of object called cycles; a closed walk and a simple cycle. A closed walk consists of a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph. A simple cycle, also called a circle or polygon, is a closed walk with no repetitions of vertices and edges allowed, other than the repetition of the starting and ending vertex.” http://en.wikipedia.org/wiki/Cycle_(graph_theory)

if no loops exits in the graph then it’s a tree. All trees are Bipartite Graphs. so how can contradictions exits?

Setter and Tester solution link is not working…

consider the sequence (X1, X2, …, XN) as a number in the form x1x2x3…xN now to find least lexicographic number we should take x1=0 and solve for rest (we are finding the number with 0 as first digit)… so the second lexicographic number would be starting with 1 => x1=1 and so on… so to find the kth lexicographic sequence we xor the whole digits(sequence) with k-1

the problem isn’t available yet in the practice section.

It will be added soon.

Setter’s Solution and tester’s solution link crashed

1 Like

In fact, there’s an infinite number of them. The limit on output numbers’ sizes wasn’t a requirement.

correct …

i think we only need to do this for the last component …

Yeah, you should do this only in the connected component with the maximal possible minimal vertex, while in the other part of graph you should find the minimal valid sequence.

Let me try to explain this to you. Forget about the tree and Xor operation for this time. Suppose you need to produce the Kth lexographical sequence of N numbers .

00000000000… upto N numbers will be the first seq. agree?

00000000000…1(nth number)will be the second seq. agree?

00000000000…2 (with nth number) will be the third seq. agree?

and so on you can simply find the kth sequence following the same
order…

00000000000…K-1(nth number) will be K th lexo… sequence…

i hope you this is helpful …

Consider any cycle and start assigning values from one of its vertices in one direction. The you will see what condition have to be preserved.

Agreed. But how is it ensured that after Xor, the sequence is Kth smallest?
I agree that once you find the (lexicographically) smallest sequence (X1,X2,…Xn), there are infinite (or 2^32) solutions which can be obtained by Xoring each with a constant.
But after Xoring, numbers can change.
If a < b, then how is it guaranteed that a Xor K < b Xor K?
If you can prove this, then everything will follow.
Thanks for responding.