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

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

HotLog


 
[Вернуться к задаче]   1 2
  1  АЩщщ, 08 ноября 2019 г. 19:25:50
     Просто обычный Фенвик ,тут даже думать над алго не надо.
  2  Аркадий Сиплюсович, 20 октября 2019 г. 17:09:04
     легкая sqrt декомпозиция
  3  Винк В В, 17 марта 2018 г. 20:58:18
     В условии написано:"В каждом ряде". Так недалеко и до "ихнего" или "евошнего" )
  4  Иванов Иван, 20 сентября 2017 г. 0:41:17
     Одномерный фенвик -- TLE 10. Поставил scanf() -- зашла 0.186
  5  Монтеверде Авраам Соломонович, 22 июля 2017 г. 22:41:29
     В задаче не нужны никакие специфические структуры данных, кроме обычного массивчика, который можно сортировать (вектор).

Заметим, что если справа от солдата A находится M солдат, меньших А ростом, то при сортировке (так как все числа различны) ему так или иначе придётся пропустить этих М солдат слева от себя. На что это похоже? Правильно -- число инверсий для роста А в перестановке чисел от 1 до N.

Ну а для подсчёта числа инверсий в последовательности чисел давно используется merge_sort (сортировка слиянием) с небольшой модификацией. Итоговая ассимптотика решения -- k * n * log n, что по времени укладывается в 1 секунду. Моё решение работает 0.25 секунд максимум.

И не нужно тут никаких деревьев.
  6  Зубашев Степан, 07 августа 2016 г. 15:28:39
     Нашёл разбор. Понял главную свою ошибку. Можно решить гораздо компактнее и проще, если по-другому подходить к подсчёту кол-ва солдат выше ростом. Не важно что вы используете (скажем дерево отрезков, дерево Фенвика или же sqrt-декомпозицию). Ключ к простому решению: возможность обновления древа при просчёте результата слева направо. Подсчитали для I-го солдата, поправили древо, посчитали для I+1-го.
И тогда не нужны сортировки и бинарный поиск по сортированному массиву. Правда получилось всего в 1.5 раза быстрее :)
  7  Зубашев Степан, 04 августа 2016 г. 21:03:37
     Решил, используя:
1. дерево отрезков с подмассивами
2. сортировку слиянием (ввиду п.1)
3. бинарный поиск
Как-то уж больно лихо для 58%, не находите? Полагаю, что я сильно перемудрил. Можно было обойтись древом отрезков и без подмассивов? Судя по лучшим результатам ребята в 200 мс укладываются.
  8  Зубашев Степан, 04 августа 2016 г. 20:49:12
     Неожиданно для себя обнаружил, что моё решение не проходило из-за throw, который я использовал пока отлаживал своё решение. throw в коде остался, хотя и не использовался. Алгоритм работал. Но я уверенно получал TLE 1.3sec. Убрав неиспользуемый throw получил 0.5 sec. Нет я знал, что исключения это медленно, но я наивно полагал, что медленно отлавливать ошибки. Оказывается медленно всё. Для олимпиадных задач, похоже, совершенно не годится.
  9  Ислом Искандаров, 01 сентября 2015 г. 21:34:18
     Дерево отрезков !!! :)
  10  Керножицкий Александр Сергеевич, 19 мая 2015 г. 13:29:22
     Дерево Фенвика!!!
  11  Денис Розимовский, 16 мая 2015 г. 17:33:24
     Так же можно решить через более элегантное BST (бинарное древо поиска).
  12  Денис Розимовский, 16 мая 2015 г. 11:58:47
     Использовал структуру данных vector. При каждом новом солдате искал неким подобием бинарного поиска его место в этом векторе. Потом добавлял к финальном результату число равное количеству чисел, которые идут после j-того солдата.
  13  Егоров Владимир Тимофеевич, 24 августа 2014 г. 8:35:51
     Гы, моё решение за 0,047 прошло.
  14  Аман Жарасхан Алматович, 07 декабря 2012 г. 16:49:35
     5 2
1 5 2 4 3 => (5 - 2) + (5 - 4) + (5 - 3) = 3 + 1 + 2 = 6
2 3 1 5 4 => (3 - 1) + (5 - 4) = 2 + 1 = 3
6 + 3 = 9
Почему ответ 7
     Мне вообще не понятны ваши записи. На самом деле дело обстоит так: в первом ряду отжимаются 3 солдата: 2 солдата с ростом 2 и 4 отжимаются по 1 разу (т.к. всего один солдат слева от них выше их самих, это солдат с ростом 5), солдат с ростом 3 отжимается 2 раза, т.к. солдаты с ростом 4 и 5 выше его и находятся левее. Итого в первом ряду мы имеем 1+1+2=4 отжимания. Со вторым рядом еще проще, там отжимаются всего 2 солдата - это солдаты с ростом 1 (2 раза отжимается, т.к. слева солдаты с ростом 2 и 3) и ростом 4 (1 раз отжимается, т.к. только один солдат с ростом 5 левее). Итого во втором ряду мы имеем 1+2=3 отжиманий. В результате получаем, что сумма отжиманий по всем рядам равна 4+3=7. Что и требовалось объяснить :)
  15  Глембоцкий Владислав Олегович, 22 апреля 2012 г. 1:56:34
     Шефтелевич Павел Аркадьевич
У меня слияние прошло на 0,14 (все зависит от сервера)
  16  Беляев Игорь, 14 июня 2011 г. 11:49:04
     2Шефтелевич Павел: Ассимптотики одинаковые, а константы разные. У merge sort константа больше из-за того, что там приходится создавать временный массив, куда сливаются два подмассива.
  17  Шефтелевич Павел Аркадьевич, 03 июня 2011 г. 19:49:22
     merge sort проходит последниq тест за 0.45-0.5c имея сложность n*(log n). для подсчета инверсий это оптимальная сложность, как же народ сдает быстрее чем за 0.15(сумматоры ведь тоже n*(log n))?
  18  Ким Игорь, 13 мая 2011 г. 9:42:34
     Опять-опять из-за медленности Java приходится переписывать код на Pascal.
Может, изменить ограничения для Java ?
  19  Фурко Роман Владимирович, 26 февраля 2011 г. 13:12:14
     а причём тут сортировка??? я писал Дерево Фенвика!
  20  Пересадин Илья, 09 февраля 2011 г. 0:14:00
     мучался, пытался за nk...так и не придумал, сдал слиянием, ну явно можно сорт подсчетом...
 1 2

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

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