Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1 2 3
  21  Шефтелевич Павел Аркадьевич, 03 июня 2011 г. 19:49:22
     merge sort проходит последниq тест за 0.45-0.5c имея сложность n*(log n). для подсчета инверсий это оптимальная сложность, как же народ сдает быстрее чем за 0.15(сумматоры ведь тоже n*(log n))?
  22  Ким Игорь, 13 мая 2011 г. 9:42:34
     Опять-опять из-за медленности Java приходится переписывать код на Pascal.
Может, изменить ограничения для Java ?
  23  Фурко Роман Владимирович, 26 февраля 2011 г. 13:12:14
     а причём тут сортировка??? я писал Дерево Фенвика!
  24  Пересадин Илья, 09 февраля 2011 г. 0:14:00
     мучался, пытался за nk...так и не придумал, сдал слиянием, ну явно можно сорт подсчетом...
  25  Менщиков Александр, 06 октября 2010 г. 17:11:52
     Интересно какие еще есть методы кроме дерева и слияния?
     Еще можно подсчетом, похоже на решение задачи Stars на тимусе.
  26  Лизунов Михаил, 31 августа 2010 г. 15:55:10
     mergesort?
     это один из возможных способов решения задачи, далеко не самый короткий...
  27  Ладик Артём, 28 августа 2010 г. 3:46:24
     те кто решает бин. деревом, не сбалансированным, решение превращается в квадрат, но такого теста нет и решения проходят
     Вряд ли чистый квадрат проходит. По крайней мере банальное решение или использование сортировки пузырьком не проходят. А то несбалансированное бинарное дерево все же не совсем квадрат. Только если спец. тесты создать. Это так же, как и быстрая сортировка может быть квадратом. Считаю, что если человек использовал дерево, то он уже молодец :)
  28  Ладик Артём, 28 августа 2010 г. 3:43:43
     Обновите тесты!!!
На этом сайте ее можно сдать и за квадрат
добавьте тесты похожие на этот
10000 20
1 2 3 4 5....
10000 9999 ....
......
  29  КаБэ `15 кодит, 28 мая 2010 г. 12:36:23
     то есть "вычеркивание минимального элемента последовательности, у которого инверсий ровно столько, сколько элеметов перед ним" здесь никак не пройдёт? тогда я сдаюсь(((
все свои учебники по алгебре перекопал, не нашёл иного более-менее программируегого метода подсчета числа инверсий. сдать бы эту задачу на Мэпл)))
  30  Никитин Андрей Иванович, 20 февраля 2010 г. 12:02:35
     Извините, но я считаю, что у вас во втором тесте ошибочка - 5 2, 4 3, 5 3,
3 1, 2 1, 5 4. Там будет 6! Или я не доконца понял?
     Вы просто невнимательный, там в обоих рядах 5 4, а тут вы один раз только перечислили.
  31  Самаль Александр Васильевич, 06 января 2010 г. 16:48:13
     Интересная задачка! Очень похожа на задачу 1090 с тимуса. И там, и тут решал с помощью сортировки слиянием.
  32  Лалетин Вадим Викторович, 06 октября 2009 г. 19:56:25
     Отличная задача:)
  33  Bogdanova Ira, 22 февраля 2009 г. 23:52:34
     Как в первом примере получается 4?
3 3
1 2 3 - 0
2 1 3 - 1
3 2 1 - 2
Итого: 3, а почему в OUTPUT-е 4?
     Вы просто считать не умеете. В последнем ряду 3, а не 2 приседания: 2й приседает 1 раз, т.к. слева 3ка, большая его, а 1ка приседает дважды, т.к. 2 человека выше. А как известно, 1+2=3, а 3<>2. Таким образом, получается, что 0+1+3=4. Что и требовалось доказать.
  34  Кулик Сергей Дмитриевич, 07 февраля 2009 г. 15:22:37
     какая сортировка??? тут же сумматор
     тут есть по крайней мере 3 решения задачи, в том числе и сортировкой можно.
  35  Ладик Артём, 21 января 2009 г. 22:11:08
     ХаХа решил построением бинарного дерева......
  36  Ладик Артём, 01 октября 2008 г. 22:40:53
     Скажите а эта задача точно на сортировку и на последовательности. Мне кажется что эта задача совсем отличается по методу решения от других задач на это тему..
     Здесь есть и другое решение. Но сортировка здесь так же может быть актуальна.
  37  Романов Егор Николаевич, 21 марта 2008 г. 23:16:53
     Беляев Игорь-"сложность моего решения O(k*(n^2)/2 * log(n)^2)).." А почему оно вообще проходит? если k*(n^2)/2 * log(n)^2)=10*10^8*log(10^4)^2=10^9*log(10^4)^2, что ни как за 10 сек не пройдёт, не говоря про 1 сек
     Он ошибся с вычислением порядка сложности, там на самом деле O(k*n*ln(n)).
  38  Беляев Игорь (<-UnderFelixAbove->) 21 год, 19 января 2008 г. 14:57:04
     сложность моего решения O(k*(n^2)/2 * log(n)^2)).. очень интересно как его делали другие участники. Я использовал идею ...
     Я использовал эту же идею (решил ее удалить из вашего сообщения), сильно хорошая подсказка. Но я смотрел другие решения. И наше решение не единственное, есть очень короткие решения этой проблемы.
  39  Andrew, 29 октября 2007 г. 22:19:33
     Поясните первый и второй пример а то что-то не понятно (не понял почему так получилось )
     А вы пытались понять? Все ведь просто: в первом примере, в первом ряду 1 2 3 никто не присядает, т.к. все стоят правильно, во втором ряду 2 1 3 присядает только рядовой 1, т.к. слева у него стоит более высокий, а в третьем ряду 3 2 1 присядает солдат 2 один раз, т.к. слева 3ка, а рядовой 1 присядает 2 раза, т.к. слева 2 солдата, которые выше его. Итого получилось 1+2+1=4 приседаний. Думаю разъяснений 1го теста достаточно.
  40  Бобер Александр Дмитриевич, 26 октября 2007 г. 5:01:26
     С детьми перестал работать-некому подсказать. Не знаю этот алгоритм. Надо искать!!
     Наверняка знаете, но не можете к нему эту задачу свести.
 1 2 3

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru