Архив форума

Скажите, пожалуйста, на Тимусе в субботу условия задач совпадали с теми, которые сейчас выложены? Или были изменения/исправления?
Может кто-нибудь помнит, как решать задачку с медианой последовательноти( http://acm.timus.ru/problem.aspx?space=12&num=7) ?
Расскажите.

называется "алгоритм поиска i-той порядковой статистики". решается за О(N). см. http://school.belhost.by/projects/schoolhelp/index.php?section=4,2,44
а лучше ахо ульман хопкрофт "структуры данных и алгоритмы"

Не понял. Массив-то надо хранить. А это явный Memory Limit

да я уже и сам понял что неправ. ну посмотри обсуждение на тимусе
http://acm.timus.ru/forum/thread.aspx?space=1&num=1306&id=9436
идея про 3/4 - вроде ничего. хотя не знаю.

Ха! Мы сегодня тренировались на этом комплекте и решили задачу именно этим способом. Те хранили 75% всех чисел. Памяти ушло 930kb. Но на самом деле задача шестилетней давности и решалась на 16-битных компиляторах, те с памятью до 600kb. Автор предлагал 2 раза пробежаться по файлу. Но, наверное, можно решить и за один проход. Вот только как? Или как два раза бежать по stdin'у ?

ну, в паскале мождно применить reset(input) еще раз. видимо в С что-то типа того..
как у вас тренировка? шансы на ЧУ-то есть по собственной оценке?

Неплохо потренировались, сдали все за 4.5 часа...

ну вы видели с кем предстоит сражаться...
здесь не только умение но и психику крепкую нужно иметь

А вы возьмите меня в качестве шамана, я ваших соперников прокляну, и они нифига решить не смогут. То, что написано ниже - не первоапрельская шутка, и Углов при случае это подтвердит: перед отбором на чемпионат он повел себя высокомерно по отношению ко мне (ну это в его стиле), и за это я взял в руки соответствующие аттрибуты и сказал зловещим голосом, потрясая ими: "Я ПРОКЛИНАЮ ВАШУ КОМАНДУ ЭТОЙ ЗАЧЕТКОЙ С ТРОЙКОЙ ПО ДИСКРЕТНОЙ ОПТИМИЗАЦИИ И ДРАНОЙ КНИЖКОЙ АСАНОВА!!" В зачетке на самом деле тройка, а книжка на самом деле поистрепалась, с 2000-то года :lol: Итог: у команды Углова, какого-никакого, но полуфиналиста, решено столько же задач, сколько у моей команды платников-троечников :oops: :lol:

Да, согласен, неспортивно использовать паранормальные способности в честной борьбе, но кому сейчас легко? :lol:

завасит от особенностей операционной системы и дескриптора, который перенаправляется в standart input. если это обычный ввод с консоли - не сработает. если перенаправление из файла - сработает. если из пайпа - не знаю. на тимусе - работает.

Обошелся без многократного чтения данных. Храню блок длиной N/2, содержащий минимальные прочитанные на каждом этапе алгоритма числа, читаю новые данные блоками по M, сортирую, сливаю. Памяти требуется N*4+M*8, выч. сложность M/N*(M*logM+N), по-моему, решаемо и на 16-битных компиляторах.

Я туплю что ли? Там, по-моему, N=250000, и 4*N в ML не лезет, тем более на 16-битниках.

это я туплю, у меня в программе у N другой смысл :) в терминах исходной задачи - N*2+M*8 - массив под меньшую половину чисел + массив под блок + резерв для склеивания.

в форуме на тимусе говорят, что это решается за N*logN с памятью N/2. хм.

как я понял, NlogN это все тот же алгоритм на базе Qsort, но модифицированный под разбивания на 2 части.

если кто не знает, buggzy на тимусе - это я, так что если хочется что-то у него спросить, можно обращаться и ко мне тоже :))

Между прочим эту задачу можно решить за O(N*log(N)), храня только половину массива, при помощи хипа.

"можно решить" означает AC или только предположение? ...а, тут товащ с тимуса подсказывает, что это какая-то структура данных, которую изучали у Лахтина во втором семестре :) ок, пойду велосипед изобретать...

Угу, получил AC с хипом за вдвое меньшее время, и код покрасивее и попроще получился.