### i.trofimow's blog

By i.trofimow, history, 5 years ago,

Given 2 mutisets A and B, |A| = |B|, |A|, |B| <= 10^5, 0 <= elements in set <= 10^18. The task is to find such X that A ^ X = B or say that such X doesnt exists. How can one do that? A ^ X means foreach element of A xor it with X

• +35

 » 5 years ago, # |   -14 Let cnt1a be the the number of elements in A where the i-th bit is 1, cnt0a be the the number of elements in A where the i-th bit is 0. cnt1b and cnt0b are defined in the same way but for the set B. If cnt1a==cnt0b => the i-th bit in x is 1, else if cnt1a==cnt1b => the i-th bit in x is 0, else such x doesn't exist. Also in the end you have to check that x transforms set A to set B, which you can do easily with sets.
•  » » 5 years ago, # ^ |   0 Thats not true, if cnt1a = cnt0a and cnt1b = cnt0b u cant say anything about this bit in X
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -11 In that case, first you check if x works for the btis you know for sure, and then you only care about the unknown ones. For simplicity lets just define the set C as the set containing all elements from A without the known bits. For example if we know bits 1 and 3 (0 indexed), and A={0101,1100,0011}, then C={11,10,01}. Define D the same way as C, but with the elements from B. Let Y=C[0]^D[0]. Then remove C[0] and D[0] from the set. Lets find X for this two sets. For every bit i, we have cnt1c!=cnt0c (since we removed one elemtent). cnt1c==cnt0d if the i-th bit of Y is 1 (because then we removed one 1 from one set and one 0 from another) => the i-th bit of X is also 1. cnt1c==cnt1d if the i-th bit of Y is 0 (because then we removed one 1/0 from a set and one 1/0 from another) => the i-th bit of X is also 0. Thus X=Y. Thus C[0]^D[0] = X. Thus we found a number that satisfies the condition.Sorry if the explanation was unclear, I'm bad at explaining stuff.
•  » » » » 5 years ago, # ^ |   0 Nah dude, this aint right either — look why.If |A| is odd, theres only 1 possible X, solution from your first comment works fine. Tho theres easier way — X = (xor of all elements in A) ^ (xor of all elements in B). This is true because if u xor every element in A with some X and then u xor all elements of A u'll get A ^ X, cause |A| is odd so |A| / 2 pairs of X will just xor to 0.Thus, if |A| is even (xor of all elements in A) should be equal to (xor of all elements in B), otherwise theres no way to do whats required. And what u were doing was like — take some random element C from A, take some random element D from B, so answer X = C ^ D, delete these elements from sets and then, magic! A ^ B = X. Got the idea? Its wrong, because this will always hold for any C, D.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   -11 You didn't get what I'm doing. I've read my solution a few times and I'm sure it's correct. Try reading again.Btw I define the sets C and D, and take two random elements from C and D not A and B. And it works by taking any two random elements because of the special property sets C and D have (that cnt0c=cnt1c=cnt0d=cnt1d).
•  » » » » » » 5 years ago, # ^ |   0 I mean there are cases where A = C and B = D(when for every bit theres equal amount of numbers where this bit is 1 and 0). If so u postulate that A[i] ^ B[j] is a correct answer for any i, j. How can this be true? Or is it actually?
•  » » » » » » » 5 years ago, # ^ | ← Rev. 3 →   +5 Well, its not true. A = {4, 7, 9, 10}. B = {2, 7, 9, 12}. If u take 7 ^ 7( = 0) u obviously fail
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 As in the first case (in mt first comment), there wont always be a solution, and you have to check if your x works. However, if there is one solution, then any x=A[i]^B[i] will work, if they have the property I talkrd abou (proof in my second comment)
•  » » » » » » » » » 5 years ago, # ^ |   +5 Whats wrong with these sets A, B i gave? i dont understand
•  » » » » » » » » » 5 years ago, # ^ |   0 There is no solution for x in the examples you gave
•  » » » » » » » » » 5 years ago, # ^ |   +5 Oh ok then
•  » » » » » » 5 years ago, # ^ |   +5 Well i believe this is wrong — u r using fact that problem can be solved independently for bits, but it cannot. So when u fixed some 'known' bits not any pairs of elements from C, D are a correct answer anymore.
 » 5 years ago, # |   0 I think the problem can be reduced to the following two: Given two sets A and B, find X such that . Given a set S, find all d such that . ReductionFirst, partition into groups by multiplicities both for A and B. Then we need to find all solutions for each group and intersect the solution sets.For one group the problem is basically to do the same as in the original problem but for normal sets. Assume there's solution X. Then . Let's choose any . We can writeNow, if there is another solution X':Then, . This shows how all solutions are related.
