codeforces-scrape

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

1650D.md (3957B)


      1 Source: https://codeforces.com/problemset/problem/1650/D
      2 
      3 D. Twist the Permutation
      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 Petya got an array $a$ of numbers from $1$ to $n$, where $a[i]=i$.
     22 
     23 He performed $n$ operations sequentially. In the end, he received a new state of the $a$ array.
     24 
     25 At the $i$-th operation, Petya chose the first $i$ elements of the array and cyclically shifted them to the right an arbitrary number of times (elements with indexes $i+1$ and more remain in their places). One cyclic shift to the right is such a transformation that the array $a=[a_1, a_2, \dots, a_n]$ becomes equal to the array $a = [a_i, a_1, a_2, \dots, a_{i-2}, a_{i-1}, a_{i+1}, a_{i+2}, \dots, a_n]$.
     26 
     27 For example, if $a = [5,4,2,1,3]$ and $i=3$ (that is, this is the third operation), then as a result of this operation, he could get any of these three arrays:
     28 
     29 * $a = [5,4,2,1,3]$ (makes $0$ cyclic shifts, or any number that is divisible by $3$);
     30 * $a = [2,5,4,1,3]$ (makes $1$ cyclic shift, or any number that has a remainder of $1$ when divided by $3$);
     31 * $a = [4,2,5,1,3]$ (makes $2$ cyclic shifts, or any number that has a remainder of $2$ when divided by $3$).
     32 
     33 Let's look at an example. Let $n=6$, i.e. initially $a=[1,2,3,4,5,6]$. A possible scenario is described below.
     34 
     35 * $i=1$: no matter how many cyclic shifts Petya makes, the array $a$ does not change.
     36 * $i=2$: let's say Petya decided to make a $1$ cyclic shift, then the array will look like $a = [\textbf{2}, \textbf{1}, 3, 4, 5, 6]$.
     37 * $i=3$: let's say Petya decided to make $1$ cyclic shift, then the array will look like $a = [\textbf{3}, \textbf{2}, \textbf{1}, 4, 5, 6]$.
     38 * $i=4$: let's say Petya decided to make $2$ cyclic shifts, the original array will look like $a = [\textbf{1}, \textbf{4}, \textbf{3}, \textbf{2}, 5, 6]$.
     39 * $i=5$: let's say Petya decided to make $0$ cyclic shifts, then the array won't change.
     40 * $i=6$: let's say Petya decided to make $4$ cyclic shifts, the array will look like $a = [\textbf{3}, \textbf{2}, \textbf{5}, \textbf{6}, \textbf{1}, \textbf{4}]$.
     41 
     42 You are given a final array state $a$ after all $n$ operations. Determine if there is a way to perform the operation that produces this result. In this case, if an answer exists, print the numbers of cyclical shifts that occurred during each of the $n$ operations.
     43 
     44 Input
     45 
     46 The first line of the input contains an integer $t$ ($1 \le t \le 500$) — the number of test cases in the test.
     47 
     48 The descriptions of the test cases follow.
     49 
     50 The first line of the description of each test case contains one integer $n$ ($2 \le n \le 2\cdot10^3$) — the length of the array $a$.
     51 
     52 The next line contains the final state of the array $a$: $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) are written. All $a_i$ are distinct.
     53 
     54 It is guaranteed that the sum of $n$ values over all test cases does not exceed $2\cdot10^3$.
     55 
     56 Output
     57 
     58 For each test case, print the answer on a separate line.
     59 
     60 Print -1 if the given final value $a$ cannot be obtained by performing an arbitrary number of cyclic shifts on each operation. Otherwise, print $n$ non-negative integers $d_1, d_2, \dots, d_n$ ($d_i \ge 0$), where $d_i$ means that during the $i$-th operation the first $i$ elements of the array were cyclic shifted to the right $d_i$ times.
     61 
     62 If there are several possible answers, print the one where the total number of shifts is minimal (that is, the sum of $d_i$ values is the smallest). If there are several such answers, print any of them.
     63 
     64 Example
     65 
     66 Input
     67 
     68 ```
     69 3
     70 
     71 6
     72 
     73 3 2 5 6 1 4
     74 
     75 3
     76 
     77 3 1 2
     78 
     79 8
     80 
     81 5 8 1 3 2 6 4 7
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 0 1 1 2 0 4 
     88 0 0 1 
     89 0 1 2 0 2 5 6 2
     90 ```
     91 
     92 Note
     93 
     94 The first test case matches the example from the statement.
     95 
     96 The second set of input data is simple. Note that the answer $[3, 2, 1]$ also gives the same permutation, but since the total number of shifts $3+2+1$ is greater than $0+0+1$, this answer is not correct.