PROBLEM LINK:Author: Antoniuk Vasyl DIFFICULTY:challenge PREREQUISITES:greedy, randomized algorithm PROBLEM:Given an array $a$ of size $3 * n$. You need to choose as many triplets as you can such that their sum is equal and no element of the array is part of more than one triplet. EXPLANATION:Guessing a desired sum of triplet ACRush chooses value of target sum using some huristics.
Please see following part of his code for choosing the target sum s.
Ceiks choose the target sum to be the average value of an triplet of the array, (i.e. 3 * sum of elements / (3 * n)). zlobober uses the following code for determining the target sum
Finding maximum number of triplets for a fixed sum ACRush has used this greedy approach with a modification. You can employ some other greedy strategies for searching triplets for a fixed sum. One huristics you may apply is to fix the largest element a[z] in the sum (expected to be found in the last 1/3 part of array) and then search for x, y such that a[x] + a[y] = s  a[z]. Now, search for such a[x] + a[y] in the initial part of the array. ceiks divides all the elements of the array into several bins w.r.t their values modulo numberOfBeans, where numberOfBeans is a predetermined constant. One could also guess whether the distribution of the test set, i.e. whether the test file is generated using Type 1 method or Type 2 method as described in the problem statement. For details of it, you can see code of zlobober for it. Please share your strategies for the problem !! It would be really great learning experience for others. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 11 Jan '16, 09:59

I have always wondered something. Since you guys run the submissions on all the files during the contest anyway, why not maintain a hidden ranklist in the background, which is being structured according to score from the visible AND hidden test cases. Then, when the contest is over, just replace it with the one that has only prelim case results on it. Doesn't make sense to run it all over again, does it? answered 11 Jan '16, 22:15

I'll share some tests instead. The filenames are in the form $\texttt{t#1\_m#2\_n#3}$, where #1 is the group type, #2 roughly the maximum element (there are groups for max <= 2e3, 2e4, 2e5, 2e6, 2e8, 2e9) and #3 the number of the test (4 within each group). All elements are nonnegative there. answered 11 Jan '16, 15:16

When final score for my submissions will be revealed? In my submissions I see results for first 4 test only. And it will be great if author reveal precise generator params for all tests. answered 11 Jan '16, 20:48
