Блог пользователя Yury_Bandarchuk

Автор Yury_Bandarchuk, история, 9 лет назад, По-русски

Всем привет!

Ну что же, вот и пришел сезон личных олимпиад в Беларуси. Совсем скоро, 12-13 января по всей Беларуси будет проходить областная олимпиада по информатике.

Предлагаю в этом посте выкладывать условия, обсуждать задачи и прочее и прочее. Я же от себя после туров буду делиться своими идеями по задачам.

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

Good luck && Have fun!

Day 1.

  1. Тупая реализация! Главное, аккуратно чекать случай, когда есть ### и выстрел в центр.

  2. A — массив ответ. A[1] = y. Дальше просто добавляем единичные биты в свободные позиции. Проверяем, что набралось N элементов — выводим ответ, иначе -1.

  3. Дп F[pref] — ответ для префикса pref. left[x] — левая граница числа x, right[x] — правая соответственно, cnt[x] — количество. Пересчет

  • f[pref] = f[pref — 1]
    • если pref == right[a[pref]], то f[pref] = max(f[pref], f[left[a[pref]] — 1] + cnt[a[pref]]

Ответ лежит в f[n].

  1. Брут за N * K^2 довольно простой, фиксим позицию которая так и останется стоять (это N * K) а дальше смотрим как нужно повернуть минимально остальные диски.

По ограничению из условия — это 60.

Итого — 360 очень простых баллов.

Кто знает как решать 4-ую на сто?

Day 2.

  1. Обычная потная реализация! (фу-фу-фу давать такие задачи два дня подряд).

  2. дпшка f[i][j] — где i — последний чувак, которого мы поставили, j — сколько пьедесталов рассмотрели. f[i][j] — минимальная высота, на которой стоит i — парень.

  3. дпшка f[i][j] — где i — последнее письмо, которое мы доставили, а j — сколько раз мы ходили вдоль домов. f[i][j] — максимальное количество писем, которые можно доставить с такими параметрами. Пересчет фенвиком, ибо думаю что ДО должно упасть.

  4. Единственная задачка, которая требует чутка внимательности и соображалки. Ответ всегда 2!!! Исходя из этих соображений просто закидываем весь набор в сет пар (количество книг, тип книги). Дальше просто жадно берем первый и последний элемент. Они гарантированно замостят всю строку! Ну вот и все, генерим outputs и получаем 100 баллов.

Итого — 400 очень простых баллов :).

  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

Условия первого дня:https://goo.gl/photos/QKFXuHDqQ5wANCMs8

»
9 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Yury_Bandarchuk (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

4ая задача. Давайте переберём цвет, который будем ставить в один ряд. Теперь смотрим на его позиции во всех строках. Допустим в строке i это b1, b2, ..., bk. Теперь видно, что нам выгодно сдвигать bi к позициям с bi до (bi + 1 + bi) / 2, а bi + 1 к позициям с (bi + bi + 1) / 2 + 1 и до bi + 1. Видно, что нам надо просто уметь добавлять арифметическую прогрессию на отрезке, а потом после добавлений получать наш массив. Делать это можно с помощью префиксных сумм.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Также можно реализовать эту идею, возможно, чуть проще: опять же разбиваем каждую строку на соответствующие отрезки, но потом используем не дерево отрезков, а проходим сканлайном.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +52 Проголосовать: не нравится

      Так никто вроде про дерево отрезков и не говорил)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +58 Проголосовать: не нравится

      Вроде префиксные суммы легче сканлайна.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        Хех. Да, моя ошибка, поторопился, не дочитал до конца, сделал неправильный ход.

        На самом деле просто я придумал решение со сканлайном, а когда увидел фразу "прибавлять ... на отрезке", ни о чем, кроме ДО, думать уже не мог.

»
9 лет назад, # |
  Проголосовать: нравится -57 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Yury_Bandarchuk (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

в 3ей задаче не надо дп. Просто максимальная возрастающая в массиве A+rev(A)+A+rev(A)+...+B. B=rev(A), если K чётное, а иначе B=A. Речь идёт о 3ей задаче второго дня.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Одна из самых красивых реализаций — считать возрастающую подпоследовательность фенвиком и ходить туда обратно по массиву.

»
9 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится
»
9 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

В третьей задаче первого тура (дня) дп не нужно: решение без дп, но с графами

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -26 Проголосовать: не нравится

    Не понимаю, почему у этого коммента так много минусов.. (хотя код я не смотрел:) )

    Действительно, можно было придумать красивое решение за O(N + max(A)^2). Будем хранить для всех чисел A(i-е) самое левое и правое его вхождение в исходную последовательность, а также количество чисел, равных A(i-е) (обозначим как cnt(i-е)).

    Теперь построим ориентированный граф, где вершинами будут являться числа A(i-е) ( не более 100 вершин). Тогда добавим ребро между i-ой и j-ой вершиной тогда и только тогда, когда самое правое вхождение числа A(i-е) находиться левее (т.е. индекс меньше) самого левого вхождения числа A(j-е).

    Вполне очевидно, что получившийся граф ацикличен. Теперь для нахождения ответа осталось лишь посчитать путь максимальной стоимости, где стоимость определяется суммой cnt по вершинам, входящим в путь. Делать это можно как угодно, например, запуская дфс из каждой вершины.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

      Не понимаю, почему у этого коммента так много плюсов. Cuellius'а минусили не за то, что его решение "некрасивое" (кто и как определяет красоту — непонятно) , а скорее за то, что он не рассказал свое решение, а просто скинул код, в котором не каждый сможет разобраться. За такое действительно можно минусить.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

      Вот именно потому, что граф ацикличен, Cuellius'a заминусовали. Вы же с ним только что такое же дп написали, как и у всех, просто у вас пересчет необычный. А так — все то же самое, ведь состояния и переходы в дп и есть ацикличный граф. Это были минусы за что-то в духе "ты че тут самый умный штоле?"

»
9 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Будут ли сводные результаты ? Результаты г.Минска

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Здесь результаты претендентов в областные команды Минска, Гомеля, Бреста (прошу прощения, если чью-то фамилию с фотки набрала неверно) и Лицея БГУ. То что доступно.

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Результаты минской области.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Результаты Гродненской области

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

А где результат Юры, его нет в таблице?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Юра в Казахстане, на Жаутыковской олимпиаде. На Республику едет без участия в областном туре.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Все команды, кроме Витебска и Могилева.

»
9 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Результаты Витебской области: https://goo.gl/photos/hyQnHqkna23WAfDJ9

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Результаты команд без Могилева

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Сколько человек планируется команда Могилевской области?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      15 + 1 (город, не область) => 16 человек

      Т.е. позиции 1-15 и 17.

»
9 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

И наконец, результаты 3 этапа Белорусской республиканской олимпиады по информатике. Сводная таблица всех команд. Смотрите, анализируйте, делайте выводы. Всем успехов в марте в Могилеве.