MAXIMUM XOR USING K ELEMENT IN ARRAY
for example
5 3
1
2
3
4
5
here no of element=5,k=3; here OUTPUT IS 7 how to approach this type of problm with or without recursion which one is easier source= https://www.spoj.com/problems/CODEIT02/
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
for example
5 3
1
2
3
4
5
here no of element=5,k=3; here OUTPUT IS 7 how to approach this type of problm with or without recursion which one is easier source= https://www.spoj.com/problems/CODEIT02/
Name |
---|
dynamic programming is very slow I think Its O(n*k*2^(log of the maximum element in the array))
but how to solve??
dp[i][k][mask] ==> The maximum xor we can get if we have checked( Not neccesary used)[1..i] and we have k elements need to xored left and until now the answer of xored is mask.
Sorry for very very poor English :(
Hm, I wonder whether it's possible to simplify this somehow...
If you could please share it :(
I believe -is-this-fft- is just trying to point out that 2^(log of something) is just "something"
Give the source otherwise it's from an ongoing contest
As the limit and Constraints are low, We need not go for a Dp solution.
We just have to try Everything.
Link to full Code https://github.com/Shahraaz/CP/blob/master/spoj/CODEIT02.cpp
I tried Dp https://ideone.com/VS8Wzc. But the time limit of 0.107s. Won't let it pass for this question. But Dp is a more preferred way to approach this kind of problems.
You meant that bottom up approach will not work.
We can only add a 3-d array dp and memoize and it will make the time better :(
Space Complexity ==> O(2^13 * 20 * 20 ) Witch is close to 3*1e6 so we can have that array.
Time Complexity ==> O(10* 2^13 * 20 * 20) Witch is not even 1e8 So we can do this with even bottom up approach easily.
If Im wrong correct me please .
This is the memoize version. It got accepted. Submission code ==> 24056632
This is Good :)
i still do struggle in dp what is the best way to learn dp from which problem should i start i mean a know reursion well but find harder to make that mwths equation any help?
Practice
any good tutorial on youtube?
Errichto New tutorial on dp
Don't prefix sums work for XOR operation?
They Work. But here we must choose a subsequence not a subarray and if want the subarray we could use window sliding technique.
Cause $$$n$$$ is small you can use bitmasks. Iterate from $$$1$$$ to $$$2 ^ n$$$. If number of bits which are $$$1$$$ is $$$k$$$ go through array and $$$xor$$$ every position which bit is $$$1$$$. And finally maximize answer with result. Complexity is $$$O(T * 2 ^ n * n)$$$.
Code
trying to understand your concept but if u have time can u elaborate it with some example
This program checks all variations and finds the best. You must choose $$$k$$$ element from array. To do this easily you can imagine binary string. $$$j - th$$$ element is chosen if $$$j - th$$$ bit in string is $$$1$$$. And by trying all combinations of binary string you can find the answer.
A classic problem about linear basis. If you are familiar with Chinese, I prefer you read this blog, a solution with time complexity of O(nlogM) is described. And this method is very useful and applied to many XOR problems.
Any English resource? Thanks!