I couldn’t solve it during the contest. Now after reading the editorial, I implemented it. But I am getting WA for first subtask. Where have I gone wrong?
your logic to check the corner points fails when there are mulitple points with same xmin/xmax/ymin/ymax. For example (-5,6), (-5,8) and (-4,8) (assuming -5 is xmin and 8 is ymax). when u are finding xmin and ymax, it is not guaranteed that u will have (-5,8) and (-5,8) or (-5,8) and (-4,8) as xmin and ymax point.Depending on the order of points it can be (-5,6) and (-4,8) or (-5,6) and (-5,8). only for the first case ur logic finds the correct answer. In other case it fails. i.e (point[xmin].y!=point[ymax].y)
Yup as said by cold5r corner case checking is not strong. Try this:
1 4 0 0 1 0 1 1 0 -1
@dragonemperor, This was my logic/approach.
I took variables like this :
X minimum, Y min and Y max of X minimum (y min is the minimum y in X minimum same for y max).
X maximum, Y min and Y max of X maximum(same as previous, the only difference is here we have X max).
Y1 min,and Y1 max(minimum and maximum value of y ordinates ).
Now there are two possibilities :
- X minimum==X maximum, then we will need only one.(it is easy to visualize)
- X minimum != X maximum. Here Again two cases arise
2.1 Is there any light house which can lighten up all the islands. this can be checked if if Ymin of Xmin or X max is equal to the Y1 min or not, or Ymax of Xmax or Xmin is equal to Y1 max,if equal then we need only 1.
Else we need 2. Now take any two points,1 from X min and one from Xmax and check their relative positions and place the light houses according to the situations.
My solution : https://www.codechef.com/viewsolution/8138990 (it is a messy one) Happy Coding…