Editorial for COCI '11 Contest 6 #5 Pastele


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let's formulate the expression for colorfulness of some set:

\displaystyle \max_{i,j}(\max(|R_i-R_j|, |G_i-G_j|, |B_i-B_j|))

This can be rewritten as:

\displaystyle \max\left(\max_{i,j}(R_i-R_j), \max_{i,j}(G_i-G_j), \max_{i,j}(B_i-B_j)\right)

If we look at R, G, and B values of colors as points in space, colorfulness is equal to the largest side of the smallest bounding rectangular cuboid. Since values of the input coordinates are rather small, this leads us to a solution that traverses each of the possible rectangular cuboids and checks if there are at least K points inside it. The number of points in any rectangular cuboid can be found in constant complexity using the inclusion-exclusion principle. This solution earns 50\% of the points.

Since colorfulness is equal to the largest side, we won't lose anything if we check only cubes. This optimization will earn an additional 30\% of the points.

Finally, we can use binary search to find the smallest cube with one corner fixed that contains at least K points.


Comments

There are no comments at the moment.