codeforces-scrape

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

1903B.md (2115B)


      1 Source: https://codeforces.com/problemset/problem/1903/B
      2 
      3 B. StORage room
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 In Cyprus, the weather is pretty hot. Thus, Theofanis saw this as an opportunity to create an ice cream company.
     22 
     23 He keeps the ice cream safe from other ice cream producers by locking it inside big storage rooms. However, he forgot the password. Luckily, the lock has a special feature for forgetful people!
     24 
     25 It gives you a table $M$ with $n$ rows and $n$ columns of non-negative integers, and to open the lock, you need to find an array $a$ of $n$ elements such that:
     26 
     27 * $0 \le a_i \lt 2^{30}$, and
     28 * $M_{i,j} = a_i | a_j$ for all $i \neq j$, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR).
     29 
     30 The lock has a bug, and sometimes it gives tables without any solutions. In that case, the ice cream will remain frozen for the rest of eternity.
     31 
     32 Can you find an array to open the lock?
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \le t \le 10^{3}$) — the number of test cases.
     37 
     38 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{3}$) — the size of the hidden array.
     39 
     40 The next $n$ lines describe the rows of $M$, line $i$ contains the table values $M_{i,1}, M_{i,2}, \ldots, M_{i,n}$ ($0 \le M_{i,j} \lt 2^{30}$).
     41 
     42 It is guaranteed that $M_{i,i} = 0$ and $M_{i,j} = M_{j,i}$ for all $1 \le i,j \le n$.
     43 
     44 It is also guaranteed that the sum of $n$ over all test cases does not exceed $10^{3}$.
     45 
     46 Output
     47 
     48 For each test case, if there is a solution print YES and an array that satisfies the property, otherwise print NO.
     49 
     50 If there are multiple solutions, print any of them.
     51 
     52 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 4
     60 
     61 1
     62 
     63 0
     64 
     65 4
     66 
     67 0 3 3 5
     68 
     69 3 0 3 7
     70 
     71 3 3 0 7
     72 
     73 5 7 7 0
     74 
     75 5
     76 
     77 0 7 7 5 5
     78 
     79 7 0 3 2 6
     80 
     81 7 3 0 3 7
     82 
     83 5 2 3 0 4
     84 
     85 5 6 7 4 0
     86 
     87 3
     88 
     89 0 0 1
     90 
     91 0 0 0
     92 
     93 1 0 0
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 YES
    100 7
    101 YES
    102 1 3 2 5 
    103 YES
    104 5 2 3 0 4
    105 NO
    106 ```