PROBLEM LINK:
Author: Evgenij Artemov
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Ad-hoc
PROBLEM:
Given are the coordinates of N islands in cartesian plane. We are supposed to place lighthouses on some or all of these islands such that each one of them gets illuminated. A lighthouse can throw light only in one of the following four directions: North West, North East, South East and South West.
EXPLANATION:
Subtask 1
In this subtask, there can be a maximum of 8 islands. This clearly hints towards an exponential algorithm. We can try all possible placements of lighthouses and check which one covers all the islands while using the minimum number of lighthouses.
How do we try all possibilities? We can use recursion. Let’s say there are N islands, numbered from 0 to N-1. We use numbers from i = 0 to 2^N-1 to denote which islands are lit and which are not. If in the binary representation of a particular i, the j^{th} bit is 1 that means j^{th} island is not lit and if 0 then it is lit.
During the recursion, we place a lighthouse on a particular island and then check how many unlit islands it lights. The placement of lighthouse can be done in 4 ways. To keep a track of the way in which the lighthouse was placed, we use base 5 representation of number. 1 indicates NE, 2 indicates NW, 3 indicates SW and 4 indicates SE.
There are 2^N total possible placements. For each placement containing k lighthouses, there are 4^k configurations. Upon, placing a lighthouse, we also have to check how many islands it lights. Thus, total complexity comes out to be \mathcal{O}(2^N * 4^N * N) = \mathcal{O}(N*2^{3N}) per test case. Though that looks like it will exceed the time limit, however, the description of subtask 2 will tell us that we don’t require more than 2 lighthouses to light all islands. Thus, the depth of this recursion won’t be very large.
Subtask 2
Let’s consider two particular sets of points:
- The first set consists of all those islands which have the least x-coordinate value.
- The second set consists of all those islands which have the highest x-coordinate value.
Now, we can make the following observations:
- If in the first set, there is an island such that it has the minimum y-coordinate amongst all given N islands, then we can place a lighthouse on it facing in the NE direction. This will illuminate all the islands.
- If in the first set, there is an island such that it has the maximum y-coordinate amongst all given N islands, then we can place a lighthouse on it facing in the SE direction. This will illuminate all the islands.
- If in the second set, there is an island such that it has the minimum y-coordinate amongst all given N islands, then we can place a lighthouse on it facing in the NW direction. This will illuminate all the islands.
- If in the second set, there is an island such that it has the maximum y-coordinate amongst all given N islands, then we can place a lighthouse on it facing in the SW direction. This will illuminate all the islands.
What if none of the aforementioned four conditions are true? Then, we can clearly say that all the islands can’t be illuminated by one lighthouse; we need more.
In that case, let’s pick up a point from the first set and another from the second set. Let the coordinates of these points be (x_1,\,y_1) and (x_2,\,y_2) respectively. We know that x_1 is the least x-coordinate value amongst all given points and x_2 is the highest x-coordinate value amongst all given points. We now consider the following two possibilities:
-
y_1 \leq y_2
In this case, we can place a lighthouse on the island at (x_1,\,y_1) facing NE, and another one on the island at (x_2,\,y_2) facing SW. This way, we will be able to illuminate all the islands. -
y_1 > y_2
In this case, we can place a lighthouse on the island at (x_1,\,y_1) facing SE, and another one on the island at (x_2,\,y_2) facing NW. This way, we will be able to illuminate all the islands.
Thus, we can accomplish the task either by placing 1 or 2 lighthouses, as the case may be. Finding the two sets of points can be done by simple iterations over the set of all the given points. Further steps can also be carried out in \mathcal{O}(N).
COMPLEXITY:
\mathcal{O}(N) per test case.
