TOWCNT - Editorial

editorial
, , , , , ,
38

@nqs_01 @rajarshi_basu I maintained slope in double and It worked fine!!!

39

You’ve initialised denominators to 0,I think they should be initialised to 1.

41

I have taken into consideration everything mentioned in editorial still getting Wrong Answer. Can anyone help me out ?
My Code

42

Did your code work after these suggestions ? I am doing almost same thing as you but still getting WA.

43

@meet_rv
Try this test case, you are doing same mistake as me, ignoring the bars on same x.
1
3 2
0 1 1
1 1 2

Output : 1 1

2 Likes
44

@abhaypatil2000
See Here

Summary

1
3 2
0 1 1
1 1 2
Ignoring bars at same x.

1 Like
45

can slope be negative in this quesion

46

Tried that also. Still it is giving Wrong Answer. Updated code NewCode. Still thanks for suggestion :slight_smile:

Edit: Got the issue. I wasn’t re-sorting them back according to id (realized this after seeing your code). Thank you!

47

Hey! Can anyone help me in this .I’m getting Runtime (SIGFPE) . Since x can always be different so there’s no chance I can have denominator 0 and I’ve used long long and long double which should not have overflow as well as precision issues .
mySolution

49

https://www.codechef.com/viewsolution/32165861
I have implemented o(n2) solution.
Don’t understand why i am getting TLE.

Please help!

50

https://www.codechef.com/viewsolution/32208750
can anybody see this code and tell what is wrong in it?

51

https://www.codechef.com/viewsolution/32302465
Can anyone look into the solution and tell what is the mistake in this solution? please

52

What if the slope is negative? For example, num1 = 1, denom1 = -2 and num2 = 1, denom2 = 2. Clearly, num1/denom1 < num2/denom2 (-1/2<1/2) but num1*denom2 < num2*denom1 (2<-2) will return false. Am I missing something here? Because if not, then editorialist’s solution might fail on a testcase with negative slopes.

53

always keep numerator negative.
if the slope is negative then you can switch signs between numerator and denominator

Check the simplify method in this code: Code

54

if you sort all towers with respect to x coordinate then you will never get denominator in -ve (for denominator subtract higher x coordinate with smaller x coordinate).

1 Like
55

I guess you are updating max and min slope only if the end-point[j] is in the visible range(line no. 43-55). But, the update of slopes shouldn’t depend on visibility of the end-point. In case it is not clear, have a look at My Solution. If it’s still not clear, contact me. I’ll share an example image with you.

1 Like
56

I made a small change in your code and it works now. Changes in Line number 52.
Working Code

57

Got it! Thanks :slight_smile:

59

Please tell me where my code is going wrong.
I would really appreciate your help

60

min<slp<max.
shouldn,t it have been max<slp<min
Please Help me out.