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≤105, 1≤𝑘≤𝑛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.
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
output
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].