PROBLEM LINK:
Author: Lalit Kundu
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak
DIFFICULTY:
SIMPLE
PREREQUISITES:
DP, bits
PROBLEM:
You are given an array A of N integers and an integer K. Your task is to return the maximum possible value of F(P) xor K, where P is a subset of A and F(P) is defined as a xor of all values in P. If P is empty, then F(P) = 0.
QUICK EXPLANATION:
Since each element of A has a value of at most 1000, we can use dynamic programming dp[i][j] := 1 if and only if there exists a subset P of A[1ā¦i] such that F(P) = j. In order to get the result, we return max 1 <= j <= 1023 { dp[n][j] * (j ^ k) }
EXPLANATION:
Let dp[i][j] := 1 if and only if there exists a subset P of A[1ā¦i] such that F(P) = j, otherwise 0
The first observation is that F(P) can be at most 1023 since any input number is at most 1000.
Initially we set all dp[i][j] := 0.
Next, we set dp[0][0] := 1, since a xor of the empty set is 0.
We iterate over all elements of A from left to right. For each A[i], we iterate over all possible values of the xor function i.e. a range from 0 to 1023 inclusive and update these values as follows:
for i = 1 to N:
for j = 0 to 1023:
dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]
The reason for this is that if there exists a subset P of A[1ā¦i - 1] such that F(P) = j then there exists also a subset of A[1ā¦i] such that F(P) = j or if there exists a subset P of A[1ā¦i - 1] such that F(P) = j ^ a[i], then F(P) ^ a[i] = j, so there exists a subset Pā of A[1ā¦i] such that F(Pā) = j
At the end we have dp[n][j] for all 0 <= j <= 1023, and we can return a maximum value of dp[n][j] * (j ^ k) for all j.
Time Complexity:
The time complexity per one testcase is O(N * 1023);
AUTHORāS AND TESTERāS SOLUTIONS:
To be uploaded soon.
RELATED PROBLEMS:
To be uploaded soon.