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 .
mySolution

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

Please help!

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

https://www.codechef.com/viewsolution/32302465
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
https://ide.geeksforgeeks.org/YIs56rw28S

min<slp<max.
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: