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

Обсуждение задачи 1167. Bicolored Horses

I wonder why somebody passed it only used less than 0.1 sec !
Послано XueMao 9 апр 2003 17:19
I used DP , 0.8 sec , but some people only used 0.04 sec and uesd
less than 100K memory ! why ? How can they do it ? can anybody tell
me ?
It can be done in O(n^2) (-)
Послано Miguel Angel 11 апр 2003 00:25
> I used DP , 0.8 sec , but some people only used 0.04 sec and uesd
> less than 100K memory ! why ? How can they do it ? can anybody tell
> me ?
Re: It can be done in O(n^2) (-)
Послано marius dumitran 27 апр 2004 20:01
how?
i managed a 0.09 O(n^3) but how do u do n^2??
i might have an N^2 ideea but it n^2 memory......
Re: It can be done in O(n^2) (-)
Послано Teragram 21 май 2004 14:11
X[i]: how many black horses are in the first i horses
Y[i]: how many white horses are in the first i horses

We use Dp.
F[i,j] = min { F[i-1,k] + (X[j]-X[k])*(Y[j]-Y[k]) } | K<J

The answer is F[K,N].

Suppose F[i,j] get the minimal value when k=k0.
Let W[i,j]=k0.

You can prove : w[i,j-1]<=w[i,j]<=w[i+1,j]

So you can solve this problem in o(n^2).
Re: It can be done in O(n^2) (-)
Послано El_Groguet 11 май 2013 23:09
Sorry, could you explain please what's k0?