Has anyone solved this by comparing subsequent slopes(gradient) ?
bro isn’t the time complexity of your code N2,
Yeah, even I feel the same. The time complexity is O(N^2). How did it pass all test cases in no time? 
1 Like
Alternate approach, without hull-
-
Start at rightmost point, lets for sake of simplicity have 10 points, p1-p10
-
Calculate recline of p10 to p9-p1 , here recline is (pa-pb)/dist between them
e.g between p10=3 and p5=8 = (8-3)/5= +1, also sign does matter so pb always is point from which we are computing recline -
Now fun stuff, max of recline for p10 to (p9-p1) gives the max distance that is visible from that given spot, also in case of tie save the max distance one, i.e if recline of p10-p5 is 1 and p10-p3 is 1 then we save distance as 7.
-
Jump to Pb-dist and repeat, also if Pb is at index less than dist no need to jump forward
-
Java function - taking input array and n as argument-
private int maxView(int a[],int n)
{int res=1; int d[]=new int[n]; for (int i = a.length-res;i>=res;) { double maxRec=Integer.MIN_VALUE; int dist=0; for (int j = 0; j < a.length-(a.length-i); j++) { double rec=a[i-j-1]-a[i]; rec/=(j+1); if(rec>=maxRec) {dist=j+1; maxRec=rec;} } if(dist>res) res=dist; i-=dist; } return res;}
-
Put function in fancy fast reader, without using fancy I/o it passes all test cases in 0.36 sec in java and with it in just 0.20 sec
Solution link- CodeChef: Practical coding for everyone
2 Likes
I have written similar code with N2 time complexity but it passed only subtask 1 and 2 as expected.
this is the submission link- CodeChef: Practical coding for everyone
I just copied this part and analyzed it.
while(i<n-1)
{
double slope=LLONG_MIN,t;
int k=i+1; // Breakpoint 1
rep(j,i+1,n)
{
t=((double)a[j]-a[i])/(j-i);
if(t>=slope)
{
slope=t;
k=j; // Breakpoint 2
}
}
ans=max(ans,k-i);
i=k; // Breakpoint 3
}
The time complexity is not O(N^2). It is O(N). Just look at the breakpoints I marked. We miscalculated the time complexity as O(N^2)
one of friend solved it , in cpp
Can you please share his code?
please tell why my code is giving WA CodeChef: Practical coding for everyone
I simply iterated from left to right and checked if the next slope is greater than present one(i.e moving anti-clockwise). Else mark the previous one as the pole. Then in the end found the maximum.
@harry_shitt , bro i tried to debug your code , but i don’t know how to find convex hull ( i.e convex hull implementation ) so , i wasn’t able to do it. But , one thing in your code at line 37 , distSq is returning int , but the difference of x can be 10^5 so square can go upto 10^{10} which was too big for int. did you handle this case ?? and also did you handle all the other integer overflow cases , like in orientation ??
Ohhhh …I forgot that , for convex hull , in main function try printing finalreq vector …anyways thank you for responding 
@harry_shitt , Found this test case where your code fails
1
7
1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Hi can anybody plz tell me or give a testcase where my code is failing I did it without using convex hull with the help of slopes
Here is my code CodeChef: Practical coding for everyone
I am not able to understand the convex hull part explained by the editorialist in the vedio. can any one exlpain that part in a bit detail , i am trying to understand the code explanation since yesterday but couldn’t able to grasp the topic , please help !!
Thank you so much for that! I thought of the exact same approach, but I wasn’t able to implement it correctly in my case. 
Those commenting here that they used stacks , infact it is convex hull azpproach using stacks.
i doubt all those solutions which used stacks are copied thats why they dont know the real logic and motivation behind the problem
As majority of solutions to this problem are copied