codeforces-scrape

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

2023A.md (2922B)


      1 Source: https://codeforces.com/problemset/problem/2023/A
      2 
      3 A. Concatenation of Arrays
      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 You are given $n$ arrays $a_1$, $\ldots$, $a_n$. The length of each array is two. Thus, $a_i = [a_{i, 1}, a_{i, 2}]$. You need to concatenate the arrays into a single array of length $2n$ such that the number of inversions$^{\dagger}$ in the resulting array is minimized. Note that you do not need to count the actual number of inversions.
     22 
     23 More formally, you need to choose a permutation$^{\ddagger}$ $p$ of length $n$, so that the array $b = [a_{p_1,1}, a_{p_1,2}, a_{p_2, 1}, a_{p_2, 2}, \ldots, a_{p_n,1}, a_{p_n,2}]$ contains as few inversions as possible.
     24 
     25 $^{\dagger}$The number of inversions in an array $c$ is the number of pairs of indices $i$ and $j$ such that $i \lt j$ and $c_i \gt c_j$.
     26 
     27 $^{\ddagger}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     28 
     29 Input
     30 
     31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of arrays.
     34 
     35 Each of the following $n$ lines contains two integers $a_{i,1}$ and $a_{i,2}$ ($1 \le a_{i,j} \le 10^9$) — the elements of the $i$-th array.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     38 
     39 Output
     40 
     41 For each test case, output $2n$ integers — the elements of the array you obtained. If there are multiple solutions, output any of them.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 2
     51 
     52 1 4
     53 
     54 2 3
     55 
     56 3
     57 
     58 3 2
     59 
     60 4 3
     61 
     62 2 1
     63 
     64 5
     65 
     66 5 10
     67 
     68 2 3
     69 
     70 9 6
     71 
     72 4 1
     73 
     74 8 7
     75 
     76 1
     77 
     78 10 20
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 2 3 1 4
     85 2 1 3 2 4 3
     86 4 1 2 3 5 10 8 7 9 6
     87 10 20
     88 ```
     89 
     90 Note
     91 
     92 In the first test case, we concatenated the arrays in the order $2, 1$. Let's consider the inversions in the resulting array $b = [2, 3, 1, 4]$:
     93 
     94 * $i = 1$, $j = 3$, since $b_1 = 2 \gt 1 = b_3$;
     95 * $i = 2$, $j = 3$, since $b_2 = 3 \gt 1 = b_3$.
     96 
     97 Thus, the number of inversions is $2$. It can be proven that this is the minimum possible number of inversions.
     98 
     99 In the second test case, we concatenated the arrays in the order $3, 1, 2$. Let's consider the inversions in the resulting array $b = [2, 1, 3, 2, 4, 3]$:
    100 
    101 * $i = 1$, $j = 2$, since $b_1 = 2 \gt 1 = b_2$;
    102 * $i = 3$, $j = 4$, since $b_3 = 3 \gt 2 = b_4$;
    103 * $i = 5$, $j = 6$, since $b_5 = 4 \gt 3 = b_6$.
    104 
    105 Thus, the number of inversions is $3$. It can be proven that this is the minimum possible number of inversions.
    106 
    107 In the third test case, we concatenated the arrays in the order $4, 2, 1, 5, 3$.