Search code examples
c++algorithmsubsetxor

Finding maximum value of all possible subsets XOR's if the subsets can be infinitely generated

I wanted to solve this problem: C. Vampiric Powers, anyone?, Codeforces

enter image description here

In short, there is sequence a, and infinitely times we can find XOR of any subset and append the XOR of this subset to the end of a. Maximum value present in a (including these appended) is our answer.

My idea is as below:

  1. Find maximum value in original a
  2. Find prefix XOR in original a
  3. Sort found prefixes in descending order. Set ans = 0, iterate over sorted prefix array, and if at any point ans XOR prefix[i] > ans, we set ans = ans XOR prefix[i].

Why the step works? Imagine a has 3 elements [x, y, z]. We can append x XOR y XOR z to the end of a, now it's equal to [x, y, z, (x XOR y XOR z)]. If we calculate one more XOR of whole updated a, it will have 0 at the end. At this point, we can select indexes (and calculate prefix sums up to them) that only increments our answer. So we sort prefix XOR array in descending order and check whether this prefix[i] will make our result better.

We sort in descending order, because if we start from ascending, then smaller elements, that are also included (their bits) in higher elements will be just substracted from answer by XOR operation.

That's code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        int maxi = 0;
        vector<int> a(n);
        vector<int> xors(n);
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
            maxi = max(maxi, a[i]);

            if (i > 0)
                xors[i] = a[i] ^ xors[i - 1];
            else
                xors[i] = a[i];
        }

        sort(xors.begin(), xors.end(), greater<int>());

        int cur = xors[0];
        for (int i = 1; i < n; ++i)
        {
            if ((cur ^ xors[i]) > cur)
            {
                cur ^= xors[i];
            }
        }

        cout << max(maxi, cur) << '\n';
    }
}

The problem is that this idea (or code?) fails some test cases (it gave too big answer, but I don't know the input). I really can't see why.

Solution

  • Since each array element is in the range [0, 255], this can be solved with dynamic programming. Note that the order in which the operations are applied does not matter.

    The value of the added element at the end can be used as the state and for each state, we can store the value of the largest element seen so far.

    #include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // no need to untie cout; it's not tied by default

    int t, n;
    for (std::cin >> t; std::cin >> n;) {
        std::vector<int> a(n);
        for (int& v : a) std::cin >> v;
        std::vector<int> dp(1 << 8, -1);
        dp[0] = 0;
        int suffXOR = 0;
        for (int v : std::views::reverse(a)) {
            suffXOR ^= v;
            int best = -1;
            for (int m = 0; m < 1 << 8; ++m)
                if (~dp[m])
                    best = std::max(best, suffXOR ^ m);
            dp[suffXOR] = std::max(dp[suffXOR], best);
        }
        std::cout << std::ranges::max(dp) << '\n';
    }
}

    Note that this can also be reduced to the problem of finding the largest XOR of any subarray, which can be solved in O(N log MAX_VALUE) with a trie.