Форум Всеукраїнської інтернет-олімпіади NetOI

FireTiger · 2007-01-04 20:29:47

Здесь я предлагаю обсудить решение задачи Pencils

Если вы собрались написать сообщение в этой теме пожалуйста прочитайте следующие правила:
1. Постить только после окончания приёма решений. (без комментариев)
2. Постите код только если вас об этом попросили. (обилие кода делает тему нечитабельной)
3. Обсуждайте только задачу, которая указана в теме.

Надеюсь эти простые правила сделают обмен мнениями более плодотворным.

Відредаговано FireTiger (2007-01-04 20:38:26)

AlexeyS · 2007-01-05 09:17:18

У кого какая сложность алгоритма в этой задаче?
Я пытался добиться O(N^2), но ничего лучше O(N^2*logN) не придумал.
Подкиньте идею, как можно было решить быстрее.

xXx · 2007-01-05 09:23:44

O(N^2) - hashtable

AlexeyS · 2007-01-05 09:25:43

xXx написав:
O(N^2) - hashtable

Намекни чуть-чуть конкретнее.

alex_kasycky · 2007-01-05 09:33:41

AlexeyS написав:
У кого какая сложность алгоритма в этой задаче?
Я пытался добиться O(N^2), но ничего лучше O(N^2*logN) не придумал.
Подкиньте идею, как можно было решить быстрее.

У меня O(N^2*logN) сортировку можно переписать за линию - будет квадрат.

AlexeyS · 2007-01-05 09:36:29

alex_kasycky написав:
AlexeyS написав:
У кого какая сложность алгоритма в этой задаче?
Я пытался добиться O(N^2), но ничего лучше O(N^2*logN) не придумал.
Подкиньте идею, как можно было решить быстрее.
У меня O(N^2*logN) сортировку можно переписать за линию - будет квадрат.

Кас, ты же сам говорил, что сортировка за линию работает дольше, чем QuickSort

guest1 · 2007-01-05 09:36:33

Я делаю так: ищу карандаши, которые УЖЕ совмещаются параллельным переносом. Если таких нет, вывожу N. Если есть, тогда я накладываю эти карандаши друг на друга и смотрю, сколько карандашей накладываются (Z).
Просматриваю все пары, нахожу максимальное Z (число карандашей, которые накладываются при параллельном переносе).Потом вывожу разность N - Z.
Вот и все. Если кто заметил неточность - высказывайте свое мнение.

xXx · 2007-01-05 09:39:52

чтоб определить кол. одинаковых элементов в массиве не обязательно его сортировать...
просто последовательно перебирая элементы нада добавлять их в хеш табл и считать кол....
блин.... тока что обнаружил что я пролетел по этой задаче.... моя хеш табл размером 1000

alex_kasycky · 2007-01-05 09:41:01

AlexeyS написав:
alex_kasycky написав:
AlexeyS написав:
У кого какая сложность алгоритма в этой задаче?
Я пытался добиться O(N^2), но ничего лучше O(N^2*logN) не придумал.
Подкиньте идею, как можно было решить быстрее.
У меня O(N^2*logN) сортировку можно переписать за линию - будет квадрат.
Кас, ты же сам говорил, что сортировка за линию работает дольше, чем QuickSort

Во-первых не всегда, во-вторых мы сейчас о сложности алгоритма, а не о времени его работы.

AlexeyS · 2007-01-05 09:42:06

guest1 написав:
Я делаю так: ищу карандаши, которые УЖЕ совмещаются параллельным переносом. Если таких нет, вывожу N. Если есть, тогда я накладываю эти карандаши друг на друга и смотрю, сколько карандашей накладываются (Z).
Просматриваю все пары, нахожу максимальное Z (число карандашей, которые накладываются при параллельном переносе).Потом вывожу разность N - Z.

Так сложность в этом алгоритме O(N^2*logN).
Вопрос, как можно было решить за O(N^2).

alex_kasycky · 2007-01-05 09:44:12

xXx написав:
O(N^2) - hashtable

Ну у тебя ведь амортизированый квадрат. Тоесть Омега а не О
Короче это врядли быстрей чем сортировка за линию.

guest1 · 2007-01-05 09:44:31

Простите за безграмотность но что такое O(N^2)? и что такое O в частности?

xXx · 2007-01-05 09:48:44

alex_kasycky написав:
xXx написав:
O(N^2) - hashtable
Ну у тебя ведь амортизированый квадрат. Тоесть Омега а не О
Короче это врядли быстрей чем сортировка за линию.

это будет быстрее, причём на порядок...
если так рассудать, то квиксорт работает медленнее чем сорт слиянием....

Відредаговано xXx (2007-01-05 09:49:39)

AlexeyS · 2007-01-05 10:07:11

guest1 написав:
Простите за безграмотность но что такое O(N^2)? и что такое O в частности?

Так обозначается сложность алгоритма. По ней можно оценить скорость работы программы. Подробно про это написано, например, в книге: "Алгоритмы: построение и анализ" авторы Кормен, Томас и др.

