sridhar153999's blog

maximum xor using k element of array
By sridhar153999, history, 5 years ago, In English

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/

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

dynamic programming is very slow I think Its O(n*k*2^(log of the maximum element in the array))

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

    but how to solve??

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

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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    2^(log of something)

    Hm, I wonder whether it's possible to simplify this somehow...

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Give the source otherwise it's from an ongoing contest

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 .

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      This is the memoize version. It got accepted. Submission code ==> 24056632

      #include <bits/stdc++.h>
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<n;++i){
            cin >> a[i];
        }
        cout << Max(0,0,k) << endl;
    }
    return 0;
}
      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't prefix sums work for XOR operation?

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

    They Work. But here we must choose a subsequence not a subarray and if want the subarray we could use window sliding technique.

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

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

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

    trying to understand your concept but if u have time can u elaborate it with some example

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

      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.

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

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.

→ Reply