Сегодня была проведена очередная командная тренировка.
Проблемсет был взят с ВКОШП 2005.
В итоге команда заняла 37/126 место с 5ю задачами из 10.
Интересно, что я так и не смог придумать внятного алгоритма на задачу C(что то сильно смахивающее на топологическую сортировку с ДП), которую решило 61 команда, но придумал решение для задачи B, которую решило всего 12 команд. Будем разбираться.
Тактических ошибок замечено не было. Все по-максимуму были заняты тем, чем надо.
Так же сегодня продолжил изучать суффиксные автоматы.
Тема очень благодатная.
Есть сильные подозрения, что данный алгоритм позволит сдать сразу 3 задачи с Тимуса.
Но в задаче 1590. Шифр Бэкона напоролся на проблему того, что построить автомат не проблема.
Проблема посчитать количество различных путей в ацикличном ориентированном графе.
Очевидное рекурсивное решение дохнет уже на строке в 4000 символов или TL'ится.
Переписанное итеративное решение с 3мя стэками не может справиться уже с 3000.
В общем, в воскресенье попробую продолжить решение данных задач и окончательно разобраться в этих автоматах.
Проблемсет был взят с ВКОШП 2005.
В итоге команда заняла 37/126 место с 5ю задачами из 10.
Интересно, что я так и не смог придумать внятного алгоритма на задачу C(что то сильно смахивающее на топологическую сортировку с ДП), которую решило 61 команда, но придумал решение для задачи B, которую решило всего 12 команд. Будем разбираться.
Тактических ошибок замечено не было. Все по-максимуму были заняты тем, чем надо.
Так же сегодня продолжил изучать суффиксные автоматы.
Тема очень благодатная.
Есть сильные подозрения, что данный алгоритм позволит сдать сразу 3 задачи с Тимуса.
Но в задаче 1590. Шифр Бэкона напоролся на проблему того, что построить автомат не проблема.
Проблема посчитать количество различных путей в ацикличном ориентированном графе.
Очевидное рекурсивное решение дохнет уже на строке в 4000 символов или TL'ится.
Переписанное итеративное решение с 3мя стэками не может справиться уже с 3000.
В общем, в воскресенье попробую продолжить решение данных задач и окончательно разобраться в этих автоматах.
Комментариев нет:
Отправить комментарий