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

Обсуждение задачи 1649. Абстракционизм в массы

BFS or DFS
Послано svr 17 ноя 2008 20:56
BFS gave TLE 7.
DFS must be much more successful.
Reasons:
1) Easy to construct the son.
2) Easy and without memory reconstruct the father.
DFS-TLE10 Therefore exists some strong mathematics in the problem to speed up algos.

Edited by author 18.11.2008 09:24
Re: BFS or DFS
Послано Vedernikoff Sergey (HSE: EconomicsForever!) 18 ноя 2008 16:04
There exists very strong pruning idea, which makes brute-force extremely fast =)
Re: BFS or DFS
Послано Deepesson 11 мар 2021 17:38
Yes, DFS is the way for this problem. My AC 0.015 solution can solve a 20x20 in about 700 recursions.
Here's a hint for the problem:
Pay close attention to the following sentence: "If the number of bacteria in a certain cell becomes 5, then 4 of them die because of overcrowding.".
What would happen if this rule didn't exist?