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

×

CHEFFILT - Editorial

4
3

PROBLEM LINK:

Contest
Practice

Author: Dmytro Berezin
Tester: Sergey Kulik
Editorialist: Kevin Atienza

PREREQUISITES:

Dynamic programming

PROBLEM:

Chef has an image $S$ consisting of just $10$ pixels in a row. Each pixel is either black or white. There are $N$ filters, where each filter is a string of length $10$ consisting of + and - characters. If a particular filter is applied, then all pixels corresponding to +s in the filter will get flipped.

How many different subsets of the filters will turn the image into an all-black image?

QUICK EXPLANATION:

We can replace images and filters with binary numbers of at most $|S|$ bits, where "white" and + correspond to $1$. In this representation, there are $2^{|S|}$ distinct filters and $2^{|S|}$ distinct images, $0 \ldots 2^{|S|}-1$, and applying a filter means simply performing a bitwise-XOR with the filter on the image.

Let $c_i$ be the number of filters $i$ present in the input. Define $f(i,j)$ be the number of ways to turn the image $j$ into an all-black image (i.e. image $0$) using only the first $i+1$ distinct kinds of filters. We can compute $f(i,j)$ using dynamic programming. The following is a recurrence for $f(i,j)$: $$f(i,j) = \begin{cases} [j = 0] & \text{if $i = -1$} \\\ f(i-1,j) & \text{if $i \ge 0$ and $c_i = 0$} \\\ \left[f(i-1,j) + f(i-1,j\oplus i)\right]2^{c_i-1} & \text{if $i \ge 0$ and $c_i > 0$} \end{cases}$$ The answer is simply $f(2^{|S|}-1, S)$. (where $|S|$ is not the absolute value, rather it is the length of the original input string. In this problem this value is always $10$.)

Since there are around $4^{|S|} \le 1.05\times 10^6$ possible arguments to $f$, we can tabulate $f(i,j)$. If the entries of this table is filled in order of increasing $i$, then we'll be able to compute all entries in just $O(4^{|S|})$ time.

EXPLANATION:

The problem can be stated in terms of binary strings. An "image" and a "filter" is really just a binary string of length $10$. So let's say we replace "white" and "+" with $1$, and "black" and "-" with $0$. Then:

  • The initial image $S$ can be represented as an integer from $0$ to $2^{10}-1$.
  • The all-black image is simply image $0$.
  • A filter $F$ can be represented as an integer from $0$ to $2^{10}-1$.
  • The result of applying the filter $F$ to $S$ is simply the bitwise XOR of $F$ and $S$, denoted $F\oplus S$. This is clear from the problem and from the definition of bitwise XOR. (see the appendix for a refresher on bitwise XOR)

The problem is now:

Given an integer $S$ and a set of $N$ filters (represented by integers), how many subsets of filters are there such that applying the bitwise-XOR of each filter to $S$ results in image $0$?

Note that filters are considered distinct even if they are represented by the same integer.

Subsets with bitwise XOR zero

$N$ can be very large, especially in the last subtask, so this seems intractable. However, notice that while $N$ can reach up to $10^5$, the number of distinct filters is at most $2^{10}$. This suggests grouping the filters according to the integer representing them. This reordering/grouping doesn't affect the answer, because order doesn't matter in subsets (and also because bitwise XOR is commutative and associative).

So now, instead of our $N$ filters, we can replace it with a list $c_0, c_1, c_2 \ldots c_{2^{10}-1}$, where $c_i$ is the number of filters that are represented by the integer $i$.

Now, what happens if we apply a set of filters represented by the same integer, say, $i$? After applying the first one, the image becomes $S\oplus i$. Then after applying the second one, it becomes the value $S\oplus i\oplus i$. But this is just equal to $S$! In other words, applying two equivalent filters is the same as applying none at all. Okay, let's proceed. After applying third one, the number becomes $S\oplus i$ again, which is the same as applying only once! We can continue with this for more and more filters to get the following fact:

Applying an odd number of equivalent filters is the same as applying just one equivalent filter. Applying an even number of equivalent filters is the same as applying none.

This makes things much easier. Suppose we look at a particular integer, say $i$. Then there are only two possible outcomes when applying any number of filters with the integer $i$ to $S$: $S$ and $S\oplus i$. Also, applying every even subset of our set of filters results in $S$, and applying every odd subset results in $S\oplus i$. Thus, we just need to know how many subsets are odd and even.

Suppose there are $c_i$ filters. How many subsets are there? For each element, there are two choices, whether to include it or not, so there are $\underbrace{2\cdot 2\cdots 2}_{c_i}$ or $2^{c_i}$ subsets.

How many of those are even? Similarly as above, we can choose, for each element, whether to include it or not. Thus, there are again two choices for each element. However, the last element is special! This is because we want to ensure that the size of the set is even. So in selecting the last element, we first check whether the size of the subset already constructed is even or odd. If it is odd, then we have no choice but to include the last element to the set to make it even. If it is even, then we have no choice but to exclude the last element, otherwise it will be odd. Therefore, after making the choices for the first $c_i - 1$ elements, there is a unique choice for the last element. This implies that the number of even-sized subsets is equal to $2^{c_i-1}$! A very similar argument shows that there are also $2^{c_i-1}$ odd-sized subsets.

