С 9 по 12 января 2017 года будет проходить областная олимпиада по информатике. Первый тур олимпиады состоится 10 января, второй — на следующий день. Постараюсь разместить здесь условия и решения задач как можно скорее, естественно не раньше начала самих туров :) В комментариях предлагаю обсудить задачи, поделиться идеями по поводу их решения, мыслями...
Всем участникам желаю удачи!
UPD. Первый тур завершен. Ниже можно почитать, как же получить полные баллы по задачам.
UPD2. Второй тур тоже завершен. Можно почитать разбор, кроме последней задачи — я ее не решал, да и решений можно придумать множество.
Первый тур
Задача 1
Отсортируем пары (ai, bi) по возрастанию ai. Возьмем первые K подарков. Сложность решения: O(N·log(N)).
Задача 2
Кому может быть выгодно заполнить индивидуальную декларацию? Очевидно, что если жителю с доходом x выгодно заполнить декларацию, то и жителю с доходом y < x будет выгодно заполнить декларацию. Поэтому отсортируем исходный массив в порядке возрастания. А дальше проверяем, выгодно ли каждому жителю заполнить декларацию. Если жителю невыгодно заполнить декларацию, тогда для этого жителя и всех остальных задаем среднее значение. Выводим ответ. Итоговая сложность O(N·log(N)).
Задача 3
Следующее решение я не доказывал, так что будет интересно почитать доказательство (или опровержение) в комментариях.
Заметим, что на самом деле нам достаточно сделать min(n, k) операций. Теперь реализуем простейший алгоритм: будем заменять самый частый символ на самый редкий. Такое можно реализовать за время O(min(n, k)·26). Но на этом еще не все. Такой алгоритм некорректно сработает на строке abbbbbb
. В таком случае выгоднее избавиться от символа a
. Поэтому отсортируем наши символы по количеству вхождений в строку S и просто переберем, какие же символы может содержать строка. Ну а дальше находим ответ для каждого случая. Итоговая сложность: O(n + min(n, k)·262).
Задача 4
Научимся находить ответ для определенной вершины. Для этого подвесим дерево за эту вершину. Для каждой смежной вершины посчитаем такую таблицу: f[i][j] — количество путей четности i и баланса j. Под балансом будем понимать сумму + 1 и - 1 — для вершин с большим номером и вершин с меньшим номером соответственно (по сравнению с номером корня дерева). Такую таблицу можно посчитать одним проходом поиска в ширину.
Как же найти ответ для выбранной вершины? Для этого нужно рассмотреть 2 случая:
- Вершина является концевой в пути, тогда к ответу прибавим: 2·f[0][0];
- Вершина является промежуточной, тогда к ответу нужно прибавить 2·f1[i][j]·f2[i][ - j], где f1 и f2 — матрицы f подсчитанные для смежных вершин, через которые проходит путь.
Если аккуратно объединять ответы для смежных вершин, можно добиться асимптотики O(N). Соответственно для N вершин итоговая сложность O(N2).
PS. На самом деле, можно не хранить четность вершины, так как это показывает баланс.
Второй тур
Задача 1
Нужно отсортировать числа исходного массива в порядке возрастания. Ответ найдем по формуле: . Сложность решения: O(N2) или O(N·log(N)).
Challenge. А можете ли вы решить за время O(N) ?
Задача 2
На мой взгляд самая неприятная задача, но не сказал бы что сложная... Можно решить разными способами, но я расскажу вкратце свой способ.
Суффиксом длины i я буду называть младшие i бит числа N. Воспользуюсь такой динамикой: f[i][j][k][l] — количество вариантов чисел длины i, если последние j бит равны l и число меньше суффикса (при k = 0) или больше суффикса (при k = 1). С помощью такой динамики можно найти ответ за время: O(402·22). Рекуррентные формулы я писать не буду, так как они получаются довольно громоздкими (я уже говорил, что эта задача мне показалась не самой приятной), но их можно посмотреть в моем решении, ссылку на которое я оставил ниже. Итоговая сложность: O(1).
Задача 3
Пусть у нас числа a и b — элементы массива, дающие оптимальный ответ. Представим их в таком виде: a = x·y1, b = x·y2. Тогда, если gcd(y1, y2) = 1, то lcm(a, b) = x·y1·y2. Переберем x, а в качестве y1 и y2 будем брать первых два минимальных частных от деления . Перебирать все делители можно за
. Получим итоговое решение за время:
.
Задача 4
Задача на открытые тесты. Нужно было написать какой-нибудь алгоритм с учетом того, что все веса являются степенями тройки.
Результаты
Спасибо markysha и kodek за то, что поделились результатами областей.
В каждой области все так же своя "система" проверки задач?
Да. Пока в этом плане перемен нет.
Мне кажется, решение третьей задачи получит TL, так как в худшем случае время работы составит 676 миллионов операций.
Хм... Тестировал все задачи на компьютерах, на которых тестировали область в Могилеве — все проходило. Тут видимо от тестов зависит и от машины, на которой тестируется решение (хотя тестировали на довольно слабой).
По поводу третьей задачи первого тура. Ее я бы решал так: Пусть c[t] = j <=> символ t встречается в строке j раз. Пусть f — самый часто встречающийся символ. Если k >= n — c[f], то все символы строки заменяем на символ f (решает проблему со строками вида "abbbbbb"), иначе: min(n, k) раз делаем: заменяем самый частый символ на самый редкий символ. Заметим, что если на каком-то шаге мы получаем строку с неравномерностью 0, тогда заканчиваем цикл.
Итоговая сложность O(n*e), где е = 26 (мощность алфавита). Можно достичь и O(n*log(e)) с помощью дерева отрезков.
Реализация на С++
Р. S. Возможно, я что-то не учел.
Я тут мимо проходил, но...
n = 9, k = 3, s = "aaaaabbbb". Ответ "aaabbbccc", у меня штраф 0, у Вас — 1.
Результаты Витебской области: ссылка
Результаты Бреста:
Оригинал: https://goo.gl/photos/vDkkjGojPMC44HLD6
В тексте: https://brestprog.neocities.org/lections/regional2017.html
Результаты Минска можно найти здесь
Результаты гомельской области:
Результаты Лицея БГУ
Результаты Гродненской области
Мерж таблиц будет?
Я соберу всех,потом выложу.
Захотелось выговориться о некоторых задачах:
1-3: Творились очень странные вещи с этой задачей, баллы могло взять все что угодно. Явно тесты были подобраны не лучшим образом.
1-4: Была группа на 80 баллов с ограничениями n ≤ 1000. Думаю эту группу нужно было сделать n ≤ 2000, так как похоже что она была создана для решений использующих структуры данных, то есть за O(n2 * log). Но никак не для глупых решение, пример.
2-2:
ДП которое работает только когда n = 2k - 1 набирает 95 баллов, хотя в ограничениях сказанно что такие решения будут набирать 80 баллов. Не понятно как такое можно было не проверить -_-
2-3:
Прошу посмотреть на пару решений который брали незаслуженные баллы:
НОК двух минимумов — 60 баллов.
100 баллов.
Решение проходящее на 100 баллов очевидно неправильное и ломается очень простым тестом. Не очень понятно почему такие тесты не были добавлены.
Это все что я смог вспомнить, но думаю меня смогут дополнить.
Скорее всего вы правы. Но я не стал бы критиковать авторов, так как сгенерировать 20 сильных тестов крайне сложно. Тут скорее всего проблема не в тестах, а в формате соревнования.
Табличка со сводными результатами всех, кроме Минской области. В табличку включены первые 15 из каждой области и 18 из Гродненской (как принимающей олимпиаду у себя). Если в других командах есть изменения, сообщайте поправлю.
Спасибо!
Только небольшой баг, у Мелеха Алексея (Минск) не 391 балл, а 506,74
Результаты Минской области
Теперь в табличке все результаты.
Мое решение для 1-4:
На длке проходит на 100.
Оно похоже на то, которое в посте, но как то меньше циклов for :-)
По идее такое, как в этом https://acm.bsu.by/oi-minsk/2016-17/city/explain.pdf разборе.