MONOCMNEZ - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Sorting

PROBLEM:

There are N points on the x-axis and M on the y-axis.
Each point must be colored either red or blue; with the additional constraint that each axis must contain at least one point of both colors.

Minimize the maximum area of a triangle whose vertices all have the same color.

In this version, N, M \le 2000.

EXPLANATION:

For convenience, we’ll denote the points on the x-axis as x_1, x_2, \ldots, x_N and the points on the y-axis as y_1, \ldots, y_M.
Further, we assume that these lists are sorted, i.e. x_i \le x_{i+1} and y_i \le y_{i+1}, since that clearly doesn’t change the answer.

Observe that any triangle with positive area formed from the given points must have two vertices on one axis and its third vertex on the other one.

Suppose two points come from the x-axis and one from the y-axis; say these points are x_i, x_j, y_k where i \lt j.
Then, the area of the triangle equals half its base times its height, which in this case is just

\frac{1}{2}\times (x_j - x_i) \times y_k

since y_k is the height and (x_j - x_i) is the length of the base.

Now, suppose we’ve already decided on a coloring for points on the y-axis.
Then, for the x-axis, it can be seen that in an optimal coloring, the set of points having the same color must form a contiguous segment - or even more precisely, there must exist an index i such that:

  • x_1, x_2, \ldots, x_i are colored red and x_{i+1}, \ldots, x_N are colored blue; or
  • x_1, x_2, \ldots, x_i are colored blue and x_{i+1}, \ldots, x_N are colored red.
Proof

Let the leftmost red and blue points on the x-axis be at positions l_1 and l_2 respectively.
Without loss of generality, assume l_1 \lt l_2.
Let the rightmost red and blue points be at positions r_1 and r_2.

Observe that any monochromatic triangle with maximum area will only use some of these points: for example, a red triangle will either use both l_1 and r_1 as its ‘base’, or use two vertices from the y-axis and then only r_1 to maximize its height.
So, we only need to care about these four points.

There are now three cases:

  1. l_1 \le r_1 \lt l_2 \le r_2
    Here, we must have l_2 = r_1+1 since every point is colored, and so the colors form a split prefix/suffix as claimed.
  2. l_1 \lt l_2 \le r_2 \lt r_1, i.e. the blue points are ‘contained inside’ the red points.
    In this case, we must have l_1 = 1 and r_1 = N.
    Observe that if we instead had l_2 = r_2 = 1 and l_1 = 2, r_2 = N, the maximum red and blue areas both cannot increase (in fact, the maximum blue area will strictly decrease).
    The [1, 1] and [2, N] split is thus at least as optimal as the initial one; and corresponds to a prefix/suffix split on colors as claimed.
  3. l_1 \lt l_2 \lt r_1 \lt r_2, i.e. there’s some intersection between points.
    Here, we must have l_1 = 1 and r_2 = N.
    In this case, observe that coloring the interval [1, r_1] red and [r_1+1, r_2] blue can only improve the answer; since the red area doesn’t increase and the blue one doesn’t decrease.

So, in every case, we’re able to switch to a prefix/suffix split on colors that keeps the solution optimal, hence proving our claim.

However, the exact same argument applies to the y-axis as well.

Thus, both axes will have their colors split into a prefix/suffix.
Further, because of symmetry of the colors, we can always assume that the x-axis will have a prefix of red points and a suffix of blue points; though both configurations of colors need to be considered for the y-axis.

Since the constraints of the easy version allow for \mathcal{O}(NM) solutions, this observation is already enough to solve the problem.

Let’s iterate through each pair of “split points”, meaning all pairs of indices (i, j) such that 1 \le i \lt N and 1 \le j \lt M.
Then, given that points x_1, \ldots, x_i are red and x_{i+1}, \ldots, x_N are blue, we have two options:

  1. y_1, \ldots, y_j are red and y_{j+1}, \ldots, y_M are blue.
    Here, we have the following:
    • The maximum area of a red triangle is either y_j \cdot (x_i - x_1) or x_i \cdot (y_j - y_1)
    • The maximum area of a blue triangle is either y_M \cdot (x_N - x_{i+1}) or x_N \cdot (y_M - y_{j+1})
    • The maximum monochrome area is hence the largest of these four values.
  2. y_1, \ldots, y_j are blue and y_{j+1}, \ldots, y_M are red.
    Here, we have the following:
    • The maximum area of a red triangle is either y_M \cdot (x_i - x_1) or x_i \cdot (y_M - y_{j+1})
    • The maximum area of a blue triangle is either y_j \cdot (x_N - x_{i+1}) or x_N \cdot (y_j - y_1)
    • The maximum monochrome area is hence the largest of these four values.

In either case, once i and j are fixed, only \mathcal{O}(1) computation needs to be done.

We can thus try all possibilities of (i, j), and take the minimum answer across them all.
The complexity is \mathcal{O}(NM) which is good enough here.

TIME COMPLEXITY:

\mathcal{O}(NM) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    xs = list(map(int, input().split()))
    ys = list(map(int, input().split()))

    xs.sort()
    ys.sort()

    ans = 10**18
    for i in range(n-1):
        for j in range(m-1):
            # red-blue for x always

            # red-blue for y
            redar = max(xs[i] * (ys[j] - ys[0]), ys[j] * (xs[i] - xs[0]))
            bluar = max(xs[-1] * (ys[-1] - ys[j+1]), ys[-1] * (xs[-1] - xs[i+1]))
            ans = min(ans, max(redar, bluar))

            # blue-red for y
            redar = max(xs[i] * (ys[-1] - ys[j+1]), ys[-1] * (xs[i] - xs[0]))
            bluar = max(xs[-1] * (ys[j] - ys[0]), ys[j] * (xs[-1] - xs[i+1]))
            ans = min(ans, max(redar, bluar))
    
    print(ans)