I am trying to solve CHEFFILT problem
I understood the Editorial partially but unable to understand how the recurrence works?Any one please explain how the recurrence works ?
Let us first understand the property of XOR operation, x \oplus x = 0 i.e. if we add even number of elements to any set, its XOR value will remain same
First we define a solution to a simpler problem, then we define it for our original problem
Problem : Given a set A of n elements and value X, how many subsets S of A will give XOR(S) \oplus X = 0, where XOR(S) represents XOR of elements of subset S. It is considered that A_i,X < 2^{10} and 1 \le n \le 1000
Solution : We first give a O(n*2^{10}) solution. As all the numbers are atmost 10 bits long, there are only 2^{10} possible XOR values. So we have state of DP as \text{(index, XOR value)}. So for every index we have to store result for every possible XOR value which results in O(n*2^{10}) space complexity and for each state we 2 possible choices of move, which makes time complexity O(2*n*2^{10}) Generally we omit this 2 in multiplication
Now let us define the recurrence relation, f(i,j) as count of subsets of A[i..n-1] such that there XOR values is j
If our i reaches n, then we have no more elements left for consideration, so if j becomes 0, we have selected a correct subset and we return 1 otherwise we return 0
Now for i \lt n , we have 2 choices, either to include A_i or not to include it
Thus our recurrence relation will be like,
Now lets move back to our original problem, the only change in problem is constraint on n. So the problem statement will be like
Problem : Given a set A of n elements and value X, how many subsets S of A will give XOR(S) \oplus X = 0, where XOR(S) represents XOR of elements of subset S. It is considered that A_i,X < 2^{10} and 1 \le n \le 10^5
Solution : Now our old O(n*2^{10}) solution will give TLE, so how can be improve our previous solution to get it accepted
As A_i \le 2^{10}, considering all same values will give a better result. Now why this works ?
Assume that we have two values P and Q, then P \oplus Q \oplus Q = P, which means that from value P, if we have infinite count of Q, only possible XOR values are P and P \oplus Q
Thus if we add even number of value Q to a set having current XOR value P, then resulting set will have XOR value P but if we add odd number of value Q, then XOR value is P\oplus Q
If a set S consists of m elements, then it has 2^m subsets, in which there are 2^{m-1} subsets with odd number of elements and 2^{m-1} subsets with even number of elements
Now for our solution, consider cnt[i] represent the count of value i
We define f(i,j) as number of subsets considering values [i..2^{10}-1] having XOR values j
In this if i reaches 2^{10} then we have no more values to consider, we return 1 if j = 0, 0 otherwise
Now the interesting part comes, we have 2 cases :
(i) cnt[i] = 0 : In this we cannot add i so we have only option to move forward without considering the i, which results in f(i+1,j)
(ii) cnt[i] \gt 0 : In this if we want to consider i then we can add it odd number of times which results in f(i+1,j\oplus i) * 2^{cnt[i]-1} ways, but if we don’t want to consider i then we can add it even number of times which results in f(i+1,j) * 2^{cnt[i]-1} ways
Thus our recurrence relation will be
The answer for problem can be get by calling f(0,X)
I hope you get the recurrence relation now. If you face any problem please ask
Happy Coding
+1 for the explanation in this point “(ii) cnt[i]>0” which is missing in the editorial…
The value of ‘X’ will be 1023 ?