×

# CHMKTRPS - Editorial

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

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.

# SAMPLE SOLUTIONS:

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

19.8k350498541

 2 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 757●2●11 accept rate: 16%
 1 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 non-negative there. answered 11 Jan '16, 15:16 7★xellos0 5.9k●5●43●93 accept rate: 10%
 0 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 7★argos 71●3 accept rate: 0% 2 I sure hope it's not going to take a month like last time. (11 Jan '16, 21:46) xellos07★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,024
×858
×106

question asked: 11 Jan '16, 09:59

question was seen: 2,301 times

last updated: 12 Mar '17, 20:10