PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Animesh Fatehpuria
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM
PREREQUISITES:
Geometry, dp
PROBLEM:
For a given convex polygon with N vertices and M additional points on a plane, where each of them is colored either red or blue, the goal is to find the number of subsets of N vertices of the polygon, such that each of these subsets describes a convex polygon with equal number of red and blue points inside it (or on its boundary).
EXPLANATION:
One crucial fact used basically in all approaches described below is that any subset of vertices of a convex polygon describes also a convex polygon. Here we define a polygon to be described by some points as a polygon described by them in an anticlockwise order.
The problem has also an additional difficulty: notice that two or more colored points in the input can share the same coordinates.
A very useful subroutine in this problem is the ability of checking if a given point is inside a convex polygon. This case is easier than checking this for any polygon, and a very efficient method of doing it is described here: How to test if a point is inside of a convex polygon in 2D integer coordinates?.
Subtask 1
In the first subtask both N, M \leq 12, so it is possible to generate all possible subsets of these N points, and then for each of these subsets iterate over all M colored points and count the number of blue and red points inside the polygon formed by the selected subset. If these two amounts are equal, just add 1 to the result.
Subtask 2
In the second subtask, N and M can be both up to 50, but we know that all colored points have different coordinates and that all them lie on the vertices of the input polygon. In this case the problem is not hard at all. Let’s say that we want to count the number of valid choices of exactly k vertices of the polygon corresponding to chosen k blue points and exactly k other vertices of the polygon corresponding to the chosen k red points. The first thing to notice is that every such choice describes a valid convex polygon with exactly k blue and k red points in it (well, exactly on it’s boundary), and no two different ways of choosing such points produces the same polygon, and also there are 2^W ways to choose vertices not sharing coordinates with any colored points, where W is the number of such vertices. Thus the total number of valid polygons containing exactly k blue and exactly k red points is given by \binom{B}{k} \cdot \binom{R}{k} \cdot 2^W, where B is the total number of blue points and R is the total number of red points. In order to get the final answer, it is sufficient to return the sum of such sub-results computed for all possible k from 2 to \min(B, R).
Subtask 3
In the third subtask we have a similar situation as in the second one. N and M also can be up to 50 and all colored points lie on the vertices of the input polygon. However, colored points can now share the same coordinates, so the method given as the solution to the second subtask cannot be applied to this one. The main difference is that if we take a vertex of the polygon into the subset, then the resulting polygon will contain all the colored points lying on this vertex, and they can have also different colors as well. However, if we first preprocess colored points and create a mapping cnt[(x, y)][b] denoting the number of blue points with coordinates (x, y) and similarly cnt[(x, y)][r] denoting the number of red points with coordinates (x, y), we can use dynamic programming to solve this subtask.
More specifically, let dp[k][i][j][taken] be the number of subsets of k first vertices of the input polygon where there are exactly i blue and j red points on the chosen vertices and where taken is the integer from 0 to 3 and denotes that there are that many taken vertices in the subset, where taken = 3 is an exception and denotes at least 3 taken vertices. This last parameter is required, because we want to include in the result only non-degenerated polygons, so the ones with at least 3 vertices. Then the final answer to the problem is the sum over dp[N][i][i][3] for i = 0 to \min(B, R), where B is the number of blue points and R is the number of red points. Entries of the dp table can be computed in a very straightforward way. Let’s say that we have computed all the entries for x < k and we want to compute dp[k][i][j][y] now. Then depending on how many blue and red points the k-th vertex of the polygon shares coordinates, it always yields two possiblities depending on the fact if we either take this k-th vertex to the subset or not. For example, let’s assume that it shares coordinates with b blue points and r red points. Then taking this vertex into the subset adds dp[x-1][i-b][j-r][z] ways to dp[x][i][j][y], while not choosing it adds dp[x-1][i][j][y] to dp[x][i][j][y] for some valid y, z. The total time complexity of this approach is therefore O(N \cdot M^2) since this is the number of entries in the dp table and each entry is filled in a constant time.
Subtask 4
Description for this subtask will be added later.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.