### 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*;

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.