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
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
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 <= A[i] <= 10^6
For Input :
4 7
1 2 3 4
Output : 4
Name |
---|
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.
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))
Can I have a coded solution ?
I will code it today, but not right now.
When you can tell which country OP is from by the title
*problem/task
I did not understand I am not frequent on codeforces blogs.
Click