Sereja and Shuffling
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja have an array A = [A1, A2, ..., AN], where N is an even integer. Let the function f(A) be defined by f(A) = |(A1 + A2 + ... + AN/2) − (AN/2+1 + AN/2+2 + ... + AN)|. Sereja want to decrease the value f(A) by the unusual way.
Let A[l..r] denote the sub-array [Al, Al+1, ..., Ar] of A. Sereja can shift some sub-array A[l..r], where 1 ≤ l ≤ r ≤ N, then the array A will become [A1, A2, ..., Al-1, Al+1, Al+2, ..., Ar, Al, Ar+1, Ar+2, ..., AN]. For example we have the array A = [1, 2, 3, 4, 5] and we choose l = 2, r = 4, then after shifting we have the following array: A = [1, 3, 4, 2, 5].
Sereja can shift multiple times, however it's burdensome to shift many elements. Thus the sum of r − l + 1 should not exceed 2 × N.
Please help Sereja to find the way for decreasing the value f(A) = |(A1 + A2 + ... + AN/2) − (AN/2+1 + AN/2+2 + ... + AN)| as much as possible. Note that you don't have to minimize the value f(A), but the smaller value will give the higher score.
Each test file contains only one test case.
The first line of input contains an integer N, denoting the length of the array. Then the next line contains N space-separated integers A1, A2, ..., AN.
The first line should contain an integer q, denoting the number of shifts. Then the kth line of the next q lines should contain two space-separated integers l and r, denoting the kth shift, where 1 ≤ l ≤ r ≤ N.
- 2 ≤ N ≤ 100000, that is, 2 ≤ N ≤ 105
- 0 ≤ Ak ≤ 1000000000, that is, 0 ≤ Ak ≤ 109
- N is even
Input 1: 6 1 2 3 4 5 6 Output 1: 2 1 6 1 6 Input 2: 4 1 2 2 3 Output: 2 1 2 2 3
Let INIT be the initial value of f(A), and S be the value of f(A) after shifting denoted by output. For each test file, your score is calculated as (INIT − S) / INIT, where you can assume INIT ≠ 0 for all official test files. Then the total your score is defined as the average of your score for the test files (see the next paragraph, for more details). The aim for this problem is to maximize the total your score.
We have 20 official test files. You must correctly solve and decrease the value f(A) strictly for all test files to receive Accepted. Invalid outputs, or S ≥ INIT for some test cases will lead Wrong Answer. You can assume that one can get Accepted for the official test files.
During the contest, the scores of the last 16 test files are 0, that is, the total your score is calculated by only the first 4 tests. After the contest, all solutions will be rescored by the average of the scores of the all 20 test files, and it will be the final score.
About Generating Tests
At first we choose 1-1 or 1-2 or 2-1 or 2-2 randomly, and each probability is 0.25. If we choose t here, then the test case is generated by the following TYPE t.
TYPE 1-1: N is chosen from [1, 105] uniformly and randomly. If N is odd, N is added by 1. Then each Ak is chosen from [0, 109] uniformly and randomly and independently.
TYPE 1-2: N is chosen from [1, 105] uniformly and randomly. If N is odd, N is added by 1. Then N real values y1, y2, ..., yN are chosen from [0, 9) uniformly and randomly and independently. And each Ak is set floor(10yk).
TYPE 2-1: A real value x is chosen from [2, 5) uniformly and randomly, and we set N = floor(10x). If N is odd, N is added by 1. Then each Ak is chosen from [0, 109] uniformly and randomly and independently.
TYPE 2-2: A real value x is chosen from [2, 5) uniformly and randomly, and we set N = floor(10x). If N is odd, N is added by 1. Then N real values y1, y2, ..., yN are chosen from [0, 9) uniformly and randomly and independently. And each Ak is set floor(10yk).
|Tags||aug14, challenge, greedy, heuristic, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.