ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1119. Метро

for those who use graph & recursion approach
Послано Anton 7 мар 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
Послано arrammis 1 ноя 2014 19:12
how you use longest increasing subsequence in this problem ?
Re: for those who use graph & recursion approach
Послано mberdyshev 10 янв 2016 03:45
Anton писал(a) 7 марта 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
Послано sukhad 18 фев 2017 03:51
Shouldn't we use bfs as we require the shortest path?