SuperSheep's blog

[Help] Divide an array into two subsequences such that the sum of their xor sums is maximum
By SuperSheep, history, 2 years ago, In English

I'm trying to solve this problem 103708A - Anya's gifts, in more detail, we need to do this.

Given an array $$$A$$$ of length $$$n$$$ ($$$n \leq 10^5$$$, $$$a_i < 2^{50}$$$), divide it into two subsequences $$$X$$$ and $$$Y$$$ such that $$$(x_1 \oplus ... \oplus x_{|X|}) + (y_1 \oplus ... \oplus y_{|Y|})$$$ is maximum. Print the maximum $$$xor\text{_}sum(X) + xor\text{_}sum(Y)$$$.

It is obvious that for each $$$2^p$$$, if the ammount of elements $$$a_i$$$ such that $$$a_i \text{ and } 2^p = 2^p$$$ is odd, the answer will always have its $$$p$$$-th bit on. I don't know how to handle the case where it's even.

Any help would be appreciated. Thanks!

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

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

Auto comment: topic has been updated by SuperSheep (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SuperSheep (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Read https://codeforces.me/blog/entry/68953

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

    Thanks a lot! I was finally able to solve it.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please give the code or approach for this questions?

      → Reply
      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        First, take all of the elements for the first subsequence. Notice that the bits that are turned on will only be turned in one subsequence, no matter which elements we take from the first subsequence to the second, because there is an odd number of elements with that bit turned on.

        Now the problem becomes: what is the maximum number that we can obtain by turning on the bits that are off in the xor of every element?

        That is because the bits that are off on the total xor, are turned on on an even number of elements (maybe zero), and if we move some of them to the second subsequence so that the bit turns on, it will be on on both subsequences.

        Notice that moving an element from the first subsequence to the second is equivalent to xor-ing it. The problem can be solved with xor basis

        → Reply