Note that the argument above only holds for $c_i$ is not $0$. But the case $c_i = 0$ is trivial: there is only one such set, namely the empty set, and it is even.

Armed with this, we can now devise a dynamic programming solution for the problem. Let's define $f(i,j)$ as the number of ways to turn the image $j$ into image $0$ using only the first $i+1$ distinct kinds of filters. The answer is simply $f(2^{10}-1, S)$.

To compute $f(i,j)$, consider the filters represented by $i$. There are $c_i$ such filters. There are $2^{c_i-1}$ even-sized subsets, and when every such set of filters is applied, the resulting image is $j$. There are $2^{c_i-1}$ odd-sized subsets, and when every such set of filters is applied, the resulting image is $j\oplus i$. Therefore, we have the following general recurrence: $$f(i,j) = \left[f(i-1,j) + f(i-1,j\oplus i)\right]2^{c_i-1}$$ (don't forget to reduce modulo $10^9 + 7$!)

Note that this only works when $i \ge 0$ and $c_i > 0$. If $c_i = 0$, then there are no filters $i$ so we can simply say $f(i,j) = f(i-1,j)$. Finally, if $i < 0$, then there are no filters to apply altogether, and the only way to turn $j$ into zero is if $j$ is already zero! Thus, we have: $f(-1,0) = 1$ and $f(-1,j) = 0$ for $j \not= 0$.

Summarizing these formulas, we now have the following: $$f(i,j) = \begin{cases} [j = 0] & \text{if $i = -1$} \\\ f(i-1,j) & \text{if $i \ge 0$ and $c_i = 0$} \\\ \left[f(i-1,j) + f(i-1,j\oplus i)\right]2^{c_i-1} & \text{if $i \ge 0$ and $c_i > 0$} \end{cases}$$ (The expression "$[j = 0]$" uses the Iverson bracket notation.)

Since there are around $4^{10} \le 1.05\times 10^6$ possible distinct arguments to $f$, we can tabulate $f(i,j)$, and populate this table in increasing order of $i$. Filling a table of up to $10^6$ elements easily passes the time limit, even in Python! (This is an example of dynamic programming.)

Appendix: bitwise XOR

It's helpful to refresh oneself about the bitwise XOR operation. The bitwise XOR of two numbers is obtained by writing two numbers in binary, padding with leading zeroes if necessary so they have the same number of digits, and "XOR"-ing each column. The resulting binary number is the bitwise XOR. (Remember that the XOR of two bits is $1$ if they are different, and $0$ if they are the same.)

For example, the bitwise XOR of $143=10001111_2$ and $202=11001010_2$ can be obtained as: $$\begin{matrix} & 10001111 \\ \oplus & 11001010 \\ \hline & 01000101 \end{matrix}$$ Thus, $143\oplus 202=01000101_2=69$.

Based on this definition, the bitwise XOR has the following properties (straightforward to prove): $$\begin{align*} a\oplus b &\equiv b\oplus a && \text{commutativity law} \\\ (a\oplus b)\oplus c &\equiv a\oplus (b\oplus c) && \text{associativity law} \\\ a\oplus 0 &\equiv a && \text{identity law} \\\ a\oplus a &\equiv 0 && \text{inverse law} \end{align*}$$ (we invite you to derive these properties yourself)

Notice that addition and multiplication follow similar rules. The XOR-identity element is $0$ (just like in addition, while in multiplication it is $1$). However, interestingly, the XOR-inverse of every number is itself! (whereas in addition, this is only true for $0$, and in multiplication this is only true for $1$ and $-1$)

From these properties, we can also prove the following: $$a = b \Longleftrightarrow a\oplus c = b\oplus c$$ We can call this the cancellation law.

The forward direction ($a = b \Longrightarrow a\oplus c = b\oplus c$) is trivial. To prove the backward direction, let's assume that $a\oplus c = b\oplus c$. Then: $$\begin{align*} a\oplus c &= b\oplus c && \text{} \\\ (a\oplus c)\oplus c &= (b\oplus c)\oplus c && \text{Forward direction of the cancellation law} \\\ a\oplus (c\oplus c) &= b\oplus (c\oplus c) && \text{Associativity law} \\\ a\oplus 0 &= b\oplus 0 && \text{Inverse law} \\\ a &= b && \text{Identity law} \end{align*}$$ which is what we wanted to prove.

Time Complexity:

$O(4^{|S|})$

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester
Editorialist

This question is marked "community wiki".

asked 12 Dec '15, 19:53

kevinsogo's gravatar image

7★kevinsogo
1.7k471134
accept rate: 11%

edited 17 Dec '15, 15:47


link

answered 14 Dec '15, 20:59

shadek's gravatar image

3★shadek
10913
accept rate: 0%

edited 01 Jan '16, 14:06

For all those who got TLE in last task, % operator for them proved really costly :D

link

answered 14 Dec '15, 15:22

xariniov9's gravatar image

6★xariniov9
93218
accept rate: 8%

1

with % operator : https://www.codechef.com/viewsolution/8948976

without % : https://www.codechef.com/viewsolution/8910699

I calculted the number of subsets, with XOR equal to value of the image represented as a binary number.

(14 Dec '15, 15:26) xariniov96★

Yep! I removed all the MOD's and just calculated manually and it got me AC. Its a really efficient optimization here.

(14 Dec '15, 15:39) h1ashdr@gon3★

I wanted to know if the solution mentioned in the editorial is a DP with bitmask or just a normal DP approach..?

link

answered 16 Dec '15, 19:22

sharad07's gravatar image

4★sharad07
20711
accept rate: 3%

edited 18 Dec '15, 10:29

Normal DP approach, not a bitwise-DP For more info read at https://discuss.codechef.com/questions/77747/how-the-recursion-for-cheffilt-works

(16 Dec '15, 21:06) pulkitsinghal6★

Thnk you..

(16 Dec '15, 21:42) sharad074★

This is my code https://www.codechef.com/viewsolution/8975829 and I have got 50points for this. The last test case gives TLE and I have no idea what I'm missing. Can anybody help me by finding the mistake.

link

answered 18 Dec '15, 17:54

snowwhite_1994's gravatar image

2★snowwhite_1994
813
accept rate: 0%

Your approach is O(N∗1024∗T). You need to be lucky to pass with that solution. Try the approach mentioned in the editorial O(T10241024).

(18 Dec '15, 18:00) xariniov96★

@xariniov Few of them passed all test cases with the same complexity.So I was wondering whats wrong with my code.

(18 Dec '15, 18:01) snowwhite_19942★

Mine also did pass all the test cases during the contest. I'm not sure, if they add stronger test cases for practice problem or it might be a case that your solution has a bigger hidden constant factor.

(18 Dec '15, 18:05) xariniov96★

Unfortunately, some $O(N*1024*T)$ solutions passed as well.

link

answered 14 Dec '15, 16:10

animesh_f's gravatar image

6★animesh_f ♦
8631318
accept rate: 9%

solution links not woking :(

link

answered 15 Dec '15, 01:34

codedog29's gravatar image

3★codedog29
556
accept rate: 0%

using Gaussian elimination : https://www.codechef.com/viewsolution/8922862

link

answered 15 Dec '15, 07:40

prikshit_47's gravatar image

3★prikshit_47
111
accept rate: 0%

can some body tell me what i am missing. i could'nt figure out where i was failing..! https://www.codechef.com/viewsolution/8947831

link

answered 14 Dec '15, 15:21

vishalgupta94's gravatar image

1★vishalgupta94
11
accept rate: 0%

I did it using O(N x 1024 x T) and it passed.Lucky for me. Can anyone explain why it happened?.I mean for N=100000,T=5 it becomes O(100000x1024x5).I too was surprised when it did not give tle. I used bottom-up and optimised mod using if(a>=mod)a-=mod;

link

answered 14 Dec '15, 18:53

parijat_196's gravatar image

2★parijat_196
1
accept rate: 0%

Has anyone done it using Gauss elimination? A link to the solution would be great.

link

answered 14 Dec '15, 19:02

rydeldcosta's gravatar image

4★rydeldcosta
1
accept rate: 0%

How can i access setter's and tester's solution, it shows access denied when clicked?

link

answered 15 Dec '15, 18:30

saar2119's gravatar image

5★saar2119
1213
accept rate: 0%

link

answered 15 Dec '15, 20:41

shivamg_isc's gravatar image

5★shivamg_isc
32618
accept rate: 0%

In editorialist's solution why is there condition (if j<=j^i )in second loop of calculation of do solution?

link

answered 22 Dec '15, 15:44

yougaindra's gravatar image

3★yougaindra
913
accept rate: 0%

The line that follows that tries to perform two operations at once:

"new_v[j] = (v[j] + v[j^i]) * p2[c[i]-1] % mod" and "new_v[j^i] = (v[j] + v[j^i]) * p2[c[i]-1] % mod"

This assigns the same value to two indices: j and j^i. However, without "j <= (j^i)", this will be done twice (once for j and another for j^i), so the answer will be incorrect. We need "j <= (j^i)" for this to be only done once.

(17 Mar '16, 15:20) kevinsogo7★

The Problem Setter's solution is not available. Could someone please help me with that. Thank you.

link

answered 23 May '16, 22:27

sidgairo18's gravatar image

3★sidgairo18
1
accept rate: 0%

Why does my solution get a WA verdict? Also, why does it TLE in the last subtask?

My Solution

Complexity: O(1024*1024)

Thanks in Advance!

link

answered 24 May '16, 11:37

arpanb8's gravatar image

3★arpanb8
120210
accept rate: 13%

i think its because of using maps....

(24 May '16, 12:18) anupam_datta4★
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:

×11,355
×2,592
×1,179
×173

question asked: 12 Dec '15, 19:53

question was seen: 6,206 times

last updated: 24 May '16, 12:18