You are not logged in. Please login at www.codechef.com to post your questions!

×

Why am I getting WA in LIGHTSE?

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?

My code

Problem

asked 17 Sep '15, 15:43

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%


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)

link

answered 17 Sep '15, 16:28

cold5r's gravatar image

4★cold5r
111
accept rate: 0%

Yup as said by cold5r corner case checking is not strong. Try this:

1
4
0 0
1 0
1 1
0 -1

alt text

link

answered 17 Sep '15, 16:59

vsp4's gravatar image

6★vsp4
1.2k138
accept rate: 28%

@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 : 1. X minimum==X maximum, then we will need only one.(it is easy to visualize) 2. 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...

link

answered 18 Sep '15, 13:56

mayank_r_b's gravatar image

4★mayank_r_b
723
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,070
×1

question asked: 17 Sep '15, 15:43

question was seen: 908 times

last updated: 18 Sep '15, 13:56