sridhar153999's blog

By sridhar153999, history, 3 years ago,

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/

• +13

 » 3 years ago, # | ← Rev. 2 →   0 dynamic programming is very slow I think Its O(n*k*2^(log of the maximum element in the array))
•  » » 3 years ago, # ^ |   0 but how to solve??
•  » » » 3 years ago, # ^ |   0 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 :(
•  » » » » 3 years ago, # ^ |   0 yup u r right!i didn't get that :(
•  » » 3 years ago, # ^ |   +44 2^(log of something) Hm, I wonder whether it's possible to simplify this somehow...
•  » » » 3 years ago, # ^ |   0 If you could please share it :(
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 I believe -is-this-fft- is just trying to point out that 2^(log of something) is just "something"
 » 3 years ago, # |   +8 Give the source otherwise it's from an ongoing contest
 » 3 years ago, # |   0 Auto comment: topic has been updated by sridhar153999 (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   +3 As the limit and Constraints are low, We need not go for a Dp solution.We just have to try Everything. const int nax = 25; int n, k; vector a(nax); int solve(int pos, int rem, int prevXor) { if (pos == n) // Exhausted the element choice { if (rem == 0) // You have chosen k elements somehow, so this is valid return prevXor; else return 0; // Something went wrong returning the least possible value } if (rem == 0) // Whoa! You have to finish the taking process return prevXor; // Now me have a choice int ret = max(solve(pos + 1, rem, prevXor), solve(pos + 1, rem - 1, prevXor ^ a[pos])); // Take the element or not -- Choose the best return ret; } void solve() { cin >> n >> k; for (int i = 0; i < n; ++i) cin >> a[i]; cout << solve(0, k, 0) << '\n'; } Link to full Code https://github.com/Shahraaz/CP/blob/master/spoj/CODEIT02.cpp
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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 .
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 This is the memoize version. It got accepted. Submission code ==> 24056632 #include using namespace std; const int MAXN = 20+1; int a[MAXN],n,k; int dp[MAXN][(1<<13)][MAXN]; int Max(int i,int mask,int remained){ if(i==n){ if(remained==0) return mask; else return 0; } if(dp[i][mask][remained]!=-1) return dp[i][mask][remained]; int res=0; if(remained>0) res = Max(i+1,mask^a[i],remained-1); res = max(res,Max(i+1,mask,remained)); return dp[i][mask][remained] = res; } int main() { int t;cin >> t; while(t--){ memset(dp,-1,sizeof(dp)); cin >> n >> k; for(int i=0;i> a[i]; } cout << Max(0,0,k) << endl; } return 0; } 
•  » » » » 3 years ago, # ^ |   0 This is Good :)
•  » » » » 3 years ago, # ^ |   0 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?
•  » » » » » 3 years ago, # ^ |   0 Practice
•  » » » » » » 3 years ago, # ^ |   0 any good tutorial on youtube?
•  » » » » » » » 3 years ago, # ^ |   0 Errichto New tutorial on dp
•  » » 3 years ago, # ^ |   0 brilliant explanation thanks!
 » 3 years ago, # |   0 Don't prefix sums work for XOR operation?
•  » » 3 years ago, # ^ |   0 They Work. But here we must choose a subsequence not a subarray and if want the subarray we could use window sliding technique.
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 trying to understand your concept but if u have time can u elaborate it with some example
•  » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # | ← Rev. 2 →   0 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.
•  » » 3 years ago, # ^ |   0 Any English resource? Thanks!