Connection Status:
Competition Arena > ColorfulEnclosure

ColorfulEnclosure

2017 TCO Semi 1 · 2017-03-31 · by Kriii

2017 TCO Semi 1 · 2017-03-31 · by Kriii · Search
Class Name: ColorfulEnclosure
Return Type: long
Method Name: minArea
Arg Types: (int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Note: This problem has a nonstandard time limit: 4 seconds.

We have n points in the plane. The points are numbered 0 through n-1. You are given the coordinates of these points in the int[]s x and y. More precisely, for each valid i, point i has coordinates (x[i], y[i]). Multiple points may share the same coordinates.

Each point has one of k distinct colors. The colors are numbered 0 through k-1. You are given the int k. You are also given the int[] c, where c[i] is the color of point i. It is guaranteed that each of the k colors appears in c at least once.

We want to find a rectangle with the following properties:
  • The sides of the rectangle must be parallel to the coordinate axes.
  • The rectangle must contain (inside or on its boundary) at least one point of each of the k colors.
  • The area of the rectangle must be as small as possible.
Note that the rectangle is allowed to be degenerate: one or both of its sides may have length equal to zero.
Compute and return the smallest possible area of such a rectangle.

Constraints

  • n will be between 1 and 1,500, inclusive.
  • k will be between 1 and n, inclusive.
  • x, y and c will contain exactly n elements.
  • Each element in x and y will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • Each element in c will be between 0 and k-1, inclusive.
  • c will contain all k colors.
Examples
0)
2
{0,1,2,3}
{0,2,1,3}
{0,1,1,0}
Returns: 2

There are four points: the points at (0,0) and (3,3) have color 0 and the points at (1,2) and (2,1) have color 1. There are multiple optimal solutions. One of them is to choose the rectangle with two opposite corners at (1,2) and (3,3).

1)
3
{3,2,1}
{1,1,1}
{0,1,2}
Returns: 0

This is an example of a test case where the optimal rectangle is degenerate. For example, one optimal solution is to choose the rectangle with opposite corners at (-4,1) and (7,1).

2)
4
{-1000000,-1000000,1000000,1000000}
{1000000,1000000,-1000000,-1000000}
{0,1,2,3}
Returns: 4000000000000

Several points can share the same coordinates.

3)
3
{0,9,8,2,0,9,4,2}
{7,0,9,3,9,3,2,2}
{0,1,0,2,1,2,2,0}
Returns: 9
4)
5
{37,80,52,30,33,89,62,84,80,70,15,13,34,28,14,70,99,77,91,74}
{29,88,45,67,50,78,71,17,32,22,53,46,92,37,77,42,78,70,15,35}
{2,1,0,1,4,3,3,1,4,1,2,0,4,2,4,0,1,3,1,2}
Returns: 480

Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ColorfulEnclosure with a public method long long minArea(int k, vector<int> x, vector<int> y, vector<int> c) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous