codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1761C.md (2474B)


      1 Source: https://codeforces.com/problemset/problem/1761/C
      2 
      3 C. Set Construction
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a binary matrix $b$ (all elements of the matrix are $0$ or $1$) of $n$ rows and $n$ columns.
     22 
     23 You need to construct a $n$ sets $A_1, A_2, \ldots, A_n$, for which the following conditions are satisfied:
     24 
     25 * Each set is nonempty and consists of distinct integers between $1$ and $n$ inclusive.
     26 * All sets are distinct.
     27 * For all pairs $(i,j)$ satisfying $1\leq i, j\leq n$, $b_{i,j}=1$ if and only if $A_i\subsetneq A_j$. In other words, $b_{i, j}$ is $1$ if $A_i$ is a proper subset of $A_j$ and $0$ otherwise.
     28 
     29 Set $X$ is a proper subset of set $Y$, if $X$ is a nonempty subset of $Y$, and $X \neq Y$.
     30 
     31 It's guaranteed that for all test cases in this problem, such $n$ sets exist. Note that it doesn't mean that such $n$ sets exist for all possible inputs.
     32 
     33 If there are multiple solutions, you can output any of them.
     34 
     35 Input
     36 
     37 Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. The description of test cases follows.
     38 
     39 The first line contains a single integer $n$ ($1\le n\le 100$).
     40 
     41 The following $n$ lines contain a binary matrix $b$, the $j$-th character of $i$-th line denotes $b_{i,j}$.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
     44 
     45 It's guaranteed that for all test cases in this problem, such $n$ sets exist.
     46 
     47 Output
     48 
     49 For each test case, output $n$ lines.
     50 
     51 For the $i$-th line, first output $s_i$ $(1 \le s_i \le n)$  — the size of the set $A_i$. Then, output $s_i$ distinct integers from $1$ to $n$  — the elements of the set $A_i$.
     52 
     53 If there are multiple solutions, you can output any of them.
     54 
     55 It's guaranteed that for all test cases in this problem, such $n$ sets exist.
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 2
     63 4
     64 0001
     65 1001
     66 0001
     67 0000
     68 3
     69 011
     70 001
     71 000
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 3 1 2 3
     78 2 1 3
     79 2 2 4
     80 4 1 2 3 4
     81 1 1
     82 2 1 2
     83 3 1 2 3
     84 ```
     85 
     86 Note
     87 
     88 In the first test case, we have $A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$. Sets $A_1, A_2, A_3$ are proper subsets of $A_4$, and also set $A_2$ is a proper subset of $A_1$. No other set is a proper subset of any other set.
     89 
     90 In the second test case, we have $A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$. $A_1$ is a proper subset of $A_2$ and $A_3$, and $A_2$ is a proper subset of $A_3$.