OPTCODE - Editorial

PROBLEM LINK:

Practice
Contest

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).

Setters and Tester Solution Codes

Setter’s solution
Tester’s solution

//