i.trofimow's blog

By i.trofimow, history, 8 years ago, In English

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

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thats not true, if cnt1a = cnt0a and cnt1b = cnt0b u cant say anything about this bit in X

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it -11 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          Rev. 2   Vote: I like it -11 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              Rev. 3   Vote: I like it +5 Vote: I do not like it

              Well, its not true. A = {4, 7, 9, 10}. B = {2, 7, 9, 12}. If u take 7 ^ 7( = 0) u obviously fail

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

                  Whats wrong with these sets A, B i gave? i dont understand

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  There is no solution for x in the examples you gave

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

                  Oh ok then

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the problem can be reduced to the following two:

  1. Given two sets A and B, find X such that .
  2. Given a set S, find all d such that .
Reduction
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, i think your reductions are correct, but how to solve any of them?

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you provide a link to the problem?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please send halp anyone

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do u mean by 'basis'?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks man. I was wondering if judge's solution is deterministic or not.. well its kinda sad that its not.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well under 'deterministic' i meant smth with complexity, fitting TL, not just some random guessing

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I just don't understand...What's the problem with solving the problem for each bit independently?

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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<<i);
            else if(cnt0a==cnt0b);
            else{
                cout << "-1";
                return 0;
            }
        }
    }
}

Next step is to find the unknown bits. Lets create two sets C and D, which contain all elemnts in A and B respectively, but with the known bits equal bits missing (or all equal to 0 for an easier code, its equivallent).

for(int i=0;i<63;i++){
    if(!unknown[i]) continue;
    for(int j=1;j<=n;j++){
        if(!(a[j] & (1 << i))) c[j]+=(1<<i);
        if(!(b[j] & (1 << i))) d[j]+=(1<<i);
    }
}

We have the following in sets C and D: cnt1a==cnt0a==cnt1b==cnt0b for every bit i, since it only contains unknown bits, which have this property, or only 0s.

Again, we assumed such an X exists. Then let's prove that X=C[1]^D[1], or any C[i]^D[j] for that matter. Let Y=C[1]^D[1]. Lets remove C[1] and D[1] for the sets entirely. Let's find X for this remaining set of n-1 elements.

Now, for each bit i, we have two cases: 1. We removes two 1s or two 0s => 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.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)))
    
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 = 2

    and

    set(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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh yeah, you are right. Thanks for pointing out my mistake.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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].

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

where is its judge?

»
8 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
    Rev. 5   Vote: I like it +15 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Yes, you are right, it's not exactly tree isomorphism. Now, I wonder if an adaptation of that algorithm is possible.