# 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 | 3686 |

2 | LHiC | 3330 |

3 | wxhtxdy | 3329 |

4 | Benq | 3315 |

5 | Um_nik | 3301 |

6 | sunset | 3279 |

7 | V--o_o--V | 3275 |

8 | yutaka1999 | 3190 |

9 | Radewoosh | 3179 |

10 | Petr | 3115 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | Radewoosh | 184 |

3 | rng_58 | 163 |

4 | PikMike | 162 |

5 | Vovuh | 156 |

6 | 300iq | 153 |

7 | Petr | 149 |

8 | Um_nik | 147 |

9 | neal | 144 |

9 | kostka | 144 |

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/

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2019 10:40:21 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

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 :(

yup u r right!i didn't get that :(

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

Auto comment: topic has been updated by sridhar15399 (previous revision, new revision, compare).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

brilliant explanation thanks!

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!

I can barely follow the translation, but thanks! I'm sure there will be English articles describing the idea somewhere.