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

Обсуждение задачи 1115. Корабли

2 different ways of DFS
Послано - GO - 7 мар 2005 13:13
this algo got TL
choose the row for each ships
ship 1  try [1,...,m]
ship 2  try [1,...,m]
...
ship n  try [1,...,m]

you could get TLE even you've bounded it (sorting)


another algo ,which is AC
fill the row until full
row 1  try 2^n
row 2  try 2^(n-1)
...
row m  try 2^(n-(m-1))

2^n looks bad but it works!
Re: 2 different ways of DFS
Послано Krayev Alexey(PSU#2) 17 июл 2005 01:56
the first way is also possible, you just need some inventiveness to think out good euristic. i got ac in 0.734
Re: 2 different ways of DFS
Послано blue shading 11 фев 2006 19:13
Why does the 2nd algo much better? Could U give a little explanations?
Although I got Aced in 200s, but i am not quite clear about that. I think it should be more important to find more questions than just solve it and go.