To challenge or not
All submissions for this problem are available.
Chef became the problem writer of ACM/ICPC regional contest this year. One week before the contest, Chef came up with an interesting idea, and wrote the following problem :
Given N integers A1, A2, ..., An, print YES (or NO) if there exists (or not) 3 numbers that form an arithmetic sequence. All integers are between 0 and 99999 (inclusive).
As Chef expected, during the contest, most teams cannot figure out an efficient algorithm to solve it. But in the last minute of the contest, judges get one 10-lines submission, which is judged as correct. The short solution works as follows, if N > 2000, output YES, otherwise brute-force it.
Chef felt extremely disappointed, and he/she believed that the solution is definitely wrong. Chef is now interested in how to challenge the submission.
Chef needs your help. Chef would like you to find a set of integers, such that no 3 integers form an arithmetic sequence. To make the task more challenging, you are given a list of M integers B1, B2, ..., BM. You can only use integers from this list. The set does not require maximality, but larger sets will score more points.
The first line of the input contains an integer M denoting the length of the list. The second line contains M space-separated integers B1, B2, ..., BM denoting the list.
First output the integer N on the first line. Then output N integers A1, A2, ..., AN on the second line.
- 1 ≤ M ≤ 100000
- 0 ≤ Bi < 100000 for each 1 ≤ i ≤ M
Your score for each test file is 100*N/M. Your overall score is the average of your scores on the individual test files. The goal is to maximize your score.
Input: 10 1 2 3 4 5 6 7 8 9 10 Output: 4 1 4 6 9
This sample output would score 100*4/10=40.
We have 50 official test cases, each of them is created as follows:
An integer L is chosen from [10000, 100000] uniformly at random. An real value p is chosen from [0.1, 0.9] uniformly at random. Then each number x from [0, L - 1], x is added into the list with probability p, independently. Regenerate the list if it's empty.
|Tags||ACRush, challenge, june13|
|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.