PROBLEM LINK:
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[i];
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.