### PROBLEM LINK

### DIFFICULTY

CHALLENGE

### PREREQUISITES

Ad-Hoc

### PROBLEM

You are given a sequence of **N** numbers. You have to sort them in **increasing** order. You have only **one operation** available to you, and that is to sort a **block of K** numbers in **increasing** order.

Sort the given sequence of numbers such that the number of operations used are **as few as possible**. The scoring function for the problem rewards

(number of operations used) * K

for each test. The total score is the sum of scores across the entire set of tests. The objective to to **minimize** the total score achieved.

### EXPLANATION

For the purpose of this editorial, we will discuss how to solve this problem without bearing any **penalty** score of **10,000,000** for any test case.

The problem clearly states that you are allowed to make at most **(N*N / K + 1000)** operations. This limit was carefully created to ensure that each test is **easily** solvable without bearing the penalty score, and the **judge program** cannot be forced to execute too long to evaluate a solution.

Firstly, it is easy to solve the problem within the given limits without even caring what sequence of numbers is given. We can repeatedly run the operation with only the **last cell from the last operation overlapping**. This ensures that the largest elements bubble to the end of the array. But this naive procedure may generate too many operations in the worst case (the program may pass if it stops after reaching maximum number of allowed operations).

Consider the following, slightly less trivial procedure.

Let us suppose that the position of the **largest element in the array** is **x**. We wish to move **x** to the end of the array. This can be done by repeatedly applying the operation

- First at
**x** - Next at
**x + K - 1** - Next at
**x + 2*K - 2** - and so on…

Hence, in at most **ceil((N-x)/(K-1))** moves, we can move the largest element in the array to the end of the array. We can now look for the position for the second largest element and move it to the end of the array.

This way, it can be ensured that there is an answer within the limit of the steps enforced.

## K = 2

For **K = 2**, this problem has an exact solution. The problem is equivalent to the problem of finding the number of inversions in the given array. The exact answer can be found by performing a **bubble sort** and print the sequence of swaps made.

The hardness of finding the answer, even for **K = 3**, inspired this challenge.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Will be uploaded shortly.