CONTAIN, CONVAIR video solution (JUNE20)

editorial
1

CONTAINS :- solution
CONVAIR :- solution

1 Like
3

convair solution added

4

I implemented a pretty similar approach to problem CONTAIN, can you tell me why did it give wrong answer in small test case and TLE in bigger cases
Link to my code: CodeChef: Practical coding for everyone

5

:+1:

1 Like
6

You have used Jarvis algorithm which runs in O(n^2). And for finding all the convex layers, the upper bound of time complexity will be O(n^3). That’s why you are getting TLE. Use graham’s scan.
I am not able to figure out the reason for wrong answer but I think I will be some implementation error as your algo is correct.

7

Thanks for seeing my solution and telling me the mistake. Actually I have no knowledge of Convex hull algorithms :confused: Can you tell me where can I learn to be good at geometry?

8

Checkout the geometry section of cp-algorithms

9

Thanks very much