Quick Sort solution codeforces

Quick Sort solution codeforces – You are given a permutation 𝑝p of length 𝑛n and a positive integer 𝑘𝑛k≤n.

Quick Sort solution codeforces

In one operation, you:

  • Choose 𝑘k distinct elements 𝑝𝑖1,𝑝𝑖2,,𝑝𝑖𝑘pi1,pi2,…,pik.
  • Remove them and then add them sorted in increasing order to the end of the permutation.

For example, if 𝑝=[2,5,1,3,4]p=[2,5,1,3,4] and 𝑘=2k=2 and you choose 55 and 33 as the elements for the operation, then [2,5,1,3,4][2,1,4,3,5][2,5,1,3,4]→[2,1,4,3,5].

Find the minimum number of operations needed to sort the permutation in increasing order. It can be proven that it is always possible to do so.

 A permutation of length 𝑛n is an array consisting of 𝑛n distinct integers from 11 to 𝑛n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (𝑛=3n=3 but there is 44 in the array).

Quick Sort solution codeforces

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑘k (2𝑛1052≤n≤1051𝑘𝑛1≤k≤n).

The second line of each test case contains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n). It is guaranteed that 𝑝p is a permutation.

Wonderful Jump solution codeforces

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

Output

For each test case output a single integer — the minimum number of operations needed to sort the permutation. It can be proven that it is always possible to do so.

Quick Sort solution codeforces

input

Copy
4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4

output

Copy
0
1
1
2

Quick Sort solution codeforces

In the first test case, the permutation is already sorted.

In the second test case, you can choose element 33, and the permutation will become sorted as follows: [3,1,2][1,2,3][3,1,2]→[1,2,3].

In the third test case, you can choose elements 33 and 44, and the permutation will become sorted as follows: [1,3,2,4][1,2,3,4][1,3,2,4]→[1,2,3,4].

In the fourth test case, it can be shown that it is impossible to sort the permutation in 11 operation. However, if you choose elements 22 and 11 in the first operation, and choose elements 33 and 44 in the second operation, the permutation will become sorted as follows: [2,3,1,4][3,4,1,2][1,2,3,4][2,3,1,4]→[3,4,1,2]→[1,2,3,4].

Leave a Reply

Your email address will not be published. Required fields are marked *