[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Author Message
Ruslan Korzhik

Topics: 14
Messages: 86

My Profile
Мне удалось придумать решение за N2logN. Кто-нибудь придумал решение лучше? Мое прошло за 2.9 сек.(ограничение 3).

Вкратце условие: есть поле со свободными и занятыми клетками, надо вписать туда прямоугольник максимальной площади (мне эта задача напомнила задачу про амбар фермера Джона)

Условие: Rus
Eng
Ruslan Korzhik

Topics: 14
Messages: 86

My Profile
Что-то никто не отвечает

Интересно, как решали Гена и Вова?
http://www.spoj.pl/status/CTGAME,tourist/
http://www.spoj.pl/status/CTGAME,vovamin/
8)

Gennadiy Korotkevich

Topics: 6
Messages: 37

My Profile
N2logN. 0.5 сек 8)
Возможно, у тебя не очень хорошая реализация или не очень эффективная идея решения...
Можешь рассказать идею своего решения?
______________________
Nothing is impossible; impossible itself says: "I m possible"...
Ruslan Korzhik

Topics: 14
Messages: 86

My Profile
Странно. У меня только чтение из файла работало за 0.5. Наверное особенности реализации
А нельзя посмотреть исходник?
Vladimir Minyaylov

Topics: 9
Messages: 30

My Profile
Можно за O(N^2).
После рассмотрения i строк высота или увеличиваеться на 1 или меняеться на 0 => можно сортить за O(N). Далее просто просчет(нарпимер, двусвязным списком).
P.S. Я слышал, что такую задачу можно решать на основе стека. Но не знаю как...
 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,047