Блог пользователя sridhar153999

maximum xor using k element of array

Автор sridhar153999, история, 7 лет назад, По-английски

MAXIMUM XOR USING K ELEMENT IN ARRAY

for example

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/

solution spoj

sridhar153999
7 лет назад
26

Комментарии (23)

Показать архивные | Написать комментарий?

BanazadehAria

7 лет назад, скрыть # |

← Rev. 2 →

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

→ Ответить

sridhar153999

7 лет назад, скрыть # ^ |

but how to solve??

→ Ответить

BanazadehAria

7 лет назад, скрыть # ^ |

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

→ Ответить

-is-this-fft-

7 лет назад, скрыть # ^ |

+44

2^(log of something)

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

→ Ответить

BanazadehAria

7 лет назад, скрыть # ^ |

If you could please share it :(

→ Ответить

wet_water

7 лет назад, скрыть # ^ |

← Rev. 2 →

I believe -is-this-fft- is just trying to point out that 2^(log of something) is just "something"

→ Ответить

nik7

7 лет назад, скрыть # |

Give the source otherwise it's from an ongoing contest

→ Ответить

Shahraaz

7 лет назад, скрыть # |

← Rev. 2 →

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

→ Ответить

Shahraaz

7 лет назад, скрыть # ^ |

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.

→ Ответить

BanazadehAria

7 лет назад, скрыть # ^ |

← Rev. 2 →

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 .

→ Ответить

BanazadehAria

7 лет назад, скрыть # ^ |

← Rev. 2 →

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;
}

→ Ответить

Shahraaz

7 лет назад, скрыть # ^ |

This is Good :)

→ Ответить

sridhar153999

7 лет назад, скрыть # ^ |

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?

→ Ответить

BanazadehAria

7 лет назад, скрыть # ^ |

Practice

→ Ответить

sridhar153999

7 лет назад, скрыть # ^ |

any good tutorial on youtube?

→ Ответить

BanazadehAria

7 лет назад, скрыть # ^ |

Errichto New tutorial on dp

→ Ответить

Kenb

7 лет назад, скрыть # |

Don't prefix sums work for XOR operation?

→ Ответить

BanazadehAria

7 лет назад, скрыть # ^ |

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

→ Ответить

Scissors_Ss

7 лет назад, скрыть # |

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

→ Ответить

sridhar153999

7 лет назад, скрыть # ^ |

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

→ Ответить

Scissors_Ss

7 лет назад, скрыть # ^ |

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.

→ Ответить

Grunt

7 лет назад, скрыть # |

← Rev. 2 →

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.

→ Ответить