You are not logged in. Please login at www.codechef.com to post your questions!

×

# SEASORT2 - Editorial

Author: Sergey Nagin
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

Challenge

# PREREQUISITES:

Heuristic, Greedy, Mixure of Methods, Test Generation Plans

# PROBLEM:

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.

# EXPLANATION:

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.

## Test Cases

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.

## Methods

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.

Because the winners' codes are tooooo complex to read, I would like to invite @kgcstar, @mugurelionut to explain their great methods.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 22 Mar '14, 08:06

161446375
accept rate: 0%

3★kcahdog
10.0k2854129

Tester's Solution link is not working!

(23 Mar '14, 17:02) 4★

 2 I want to add another simple method, which I think many top 20 competitor's used: Loop over the resting interval and group the same numbers together in the direction they are expected to end Example: 1 2 5 3 7 3 8 3 (solving it small to bigger, 1 and 2 are already in place) intuitive method from editorial: 1 2 5 3 7 3 8 3 1 2 3 5 7 3 8 3 // 1 1 2 3 3 7 5 8 3 // 3 1 2 3 3 3 8 5 7 // 4 bringing the 3's 1 by 1 together: 1 2 5 3 7 3 8 3 1 2 5 3 7 3 3 8 // 1 1 2 5 3 3 3 7 8 // 2 1 2 3 3 3 5 7 8 // 3  For this simple case our total window is only 6 vs 8 Plus the fact that you can take advantage of the fact when 2 same numbers are already together. Than you don't have to reverse. In that case we win an entire window. (according to how the score is calculated) answered 22 Mar '14, 16:03 5★samjay 427●1●5●10 accept rate: 10%
 1 @shangjingbo @samjay @mugurelionut The editorial places a lot of weightage on determining the nature of the test cases in the input file. Could you please some details or resources on how this is done ? What sort of code is used to do this ? It would be great if you could provide some hints. answered 22 Mar '14, 17:13 3★kcahdog 10.0k●28●54●129 accept rate: 14% mugurelionut has posted his methods. :) (24 Mar '14, 05:20)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,000
×847
×29
×20
×1

question asked: 22 Mar '14, 08:06

question was seen: 2,404 times

last updated: 29 Mar '14, 02:17