TOWCNT - Editorial

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 .
I have implemented o(n2) solution.
Don’t understand why i am getting TLE.

Please help!
can anybody see this code and tell what is wrong in it?
Can anyone look into the solution and tell what is the mistake in this solution? please

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.

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

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

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.

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

Got it! Thanks :slight_smile:

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

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

Can we do it in better time complexity than O(n^2) something like nlogn may be?
We have to find longest subsequence with non-decreasing slopes.
Thanks :slight_smile: