Tudor's blog

XorSubstrings
By Tudor, history, 9 years ago, In English

It is an array with n elements and d[i] = how many substrings have XOR value i. What is the optimal algorithm for build this dp? substring = a[i1] , a[i2] , ... not contigous.

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

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

What is the range of elements ?

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

In the beginning you mention substrings, then in the end "not contiguous".

By the way, if you're interested in contiguous substrings with their XOR equals to a value X:

1) Create a trie with all XOR prefixes of values in array A.

2) Take advantage of XOR associativity property and then, for each prefix, search for an value inside the trie which it's value XOR the current prefix would lead to X.

Insertion on trie is O(N*L) with L as the number of bits of the value. As the maximum value is 32, insertions and queries are negligible. The overall complexity is O(n).

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

    I know the solution for contiguous substrings but I want for not contiguous. Anyway , thank you!

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

Take a dp[n][xor] which stores the number of substrings having xor value 'xor' starting at index i;

start iterating over the string from the end. dp[i][x]=dp[i+1][a[i]^x];

for non contiguous, use the idea of inclusion exclusion dp[i][x]=dp[i+1][x]+dp[i+1][x^a[i]];

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

    OK , this solution is in O(n^2) , but i want in O(nlogn) or something like this.

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

      not o(n^2), more like ~ o(n * max_a) where max_a is the biggest element in the array. That complexity can be worse or better depending on the constrains. How big are the constrains for the elements and for N?

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

        Ok , but it isn't optimal good. N <= 10 ^ 5 or something like this

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      ignore

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

can u give me the link of problem?

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

    There isn't a problem... I thought at this, some time and i didn't find a good solution, so I published this post.

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

  1. Use Gaussian Elimination to find a basis for the space spanned by the N vectors. Let R be its rank.

  2. Add the vector i to the basis, and use Gauss again to check whether the rank increased. If it did, the answer is 0, since i is not in the space spanned by the elements of the original array.

  3. If adding i didn't increase the rank, the answer is 2 ^ (# of free variables); that is, 2 ^ (N — R).

→ Reply