for those who use graph & recursion approach

Posted by

Anton 7 Mar 2012 06:30

My graph consists of vertexes, which are points, that allow diagonal crossing. Edge (a, b) exists if and only if (a) strictly south-west from (b). Since graph is built, simple dfs easily helps solve the problem ( length of the longest path in the graph - it's diagonal part of result path ).

To avoid TLE#10 in this approach, memorization should be used.

I know, it's not the best approach, but since constraints are relatively low, it does work.

My AC - 0.015 164 КБ.

I think, Longest increasing subsequence - is better in general case.

Re: for those who use graph & recursion approach

To avoid TLE#10 in this approach, memorization should be used.

Thanks, it helped me) I added functools.lru_cache() decorator for my Python program and got AC :)