Автор |
Сообщение |
30.09.2006 15:56:33
Тема: CTGAME
|
Руслан Коржик
Темы: 14
Сообщений: 86
Мой профиль
|
Мне удалось придумать решение за N2logN. Кто-нибудь придумал решение лучше? Мое прошло за 2.9 сек.(ограничение 3).
Вкратце условие: есть поле со свободными и занятыми клетками, надо вписать туда прямоугольник максимальной площади (мне эта задача напомнила задачу про амбар фермера Джона)
Условие: Rus
Eng
|
05.10.2006 16:32:03
Тема: Re:CTGAME
|
Руслан Коржик
Темы: 14
Сообщений: 86
Мой профиль
|
Что-то никто не отвечает
Интересно, как решали Гена и Вова?
http://www.spoj.pl/status/CTGAME,tourist/
http://www.spoj.pl/status/CTGAME,vovamin/
8)
|
05.10.2006 18:47:36
Тема: Re:CTGAME
|
Геннадий Короткевич
Темы: 6
Сообщений: 37
Мой профиль
|
N2logN. 0.5 сек 8)
Возможно, у тебя не очень хорошая реализация или не очень эффективная идея решения...
Можешь рассказать идею своего решения?
______________________
Nothing is impossible; impossible itself says: "I m possible"...
|
06.10.2006 13:05:13
Тема: Re:CTGAME
|
Руслан Коржик
Темы: 14
Сообщений: 86
Мой профиль
|
Странно. У меня только чтение из файла работало за 0.5. Наверное особенности реализации
А нельзя посмотреть исходник?
|
06.10.2006 17:46:58
Тема: Re:CTGAME
|
Владимир Миняйлов
Темы: 9
Сообщений: 30
Мой профиль
|
Можно за O(N^2).
После рассмотрения i строк высота или увеличиваеться на 1 или меняеться на 0 => можно сортить за O(N). Далее просто просчет(нарпимер, двусвязным списком).
P.S. Я слышал, что такую задачу можно решать на основе стека. Но не знаю как...
|
|