All submissions for this problem are available.
Chef has a set of very large set of very important data he doesn't want to lose. Chef has a number of servers on which he stores the data. To store the data, Chef begins by splitting his data into chunks. Then he assigns a set of chunks to each server. For the sake of redundancy, the same chunk may be assigned to multiple servers. If multiple chunks are assigned to the same server, there will not be enough space to store all of the chunks individually, so instead the chunks are combined together. When multiple chunks are combined together it is no longer possible to retrieve the data from the original chunks. However, by combining data from multiple servers it may be possible to retrieve the original data.
Denote A ⊕ B as the result of combining chunks A and B. The following properties hold:
- A ⊕ B = B ⊕ A
- (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
- (A ⊕ A) ⊕ B = B
Note that the first two properties imply that when combining more than two chunks, the order in which they are combined does not matter.
Let's consider an example (this example will coincide with the sample input below). There are 4 chunks of data, and 6 servers. Denote Ci (0 ≤ i < 4) as the original chunks of data, and Sj (0 ≤ j < 6) as the data stored on the servers. Chef combines chunks as follows:
- S0 = C2
- S1 = C0 ⊕ C3
- S2 = C0 ⊕ C2
- S3 = C1 ⊕ C3
- S4 = C0 ⊕ C1 ⊕ C2
- S5 = C0 ⊕ C1
One way Chef may recover the original data is as follows:
- C0 = S0 ⊕ S2
- C1 = S2 ⊕ S4
- C2 = S0
- C3 = S2 ⊕ S3 ⊕ S4
Chef is now interested in how safe his data is. If the data from some servers is lost it may be impossible to recover the original data. Chef would like you to find a set of servers such that simultaneous failure would make some part of his data irrecoverable. Chef prefers that you find a small set of servers, but does not require minimality. Smaller sets will score more points.
Each test file contains only one test case.
The first line of input contains 2 space-separated integers N and S, denoting the number of chunks and number of servers, respectively. Then S lines follow, each with a description of the chunks stored on one server. A server description consists of an integer C denoting the number of chunks assigned to this server, followed by C integers denoting the ids of the chunks assigned to this server. Chunks are numbered from 0 to N−1 and servers numbered 0 to S−1.
First output an integer K, the number of failing servers in your solution. Then output the distinct ids of the failing servers.
- 50 ≤ N ≤ 200
- 2*N ≤ S ≤ 1000
- 1 ≤ C ≤ N
- Each server stores distinct chunks.
- Chef can recover the original data if no servers are lost.
- All official test files are generated by the method written in Test Case Generation.
Note that the following Sample Input does not satisfy the constraints.
Your score for each test file is 10*K/(S−N+1). The total score is the average of scores over all test files. The goal is to minimize your score.
Input: 4 6 1 2 2 0 3 2 0 2 2 1 3 3 0 1 2 2 0 1 Output: 1 2
This sample output would score 10*1/(6−4+1) = 3.333.... If server 2 is lost, there is no way to recover data chunks 0, 1, or 3.
Test Case Generation
The judge has 40 official test files.
An integer N is chosen randomly and uniformly between 50 and 200, inclusive. Then an integer S is chosen randomly and uniformly between 2*N and 1000, inclusive. A real number P is chosen randomly and uniformly between 0.3 and 0.8, inclusive, and each chunk is assigned to each server with probability P. The order of the chunks assigned to each server is shuffled.
If a generated test does not satisfy the constraints, then the test is discarded.
|Tags||april13, bitwise, challenge, gauss-elim, pieguy|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.