CodingBeast23's blog

Need Help in this question...
By CodingBeast23, history, 4 years ago, In English

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
  • Vote: I like it
  • -7
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

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

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

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

Spoiler
→ Reply