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.