PROBLEM LINK:
Author: Praveen Dhinwa
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa
DIFFICULTY:
simple
PREREQUISITES:
basic implementation, arrays
PROBLEM:
Given two arrays X and Y of length N. Find out the maximum value returned by this program.
input: integer N, list X[1, 2, ..., N], list Y[1, 2, ..., N]
output: integer res
function:
set res = 0;
for i := 1 to N do
for j := 1 to N do
for k := 1 to N do
if (X[i] = X[j]) OR (X[j] = X[k]) OR (X[k] = X[i])
continue
else
set res = max(res, Y[i] + Y[j] + Y[k])
return res
SOLUTION
Note that we want to find the maximum value of Y[i] + Y[j] + Y[k] such that none of X[i], X[j] and X[k] are same.
We split the values array (X, Y) into groups of equal X values. This can be done by using a map data structure (map in C++). You can also do it using sorting.
For each of such group, we maintain the maximum Y value.
Now, we want to select three of the Y values from these groups.
Finally, if the number of such groups is at least 3, then we can pick the top 3 maximum of these Y values and output their sum.
Time complexity of this solution is \mathcal{O}(n \log n).