×

# How the recursion for CHEFFILT works ?

 1 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 ? asked 16 Dec '15, 07:32 4★pallesai 176●7●28 accept rate: 17% 0★admin ♦♦ 19.0k●348●495●531

 5 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 :) answered 16 Dec '15, 10:44 357●2●9 accept rate: 43% 1 +1 for the explanation in this point "(ii) cnt[i]>0" which is missing in the editorial.. (18 Dec '15, 00:22) The value of 'X' will be 1023 ? (18 Dec '15, 22:37)
 0 Why am i getting wrong answer ? https://www.codechef.com/viewsolution/10150470 answered 23 May '16, 14:21 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,155
×1,754

question asked: 16 Dec '15, 07:32

question was seen: 1,399 times

last updated: 23 May '16, 14:21