ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1119. Metro

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
Posted by arrammis 1 Nov 2014 19:12
how you use longest increasing subsequence in this problem ?
Re: for those who use graph & recursion approach
Posted by mberdyshev 10 Jan 2016 03:45
Anton wrote 7 March 2012 06:30
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 :)
Re: for those who use graph & recursion approach
Posted by sukhad 18 Feb 2017 03:51
Shouldn't we use bfs as we require the shortest path?