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

Обсуждение задачи 1147. Цветная бумага

My algorithm in worst case is O(n^3).But it seem to be impossible to appear. So the average time is O(n^2),and I got AC in 0.046sec.
Послано Yu YuanMing 2 июл 2004 22:00
If someone has a better solution,
would you please write it down?
Thanks.
Re: My algorithm in worst case is O(n^3).But it seem to be impossible to appear. So the average time is O(n^2),and I got AC in 0.046sec.
Послано Chan-Min Kim 11 июн 2005 17:00
I don`t no how u did.. but maybe you did it in exact
 O(n^2).

I got AC too.
and it seemed to be O(n^3), but it was O(n^2) always.

I think it is such a good prob...
I have known a better way :)
Послано Yu Yuanming 11 июн 2005 19:14
Use 2D interval tree, just O(nlog2n)
Re: I have known a better way :)
Послано kcm1700 13 июн 2005 15:58
That`s good...
O(n lg^2 n) algorithm using binary tree.... hmm..
it was tough work for me to make program for it.;(
My opinion
Послано Yu Yuanming 16 июн 2005 07:41
I think O(nlgn) is enough, not O(nlg^2n)...

And the most important thing is that O(nlogn) algo can save a lot of memory...also, it is faster...:)
My opinion
Послано Yu Yuanming 16 июн 2005 07:42
2D interval tree uses O(nlg^2)...

Now I have a better way, it uses 1D interval tree
I think O(nlgn) is enough, not O(nlg^2n)...

And the most important thing is that O(nlogn) algo can save a lot of memory...also, it is faster...:)

Edited by author 16.06.2005 07:45