LIGHTHSE - Editorial

PROBLEM LINK:

Practice
Contest

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.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

4 Likes

I followed a similar approach . Here is my submission -> https://www.codechef.com/viewsolution/8097661
Could you tell me a test case where this fails. I only got 85 points(WA in subtask 1). Thanks!

1 Like

Hi ,can anyone tell me why my code is not running for subtask-1 although it is running for subtask-2.

https://www.codechef.com/viewsolution/8156136

I suppose there will be a lot of comments here asking for why my code didn’t passed the 1 subtask although it cleared the 2 sub task, while following the similar approach…

As a lot of solution only got their 2 sub-task cleared, while the problem can have more than 1 answers.

https://www.codechef.com/viewsolution/8166788
@admin I have solved it the same way as explained in editorial… Can u plz point out the mistake or give me some test cases where I fail…I m currently getting 85

Hey, can anyone please point out a test case that prove my solution wrong for sub-task 1.I just want to know my mistake.
https://www.codechef.com/viewsolution/8132345

hey cant we take the 2 top most points and then compare their x coordinates. And then give the respective directions SE and SW.

if(x[top2]>x[top])
    {
    	printf("%d SE

“,top+1);
printf(”%d SW
“,top2+1);
}
else
{
printf(”%d SW
“,top+1);
printf(”%d SE
",top2+1);
}

@vsp4 3NW is correct for this test case .

2 Likes

Get More Details-
pest control connaught place @ http://pest-control-delhi.pestcontrolindelhi.com/pest-control-in-connaught-place.html
pest control services in vasantkunj @ http://pest-control-delhi.pestcontrolindelhi.com/pest-control-in-vasant-kunj.html
pest control services in dwarka @ http://pest-control-delhi.pestcontrolindelhi.com/pest-control-in-dwarka.html
pest control laxmi nagar @ http://pest-control-delhi.pestcontrolindelhi.com/pest-control-in-laxmi-nagar.html
pest control services in preet vihar
@ http://pest-control-delhi.pestcontrolindelhi.com/pest-control-in-preet-vihar.html
pest control vikaspuri @ http://pest-control-delhi.pestcontrolindelhi.com/pest-control-in-vikas-puri.html

For people asking Why Subtask 1 WA please try the below 3 test cases. These are the cases where i got WA

1
7
0 0
-2 0
1 1
1 -1
2 0
-1 -1
-1 1

1
7
0 0
0 2
1 1
1 -1
0 -2
-1 -1
-1 1

1 7 0 5 0 -5 5 2 -5 -2 -6 3 6 -3 0 0

Please tell me what is wrong. http://ideone.com/mjOBNe

@code01aviraj my code is showing right answer for those cases , still getting WA on subtask 1 .
link to my code https://www.codechef.com/viewsolution/8163532

@code01aviraj - Testcase is working according to the logic.

@ayushgarg1804 and @mudit1993 I think your code gives wa for the below case. Point 5 is not illuminated.
1
7
0 5
0 -5
5 2
-5 -2

  • 6 3
    6 -3
    0 0

@sarvagya3943
@drift_king
check this test case… i think many people who got 85 and not 15 fail for this type of case… For 85 , the points are far away may be so it passed… for 15 , the test cases may be a bit intelligent :stuck_out_tongue:
1
5
3 0
-3 -1
-3 -2
3 -4
0 1

i think it failed there, and many test cases of same type !

For all those who got WA in subtask1 1/ Try checking your answer when all the points lie on the same line I.e. either the x coordinate or y coordinate for all points remains constant.

Really poor test cases were set up for the question. Corner cases were included in Subtask 1 but were not included in Subtask 2. Many users got away with 85 points although there was a glitch in their approach or logic.

This should not have happened.

There is a small correction in the Editorial.

In sub task 2, the word ‘first’ set has to be changed to ‘second’ set in the 4th point.

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 SW direction. This will illuminate all the islands.

to

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.

2 Likes

I am convinced that there are a few missing solutions in this problem. I have tested my solution with all the tricky edge cases mentioned in the comments so far. And all of them have given the correct output so far. I am yet to come across a test case for which my solution fails. I still have no idea why my solution got 85pts only. I would be grateful if someone can come up with a test case for which my solution fails. Here’s the link : https://www.codechef.com/viewsolution/8033551

@Author: why not provide the test cases ? I think it would make the discussion easier. A lot of people seem to think there is no bug in their solution…