LSTGRPH - Editorial

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.” Loop (graph theory) - Wikipedia

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.” Cycle (graph theory) - Wikipedia

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.

It doesn’t contain self-loops, but it is not limited to trees…