FLIPOINTS - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

MEDIUM

PREREQUISITES:

Linear Separability, DP

PROBLEM:

Given N points in the 2D plane, each having color red or green. In one move, you may select a subset of these points where the selected points (along with the origin) can be linearly separated from the other points, and flip their colors.

Determine the minimum number of moves required to make all points green.

EXPLANATION:

Hint 1

The constraint N\le 17 tells a lot.

Hint 2

If you knew all the subsets of points that could be flipped in one move, how would you determine the minimum number of moves required to solve the problem (aka flip all the red points)?

Solution

From this post, it is clear that the maximum number of subsets (that can be flipped in one move) is equal to N^2. Call the set containing all these subsets S.

Then, a straightforward DP on bitmasks approach may be employed.
Let dp[mask] represent the minimum number of moves to flip only points corresponding to the set bits of mask.

Initially, dp[mask]=\infty for all mask, and dp[0] = 0 (base case).

for s in S:
	for mask in range(0, 1<<N):
		dp[s^mask] = min(dp[s^mask], dp[mask]+1)

Thus, given the set of flippable subsets, we can compute the minimum number of moves required in O(|S|\cdot2^N) \approx O(N^2\cdot 2^N).

Solution

Now, all we are left to do is find the set S of all subset of points that can be flipped in one move. Here’s a simple approach to achieve the same -

Iterate over all subsets of the N points. For each subset, calculate if there exists a line that separates these points from the other points (not in the subset) - this is a standard problem called Linearly Seperable Points. If it does exist (and also encloses the origin point), add this subset to S.

This approach has time complexity O(2^N\cdot (N\log N + N^2)) (the second part of the time complexity is to generate the convex hulls and check if they intersect, respectively), which is efficient enough to pass for the given constraints!

Bonus: The approach employed in my code does it in O(N^3). Use the fact that there are atmost N^2 sets in S, along with the collision algorithm.

TIME COMPLEXITY:

Calculating all subsets of flippable points takes O(2^N\cdot (N\log N + N^2)) \approx O(2^N\cdot N^2). Given that there can be atmost N^2 flippable subsets, computing the minimum number of moves to flip a subset of points using DP takes O(N^2\cdot2^N).
The total time complexity is therefore

O(2^N\cdot N^2+N^2\cdot2^N) \approx O(2^N\cdot N^2)

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters