CHMKTRPS - Editorial

challenge
editorial
greedy
jan16

#1

PROBLEM LINK:

Practice
Contest

Author: Antoniuk Vasyl
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Praveen Dhinwa

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
First let us guess for possible values for sum of a triple.

ACRush chooses value of target sum using some huristics.
Please see following part of his code for choosing the target sum s.

const int w=(n/2-n%2%3);
const int sw=n/2-w/2;
const int tw=sw+w;
for (int i = sw; i <= tw; i++) s += a*;
s=(s+w/6)/(w/3);

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

llong determineOptSum() {
llong tot = accumulate(A, A + n, 0ll); // sum of array A
llong rem = tot % (n / 3);
if (rem < n / 6) {
return tot / (n / 3);
} else {
return tot / (n / 3) + 1;
}
}

Finding maximum number of triplets for a fixed sum
Now, for we know the sum of each triple. We can use the following greedy strategy for finding maximum number of triplets for this given sum.
At each point, we choose two random values in array x, y. We can search for value z in the array such that z = sum - x - y.
Note that this search can be faster if we maintain the array in sorted order.
After this, we erase all of these three points from the array.
All these operations can be implemented efficiently using stl:set in C++.

ACRush has used this greedy approach with a modification.
Now, instead of maintaining a set for deleting and inserting elements to check whether an element is used or not. He maintains a disjoint set union data structure, using that you an efficiently find the next available (not deleted yet) index j for an index i.
Time complexity of this method is O(n).

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.
Now, he reduces his search space for searching the triplets in the smaller bins.

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:

Author
Tester
Editorialist


#2

I’ll share some tests instead. The filenames are in the form exttt{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 non-negative there.


#3

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.


#4

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?


#5

I sure hope it’s not going to take a month like last time.