Heuristic, Greedy, Mixure of Methods, Test Generation Plans
Sort a sequence only using reverse operations. Minimize the cost function, S/N+Q, where Q is the total operations, N is the length of the sequence, and S is the sum of lengths of intervals in all reverse operations.
This is a challenge problem. The most important thing in solving challenge problem is to find some approximation/partial methods using the combination of search, greedy, dynamic programming, etc…, because this challenge problem is NP-hard. Also, it is important to write a local test system to help you find the best strategy (almost all top ranked guys wrote their own test codes).
In this problem, there are two parts in the objective function: S/N and Q. Because N is a constant once the input is given, we need to find a trade-off between minimizing S and Q.
And, for the challenge problem, usually we can have the generation plans of test data. But, this time, the plan is omitted. Therefore, we need to get some senses of them in some special ways. For example, we can check, whether N lies in a range [Nmin, Nmax]. If not, make our submission to TLE or RE, or something you want. And then, try different ranges, and finally collect the information about the generation plans.
For the generation plans, you guys can have a look at the kgcstar’s code and mugurelionut’s code. Specifically, in kgcstar’s code, the solving methods are highly specialized for different files. And the comments in mugurelionut’s code tell us that
// Structure of the tests: // 1 test : 6 <= N <= 10 // 39 tests : 9000 < N <= 10000 // - 4 tests: 1000 <= ndif < 1050 // - 4 tests: 250 <= ndif <= 300 // - 11 tests: 100 < ndif <= 175 // - 4 tests: 80 < ndif <= 100 // - 4 tests: 60 < ndif <= 80 // - 4 tests: 30 < ndif <= 60 // - 8 tests: ndif <= 10
where, ndif is the number of different numbers in the input sequence.
After got some senses about the test cases, we need to find some strategies.
Note that there is a constraint that Q<=N. It is easy to achieve that, if we put numbers to their own position from left to right.
And then, if there are some numbers are already putted on correct places, i.e. [1…l] and [r… N] are correct, we can clearly reduced it to a problem of [l + 1 … r - 1].
So, the most straightforward algorithm is to greedily choose a smallest/largest number and put it to its correct position. Here, you can try different heuristic methods to choose the proper interval to reverse.
Further, you can not only put the smallest/largest number, but also try some complex methods to put some internal numbers to their correct positions, or divide the whole intervals into some separated intervals and then combine the results.