Editorial for COCI '11 Contest 6 #5 Pastele
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's formulate the expression for colorfulness of some set:
This can be rewritten as:
If we look at , , and 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 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 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 of the points.
Finally, we can use binary search to find the smallest cube with one corner fixed that contains at least points.
Comments