xXx · 2007-01-05 10:10:22

O(f(n)) = g(n) <=> lim(n->oo) f(n)/g(n) = const

FireTiger · 2007-01-05 10:26:10

xXx написав:
O(N^2) - hashtable

+1

Только табличка у меня на 1000000... чисто на всякий случай

xXx · 2007-01-05 10:29:39

1000000 эт не на всякий случай эт ровно минимум для правильного решения....

Yevgeniy · 2007-01-05 10:40:50

Да але на рішення задачі недостатньо одного масиву на 1000000. Для правильного рішення необхідно два масива????

FireTiger · 2007-01-05 10:45:59

Yevgeniy написав:
Да але на рішення задачі недостатньо одного масиву на 1000000. Для правильного рішення необхідно два масива????

Зачем???

xXx · 2007-01-05 10:53:07

один для хеш-значений, другой для самих элементов.....

FireTiger · 2007-01-05 10:56:29

Ну не знаю... мож я чёт не так делал... ну да ладно... посмотрим по результатам.

xXx · 2007-01-05 11:05:17

покажи код... скажу результаты...))

Yevgeniy · 2007-01-05 11:42:41

FireTiger написав:
Yevgeniy написав:
Да але на рішення задачі недостатньо одного масиву на 1000000. Для правильного рішення необхідно два масива????
Зачем???

Для знаходження схожих частин малюнків нам потрібно два знаження вираховувати: це dx i dy між кожною парою олівців, які можна сумістити при паралельному переносі. Далі потрібно знайти в цих масивах максимально можливу кількість елементів Z для яких dx[i] == dx[j] s i dy[i] == dy[j], i != j.І результат тоді N - Z

guest1 · 2007-01-05 11:45:09

Yevgeniy написав:
FireTiger написав:
Yevgeniy написав:
Да але на рішення задачі недостатньо одного масиву на 1000000. Для правильного рішення необхідно два масива????
Зачем???
Для знаходження схожих частин малюнків нам потрібно два знаження вираховувати: це dx i dy між кожною парою олівців, які можна сумістити при паралельному переносі. Далі потрібно знайти в цих масивах максимально можливу кількість елементів Z для яких dx[i] == dx[j] s i dy[i] == dy[j], i != j.І результат тоді N - Z

Ну, я так и делал ...

xXx · 2007-01-05 12:00:44

Yevgeniy написав:
FireTiger написав:
Yevgeniy написав:
Да але на рішення задачі недостатньо одного масиву на 1000000. Для правильного рішення необхідно два масива????
Зачем???
Для знаходження схожих частин малюнків нам потрібно два знаження вираховувати: це dx i dy між кожною парою олівців, які можна сумістити при паралельному переносі. Далі потрібно знайти в цих масивах максимально можливу кількість елементів Z для яких dx[i] == dx[j] s i dy[i] == dy[j], i != j.І результат тоді N - Z

логической связи не уловил.... как это относится к хеш-таблицам?
+ dx и dy можно хранить в одном масиве например dxy, dxy[i] = dx[i]|(dy[i]<<16)

Форум Всеукраїнської інтернет-олімпіади NetOI

#1 2007-01-04 20:29:47

Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#2 2007-01-05 09:17:18

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#3 2007-01-05 09:23:44

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#4 2007-01-05 09:25:43

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

xXx написав:

#5 2007-01-05 09:33:41

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

AlexeyS написав:

#6 2007-01-05 09:36:29

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

alex_kasycky написав:

AlexeyS написав:

#7 2007-01-05 09:36:33

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#8 2007-01-05 09:39:52

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#9 2007-01-05 09:41:01

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

AlexeyS написав:

alex_kasycky написав:

AlexeyS написав:

#10 2007-01-05 09:42:06

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

guest1 написав:

#11 2007-01-05 09:44:12

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

xXx написав:

#12 2007-01-05 09:44:31

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#13 2007-01-05 09:48:44

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

alex_kasycky написав:

xXx написав:

#14 2007-01-05 10:07:11

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

guest1 написав:

#15 2007-01-05 10:10:22

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#16 2007-01-05 10:26:10

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

xXx написав:

#17 2007-01-05 10:29:39

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#18 2007-01-05 10:40:50

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#19 2007-01-05 10:45:59

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

Yevgeniy написав:

#20 2007-01-05 10:53:07

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#21 2007-01-05 10:56:29

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#22 2007-01-05 11:05:17

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

#23 2007-01-05 11:42:41

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

FireTiger написав:

Yevgeniy написав:

#24 2007-01-05 11:45:09

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

Yevgeniy написав:

FireTiger написав:

Yevgeniy написав:

#25 2007-01-05 12:00:44

Re: Обсуждение решения задачи Pencils (только после 23:59 04.01.07)

Yevgeniy написав:

FireTiger написав:

Yevgeniy написав:

Нижній колонтитул