You are not logged in. Please login at www.codechef.com to post your questions!

×

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 ?

asked 16 Dec '15, 07:32

pallesai's gravatar image

4★pallesai
176830
accept rate: 17%

edited 16 Dec '15, 13:33

admin's gravatar image

0★admin ♦♦
19.6k349497539


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

link

answered 16 Dec '15, 10:44

pulkitsinghal's gravatar image

6★pulkitsinghal
35729
accept rate: 43%

edited 16 Dec '15, 12:50

1

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

(18 Dec '15, 00:22) sanstroke4★

The value of 'X' will be 1023 ?

(18 Dec '15, 22:37) theweblover0072★

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

link

answered 23 May '16, 14:21

purvabaradia's gravatar image

3★purvabaradia
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,615
×1,965

question asked: 16 Dec '15, 07:32

question was seen: 1,435 times

last updated: 23 May '16, 14:21