codeforces-scrape

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

1790C.md (2742B)


      1 Source: https://codeforces.com/problemset/problem/1790/C
      2 
      3 C. Premutation
      4 
      5 time limit per test
      6 
      7 3 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 A sequence of $n$ numbers is called permutation if it contains all integers from $1$ to $n$ exactly once. For example, the sequences [$3, 1, 4, 2$], [$1$] and [$2,1$] are permutations, but [$1,2,1$], [$0,1$] and [$1,3,4$] — are not.
     22 
     23 Kristina had a permutation $p$ of $n$ elements. She wrote it on the whiteboard $n$ times in such a way that:
     24 
     25 * while writing the permutation at the $i$-th ($1 \le i \le n)$ time she skipped the element $p_i$
     26 
     27 So, she wrote in total $n$ sequences of length $n-1$ each.
     28 
     29 For example, suppose Kristina had a permutation $p$ = $[4,2,1,3]$ of length $4$. Then she did the following:
     30 
     31 1. Wrote the sequence $[2, 1, 3]$, skipping the element $p_1=4$ from the original permutation.
     32 2. Wrote the sequence $[4, 1, 3]$, skipping the element $p_2=2$ from the original permutation.
     33 3. Wrote the sequence $[4, 2, 3]$, skipping the element $p_3=1$ from the original permutation.
     34 4. Wrote the sequence $[4, 2, 1]$, skipping the element $p_4=3$ from the original permutation.
     35 
     36 You know all $n$ of sequences that have been written on the whiteboard, but you do not know the order in which they were written. They are given in arbitrary order. Reconstruct the original permutation from them.
     37 
     38 For example, if you know the sequences $[4, 2, 1]$, $[4, 2, 3]$, $[2, 1, 3]$, $[4, 1, 3]$, then the original permutation will be $p$ = $[4, 2, 1, 3]$.
     39 
     40 Input
     41 
     42 The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     43 
     44 The description of the test cases follows.
     45 
     46 The first line of each test case contains one integer $n$ ($3 \le n \le 100$).
     47 
     48 This is followed by $n$ lines, each containing exactly $n-1$ integers and describing one of the sequences written out on the whiteboard.
     49 
     50 It is guaranteed that all sequences could be obtained from some permutation $p$, and that the sum $n^2$ over all input sets does not exceed $2 \cdot 10^5$.
     51 
     52 Output
     53 
     54 For each test case, output on a separate line a permutation $p$ such that the given $n$ sequences could be obtained from it.
     55 
     56 It is guaranteed that the answer exists and it is the only one. In other words, for each test case the required permutation is sure to exist.
     57 
     58 Example
     59 
     60 Input
     61 
     62 ```
     63 5
     64 
     65 4
     66 
     67 4 2 1
     68 
     69 4 2 3
     70 
     71 2 1 3
     72 
     73 4 1 3
     74 
     75 3
     76 
     77 2 3
     78 
     79 1 3
     80 
     81 1 2
     82 
     83 5
     84 
     85 4 2 1 3
     86 
     87 2 1 3 5
     88 
     89 4 2 3 5
     90 
     91 4 1 3 5
     92 
     93 4 2 1 5
     94 
     95 4
     96 
     97 2 3 4
     98 
     99 1 3 4
    100 
    101 1 2 3
    102 
    103 1 2 4
    104 
    105 3
    106 
    107 2 1
    108 
    109 1 3
    110 
    111 2 3
    112 ```
    113 
    114 Output
    115 
    116 ```
    117 4 2 1 3 
    118 1 2 3 
    119 4 2 1 3 5 
    120 1 2 3 4 
    121 2 1 3
    122 ```
    123 
    124 Note
    125 
    126 The first test case is described in the problem statement.
    127 
    128 In the second test case, the sequences are written in the correct order.