•  » » 5 years ago, # ^ |   0 Yes, i think your reductions are correct, but how to solve any of them?
 » 5 years ago, # |   +8 Can you provide a link to the problem?
•  » » 5 years ago, # ^ |   0 Problem H from here http://codeforces.com/gym/100965/
 » 5 years ago, # |   0 Please send halp anyone
 » 5 years ago, # |   0 I'm don't check this but seems right. Look at the basis of A (name it Ba) and basis of B (name it Bb). Any of them has at most log vectors. We need to map one onto another one. If we fix image in Bb of any arbitrary vector from Ba we will now have image off whole A and we may check if latter equals B in O(nlogn) or better. Only log different images we may choose for our vector from A thus smth like O(nlog2n) we have.
•  » » 5 years ago, # ^ |   0 What do u mean by 'basis'?
•  » » 5 years ago, # ^ |   0 The (multi)sets are not necessarily forming linear spaces, i.e. they are not closed with respect to xor, so if you take any "basis" it may not produce exactly the set you want.
 » 5 years ago, # | ← Rev. 2 →   0 The problem is a tough one(solved by only one). You can always ask your friend who has coach rights. Judge Solution — http://ideone.com/GQJJBU First contract the multimaps as (number,occurrences) then if the occurrences multimaps are not equal then there can't be a solution since X will map each different number to different number. Then create a candidate of solutions and try them all(random_shuffle and time cutoff seems to be the trick emplyed here).
•  » » 5 years ago, # ^ |   0 Thanks man. I was wondering if judge's solution is deterministic or not.. well its kinda sad that its not.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Well, there exist other judge solutions which don't have time cutoff but random_shuffle just so that the solution if exists gets faster(we don't get too unlucky). So, they are deterministic. I can send you them if you need. This was the easiest and shortest looking solution to understand so I described this one.
•  » » » » 5 years ago, # ^ |   0 Well under 'deterministic' i meant smth with complexity, fitting TL, not just some random guessing
•  » » 5 years ago, # ^ |   0 The solution you linked does not work. It almost always prints -1 in the tests generated by this code even though there always exists a unique answer.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 It's kostya_by's accepted solution from that gym problem link(you can re-verify if it is by using coach rights :) ). If others are interested here is Los_Angelos_Laycurse's accepted solution: http://ideone.com/WB3lgE
 » 5 years ago, # |   0 I just don't understand...What's the problem with solving the problem for each bit independently?
•  » » 5 years ago, # ^ |   +5 Because bits arent independ.
•  » » » 5 years ago, # ^ |   0 Oh, Now I understand...
 » 5 years ago, # | ← Rev. 2 →   0 Ok, since my last explanation was very confusing, I'll try explaining it again more clearly, also with code. We itterate on each bit i. We count how many elements in A have the bit i equal to 0 (We store this count in cnt0a), how many have it equal to 1 (store in cnt1a) and the same for B (store in cnt0b and cnt1b) for(int i=0;i<63;i++){ for(int j=1;j<=n;j++){ (!(a[j] & (1 << i))) cnt0a++; else cnt1a++; (!(b[j] & (1 << i))) cnt0b++; else cnt1b++; } } Obviously cnt0a+cnt1a=cnt0b+cnt1b=63;Now let's assume that a solution X exists. For every bit i we must have either cnt0a==cnt1b (and obiously then cnt1a==cnt0b) (Then the i-th bit of X is 1, and transforms all 0s into 1s and viceversa), or cnt0a==cnt0b (and obiously then cnt1a==cnt1b) (Then the i-th bit of X is 0, and transforms all 0s into 0s and all 1s into 1s). Otherwise, no X exists. Then we can tell the i-th bit of X for all bits, EXCEPT for the case that cnt0a==cnt1a, then we can't tell what the i-th bit of X is. We set this bit as unknown. Let's ignore the unknown bits for now. for(int i=0;i<63;i++){ for(int j=1;j<=n;j++){ if(!(a[j] & (1 << i))) cnt0a++; else cnt1a++; if(!(b[j] & (1 << i))) cnt0b++; else cnt1b++; if(cnt0a==cnt1b) unknown[i]=1; else{ if(cnt0a==cnt1b) x+=(1< the i-th bit of Y is 0, cnt1a!=cnt0a, cnt1a==cnt1b, cnt0a==cnt0b. Thus, with the same reasoning as previously, the i-th bit of X is 0, and it coincides with the i-th bit of Y. 2. We removes one 1 and one 0 => the i-th bit of Y is 1, cnt1a!=cnt0a, cnt1a==cnt0b, cnt0a==cnt1b. Thus, with the same reasoning as previously, the i-th bit of X is 1, and it coincides with the i-th bit of Y.Thus X==Y, so it works for the deleted elements too. Thus the X for sets C and D is just C[1]^D[1]. Of course, this ONLY works if there exists a valid solution for X.Now we just sum the two Xs we've got to get the final answer. x+=c[1]^d[1]; Observe that all we've done so far was right, but we assumed that a solution X exists! What if it doesnt? Well the X we've found is the only possible X, but it might be wrong. We have to check it. It can easily be done using multisets. for(int i=1;i<=n;i++) s.insert(b[i]); for(int i=1;i<=n;i++){ a[i]^=x; auto it=s.find(a[i]); if(it==s.end()){ cout << -1; return 0; } s.erase(it); } cout << x; I hope it was clear, if you have any questions or if I am wrong somehow please let me know.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I believe, you're code is not really correct. You're not counting the number of 0 / 1 bits correclty. if(a[j] ^ (1 << i)) Should be replaced with if(!(a[j] & (1 << i))) 
