|
|
back to boardShow all messages Hide all messagesMy 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. how you use longest increasing subsequence in this problem ? 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 :) Shouldn't we use bfs as we require the shortest path? |
|
|