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

Обсуждение задачи 1418. Армейская история

How to get AC in 0.1 s or less ?
Послано N.M.Hieu ( DHSP ) 12 июн 2006 17:27
I've got AC but my run time is 0.765s . I saw that some people got AC with little run time so I think there's another solution better than using Graham k times ( k = maximal possible number of fences ).
If it's true , please tell me your solution.
Thank you very much.
My e-mail : hard7771988@yahoo.co.uk
Re: How to get AC in 0.1 s or less ?
Послано Igor Dex 22 июн 2006 13:25
To solve this problem efficiently we have to use Chazelle's algorith which is O(n log n). Sometimes it's called "onion peeling algorithm". But I can't find this algorithm in the net. If someone knows , please tell us links to it.
Re: How to get AC in 0.1 s or less ?
Послано TheBeet 21 авг 2006 11:14
 TheBeet 1418 C++ Accepted
 0.093 206 KB

I use Graham k times. My solution is O(n^2)