•  » » » 5 years ago, # ^ |   0 woops. Thanks for pointing it out.
•  » » 5 years ago, # ^ |   +13 I think you are wrong. As i.trofimow mentioned before, the bits are not independent. You are right that when bits are not balanced it is easy to deduce the correct bit for X. But the hardest case is when all bits are balanced. And here you are wrong that all C[i] ^ D[j] work if there exists a solution. It is true only separately for each bit level as you do prove.Consider the hardest case, when all bits are "unknown", that is cnt1a==cnt0a==cnt1b==cnt0b for every bit i.Your second loop then simply xors both sets with 0xffff.. and it does not matter. So let C = D = [1, 3, 5, 10, 12, 14].If you set i=0 and j=1, so that 1 from C maps to 3 from D, you get:X = 1 ^ 3 = 2andset(C ^ X) = {1, 3, 7, 8, 12, 14} != D.And obviously X = 0 will work. So you have a solution but not all C[i] ^ D[i] work.
•  » » » 5 years ago, # ^ |   +5 Oh yeah, you are right. Thanks for pointing out my mistake.
•  » » 5 years ago, # ^ |   +10 From what I understand you prove that if a solution X exists such that if C[1] ^ X = D[1] then the solution for the remaining sets of size (n-1) would also be X. But does that help us anyway in finding a valid X? Since the assumption is C[1] ^ X = D[1]. It could be that C[1] mapping to any other D[i] leads to a valid X but not to D[1].
•  » » » 5 years ago, # ^ |   0 Any X=C[i]^D[j] works, there are multiple solutions.
•  » » » » 5 years ago, # ^ |   0 No they don't. hellman_ already gave an example.
•  » » » » » 5 years ago, # ^ |   0 Yup, got my mistake, thanks.
 » 5 years ago, # |   +3 where is its judge?
•  » » 5 years ago, # ^ |   0 Problem H from here http://codeforces.com/gym/100965/
 » 5 years ago, # |   -7 1) The answer can be broken down independently to each bit. 2) Having reduced the problem to one bit, you can easily see that the answer can be zero or one, or both (when the elements that are 1 equal the ones that are 0).
•  » » 5 years ago, # ^ |   +10 Bits are not independent though..
•  » » » 5 years ago, # ^ |   0 Yeah, never mind.
 » 5 years ago, # |   +10 What about putting all elements of A (with multiplicity) in a binary trie, do the same with elements of B and then doing tree isomorphism?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +15 Probably I did not understand idea completely but you need need to choose whether to swap subtrees for every vertex on the same level in the same way (because you xor all numbers with a fixed number), so this problem is not directly equivalent to tree isomorphism.UPD. I mean, consider A = {00000, 11111} and B = {00000, 11110} (I write numbers as bit strings for clarity). Then corresponding tries are isomorphic as rooted trees, but no x such that exists.
•  » » » 5 years ago, # ^ |   +10 Yes, you are right, it's not exactly tree isomorphism. Now, I wonder if an adaptation of that algorithm is possible.