Всем доброго времени суток!
Начался отборочный (заочный) этап олимпиады, который продлится до 15 января. Опубликованы первые пять задач олимпиады (новые задачи будут добавлены позже), открыта регистрация и тестирующая система для сдачи задач. Весной 2014 года будет проведен очный финальный тур олимпиады, на который будут приглашены участники, показавшие высокие результаты в заочных турах. Страничка олимпиады — olympiads.ru/zaoch.
Жюри олимпиады считает своим долгом напомнить, что любое обсуждение задач (в том числе в комментариях к данному посту) будет караться немедленной дисквалификацией. Все вопросы по условиям задач задаются через тестирующую систему.
Следите за обновлениями на сайте олимпиады и в тестирующей системе.
Что на счёт копипасты с e — maxx ?
префикс-функцию сам не можешь написать?
По моему это считается как подсказка.
Та ладно что вы его заминусовали, парень просто пытается убирать конкурентов :)
Шутки — шутками, а я все — равно не понял, будуь банить или нет?
Да вряд ли. Если происходит копипаста с емакса, то человек не в состоянии выучить/понять алгоритм сам, а значит либо не пройдёт на очный этап либо ничего достойного там не займёт, а значит бояться такого участника не надо.
Осталось меньше месяца, скоро ли добавят новые задачи?
"Добавлены пять новых задач (F-J), в ближайшее время будет добавлена еще одна задача. "
Напомню, что сегодня последний день заочного этапа. timeanddate
Последние два дня условия задач на сайте не скачиваются.
Как решать задачу про торты?
Коротко : дп по профилю + кэши => прекалк.
Длинно :
1) Будем держать такие переходы : пусть i — маска торчащих из предыдущего столбца доминошек, тогда vector переходов g[i][j](->k) переход из нашего столба в предыдущий, так что j — финальная раскраска предыдущего столбца, а член такого вектора(k) — список торчащих из препредыдущего в предыдущий столбец доминошек.
2) Тогда запустим такой dfs(cur, vector now), где cur — номер столбца, now — vector неинвариантных i(из предыдущего пункта) к текущему столбцу( то есть ответом будет (dfs(m + 1, {0} ). Внутри dfs мы находим объединение переходов к (j; k), то есть держим мап мап. Откаждого полученного списка j запускаем dfs(cur — 1, {k}). Ответ — сумма.
3) Закэшируем это дело, получаем , что для (n == 6 и m <= 500) считается примерно минуту.
4) Всё
5) Код
Как скоро появятся предварительные результаты заочного этапа?
Поделитесь, кто как решал J?
моё решение:
1) забудем пока про возможный цикл, теперь у нас лес.
2) заметим, что в запросе для каждого T нужно найти ближайшего предка F. Для каждой такой пары найти максимум на пути (вес ребра — его номер), а потом среди всех таких величин минимум.
3) найти максимум по пути вверх можно за logN и NlogN памяти (метод двоичного подъёма)
4) как найти для T его предка? перед запросами запустим по лесу dfs и запомним время входа/выхода для вершин. тогда отсортив T[] и F[] по времени входа можно эмулировать dfs только на этих вершинах, поддерживая стек и два указателя.
5) вспоминаем про цикл — ребро из откуда-то в корень дерева. тут нужно знать много инфы: для каждой вершины в каждом дереве запомнить, что она на цикле, в какой она компоненте, вес ребра для каждого дерева и вершину, из которой (вверх) идёт это ребро. запрос же разбивается на три величины: от самой нижней вершины F на цикле до вершины из которой идёт ребро вверх, само это ребро и от корня до вершины T.
Я находил все циклы, сжимал в одну вершину и решал 3 случая : на дереве, на сжатом цикле, и, сначала на дереве, а потом на сжатом цикле.
Ничего, что задача H боян?
во-первых, это лишь подзадача, а во-вторых на e-olimp'е всё равно никто не сидит.
Без этой подзадачи нельзя было получить 80 баллов, а на e-olimp 51(!) засчитанное решение по этой задаче.
Вот ещё один баян (2491 засчитаных решений), и на snws была задача K (а туда задачи берут с регионов), и F по-любому где-то была (уж больно банальная формулировка), и задача E сводится к баянистым вещам. И как это вообще терпеть? Авторов на мыло!
Я не говорил ничего вроде "авторов на мыло", я просто указал на боян, о котором, по моему, знали не все участники, а мое замечание о 51 решении относилось исключительно к популярности e-olimp-а.
Между тем эта задача входила в тройку самых сложных:(
А нельзя посмотреть код, который ты отправил?
В прошлом году открыли эту возможность после проверки на списывание, вроде.
UPD: Уже можно.
Уже можно)
Как решать F?
Вообще задача довольно известная. Здесь описано одно из решений.
Лично я, впрочем, решал иначе. Решение было за O(N + MAX(ai)). Я в динамике DP[1..1000000] хранил массив количества подпоследовательностей, которые оканчивались НЕ числом ai и исходя из этой информации пересчитывал суммарное количество подпоследовательностей. Частью решения было увеличение всех значений в DP[1..1000000], кроме ai. Для этого использовалась идея, схожая с несогласованными поддеревьями в дереве отрезков для изменений на подстроках. Отдельно хранилось число, характеризующее суммарное общее отклонение элементов от нуля — control. К нему добавлялось DP[ai], а после этого DP[ai] пересчитывалось так, чтобы DP[ai] + control возвращало такое же значение, что и раньше.
Посчитаем динамику dp[i] — количество различных подпоследовательностей, заканчивающихся в позиции i. Тогда, если все числа различные, то dp[i] = dp[0] + dp[1] + ... + dp[i — 1]. Теперь заметим, что если у нас раньше была такая цифра, то некоторые подпоследовательности будут повторяться, найдем такую максимальную позицию j (j < i && a[j] == a[i]), тогда ответом будет dp[i] = dp[j] + dp[j + 1] + .. + dp[i — 1]. Ответ задачи — сумма всех dp. Соответственно, чтобы быстро пересчитывать динамику понадобятся частичные суммы, а также массив, который позволяет находить нам позиции j за О(1).
участники, показавшие высокие результаты в заочных турах
ААА высокие резултаты это сколько????
Спасибо :D
По опыту прошлых лет, думаю, что для 11-х классов это будет 600-650 баллов, а для "младших" ~ 500-550. Ждём-с.
Как решать D не на 30 баллов?
Не на 30 и не на ноль, разумеется)
И кстати, задача аналогичная D есть на тимусе http://acm.timus.ru/problem.aspx?space=1&num=1150
Вот мой код. Небольшие пояснения: в func считаем ответ для чисел меньше max и не учитывая числа меньшие 10⌊log10(max)⌋ если flag = false. В answer[i] — количество цифр i среди выписанных.