codeforces-scrape

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

1473C.md (2402B)


      1 Source: https://codeforces.com/problemset/problem/1473/C
      2 
      3 C. No More Inversions
      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 have a sequence $a$ with $n$ elements $1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)$ ($k \le n \lt 2k$).
     22 
     23 Let's call as inversion in $a$ a pair of indices $i \lt j$ such that $a[i] \gt a[j]$.
     24 
     25 Suppose, you have some permutation $p$ of size $k$ and you build a sequence $b$ of size $n$ in the following manner: $b[i] = p[a[i]]$.
     26 
     27 Your goal is to find such permutation $p$ that the total number of inversions in $b$ doesn't exceed the total number of inversions in $a$, and $b$ is lexicographically maximum.
     28 
     29 Small reminder: the sequence of $k$ integers is called a permutation if it contains all integers from $1$ to $k$ exactly once.
     30 
     31 Another small reminder: a sequence $s$ is lexicographically smaller than another sequence $t$, if either $s$ is a prefix of $t$, or for the first $i$ such that $s_i \ne t_i$, $s_i \lt t_i$ holds (in the first position that these sequences are different, $s$ has smaller number than $t$).
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     36 
     37 The first and only line of each test case contains two integers $n$ and $k$ ($k \le n \lt 2k$; $1 \le k \le 10^5$) — the length of the sequence $a$ and its maximum.
     38 
     39 It's guaranteed that the total sum of $k$ over test cases doesn't exceed $10^5$.
     40 
     41 Output
     42 
     43 For each test case, print $k$ integers — the permutation $p$ which maximizes $b$ lexicographically without increasing the total number of inversions.
     44 
     45 It can be proven that $p$ exists and is unique.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 1 1
     54 2 2
     55 3 2
     56 4 3
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 1 
     63 1 2 
     64 2 1 
     65 1 3 2
     66 ```
     67 
     68 Note
     69 
     70 In the first test case, the sequence $a = [1]$, there is only one permutation $p = [1]$.
     71 
     72 In the second test case, the sequence $a = [1, 2]$. There is no inversion in $a$, so there is only one permutation $p = [1, 2]$ which doesn't increase the number of inversions.
     73 
     74 In the third test case, $a = [1, 2, 1]$ and has $1$ inversion. If we use $p = [2, 1]$, then $b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]$ and also has $1$ inversion.
     75 
     76 In the fourth test case, $a = [1, 2, 3, 2]$, and since $p = [1, 3, 2]$ then $b = [1, 3, 2, 3]$. Both $a$ and $b$ have $1$ inversion and $b$ is the lexicographically maximum.