Sereja and Sorting 2
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja has an array A[1 .. N], which contains N integers. Now Sereja wants to sort it.
The only thing that Sereja can do, is to reverse all elements in some sub-array, which is a consecutive parts of A. In other words, in one operation, Sereja can choose two integers L and R (1 <= L < R <= N), and swap elements A[L] and A[R], A[L+1] and A[R-1], A[L+2] and A[R-2] and so on.
In such operation of L, R, the total energy that Sereja spends R - L + 1. Clearly, Sereja wants to minimize the spent energy. Also, Sereja would like to minimize the total number of all operations. Therefore, we give a mixed objective as shown in Scoring.
First line contains an integer N. Next line contains a sequence of integers A, A, A, ..., A[N].
First line contains an integer Q - the total number of operations you need to sort the array. In each of next Q lines, there should be two integers L and R (1 <= L < R <= N) indicate the operation that Sereja should do.
Also you should remember, that Q shouldn't be greater than N.
Suppose S is the total spent energy of your output, i.e. the sum of R - L + 1 of all operations. Your score is S / N + Q. Lower scores will earn more points.
We have 40 official test files. You must correctly solve all test files to receive OK. During the contest, your overall score is the sum of the scores on the first 10 test files. After the contest, all solutions will be rescored by the sum of the scores on the rest 10 test files. Note, that public part of the tests may not contain some border cases.
- 1 <= N <= 10000
- 1 <= A[i] <= 5000
Input: 6 2 1 5 4 3 2 Output: 2 3 6 1 2
|Tags||challenge, greedy, heuristic, march14, sereja, test-gen-plans|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.