All submissions for this problem are available.
Sereja has an array of n integers a, a, ..., a[n]. In one move Sereja can do the following operation
Assume integers v and t, Where 1 ≤ v, t ≤ n, such that, all the elements of the array a[v], a[v + t], a[v + t * 2], ... a[v + t * k] Where k ≥ 0 are equal.
To delete all elements a[v], a[v + t], a[v + t * 2], ... a[v + t * k] from the array. The remaining elements are written in a without any gaps.
Note that you can not decide the value of k. After you decide the integers v and t, k will be set to the largest value possible. That is, the largest k such that v + t * k ≤ n. Your selection of v and t must satisfy the conditions described above for this value of k.
Sereja wants to delete the entire array. Help him delete all the elements of the array in the fewest number of moves. Since this is a Challenge Problem, your objective is to minimize the number of moves it takes to delete the entire array.
The first line contains an integer n, the size of the array. The second line contains integers a, a, ..., a[n], the integers written in the array.
For each test case print in the first line number q, the number of moves you will take. In next q lines print pairs of the integers v[i], t[i] (1 ≤ i ≤ q), the values for v and t that you assume during the move i. Be careful with the output sequence and output format. This problem uses a custom judge. Non adherence to the format may lead to verdicts like internal error, run time error and wrong answer.
- 1 ≤ n ≤ 100000
- 1 ≤ a[i] ≤ 100000
Input 1: 3 1 1 1 Output 1: 1 1 1 Input 2: 4 1 2 1 2 Output 2: 4 4 4 3 3 2 2 1 1 Input 3: 5 1 2 3 4 1 Output 3: 4 1 4 3 1 2 1 1 1
In the third case
- After the move 1 4, we remove 1st and 5th (1 + 4) number, and the array will become: 2 3 4.
- After the move 3 1, 4 will be omitted and the array will become 2 3. Note how the 1-based indexes now refer to the positions in the array [2, 3, 4] and not the positions of 2, 3, 4 in the original array.
- And after the following two commands 3 and 2 will be removed and the array will become empty.
If your program solves a test case, it receives the score of 100*q/n for that test case. Solving a test case means that the given array should be emptied using the given operation. Otherwise the test case is considered, not solved and the verdict Wrong Answer is provided. The total score of the program is simply the sum of the scores for each test files, divided by the number of test files (this is what the generic master judge does). Each test file has a single test case. Since the number of test files are same for everyone, this is effectively equal to the sum of scores for all the test files. In case it isn't apparent yet, the objective of this problem is to minimize your total score.
The tests are not randomly generated. Special properties are forced upon the generated array, which may or may not be different for each test case.
|Tags||ad-hoc, aug13, challenge, order-statistic, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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.