Блог пользователя Tudor

XorSubstrings
Автор Tudor, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the range of elements ?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      ignore

      → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can u give me the link of problem?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить