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

Автор CodingBeast23, история, 4 года назад, По-английски

You are given an array A of size N; find the minimum value of K such that number of subarrays with XOR value at most K is at least X:

  • 1 <=N << 10^5
  • 1 <= X <= N*(N+2)/2
  • 1 <= A[i] <= 10^6

    For Input :
    4 7
    1 2 3 4    
    Output : 4
    
  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

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

Use binary search to find the value of k which satisfies the given constraint. For each k, check if its possible to have atleast X subarrays with Xor value = K. checking part should be possible in O(nlogn), so the time complexity would be around O(nlogn^2). refer to the following link for checking the constraint part.

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

Imagine we build an array cnt[], where cnt[xr] — number of different subarrays with XOR-sum equal xr.

Then we can greedy pick subarrays in increasing order of xor-sum until we haven't collect X of them.

example: cnt = {2, 3, 4, 1}, X = 6 — then answer is 2, because (cnt[0]+cnt[1] < X && cnt[0]+cnt[1]+cnt[2] >= X)

That part works in O(N)

Turns out we can build cnt[] in O(A log(A)) time

Consider (pm[i] = pm[1] xor pm[2] xor ... xor pm[i]) (pm[0] = 0)

Then xor-sum of [L, R] subarray equals to (pm[R] xor pm[L-1])

now we need to calculate the number of ways to choose L, R such that: (pm[L] xor pm[R] == xr) for every xr

note that we make reindexation so (L < R) now

That can be done by Fast Walsh-Hadamard transform in O(A log(A)).

After that we have to substract all [p, p] subarrays : for p from 0 to N (cnt[pm[p]]--)

Divide all cnt[] by 2, to substract L > R subarrays

total complexity: O(A log(A))

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

When you can tell which country OP is from by the title

Spoiler