Nice problem set 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).
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…
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?
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
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
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…
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.