How the recursion for CHEFFILT works ?

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 ?

1 Like

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,

f(i,j) = \begin{cases} 1 & \text{if $i = n$ and $j = 0$}\\ 0 & \text{if $i = n$ and $j \ne 0$}\\ \left[f(i+1,j) + f(i+1,j\oplus A_i)\right] & \text{if $i \lt n$} \end{cases}

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

f(i,j) = \begin{cases} 1 & \text{if $i = 2^{10}$ and $j = 0$}\\ 0 & \text{if $i = 2^{10}$ and $j \ne 0$}\\ f(i+1,j) & \text{if $i \lt 2^{10}$ and $cnt[i] = 0$}\\ \left[f(i+1,j) + f(i+1,j\oplus i)\right]*2^{cnt[i]-1} & \text{if $i \lt 2^{10}$ and $cnt[i] \gt 0$} \end{cases}

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

5 Likes

Why am i getting wrong answer ?
https://www.codechef.com/viewsolution/10150470

+1 for the explanation in this point “(ii) cnt[i]>0” which is missing in the editorial…

1 Like

The value of ‘X’ will be 1023 ?