Традиционное обсуждение (или осуждение -- кому как) регионального этапа ВсОШ 2022 года. Кажется, к 15 часам МСК он уже должен был закончиться везде.
Традиционная сборная таблица результатов: https://reg.prog.cf/. Пока данные берутся только из опроса (заполните!) и нескольких официальных таблиц, когда появятся остальные -- добавится информация оттуда.
Отдельная просьба организаторам и другим людям с доступом к результатам своего региона: пожалуйста, перешлите их @prog_cf_bot.
Ура, написал худший регион
Кажется, что очень просто.
Такое чувство, будто градация сложности несколько более ломаная, нежели раньше. P.S. в чем идея в D?
У кого-то в D алгоритм Манакера, у кого-то хеши + бинпоиск. В целом примерно то же самое, что и в задаче поиска палиндрома максимальной длины. Могу поподробнее рассказать чуть позже, если будет нужно и еще не будет разбора
Я получил 46 баллов за алгоритм Манакера, не дадите подсказку как его использовать, чтобы полный балл получить?
Кажется, я не правильно кого-то понял. Видимо, на 100 Манакера не получается загнать.
Можете дать подсказку о решении, которое можно загнать на 100? Я смог узнать, что можно сделать палиндром из подстроки A, только если есть подстрока B, где разность b[i]-b[n-i+1] == a[n-i+1]-a[i], но я так и не нашёл ни как искать такие штуки быстро, ни как быстро их строить :/
Пусть у тебя есть массивы x_1, x_2, ..., x_n и у_1, y_2, ..., y_n. Тогда заметим, что хэш массива x_1 — y_1, x_2 — y_2, ..., x_n — y_n равен разности хэшей массивов x и y. Тогда если есть подотрезок в a или b, то можно его представить как разность хэшей его левой и правой половины. Сделаем бинпоиск по ответу (чётные и нечётные отдельно, получится 2 бинпоиска), внутри бинпоиска считаем такие разностные хэши всех подмассивов b заданной длины, затем проходимся по подмассивам a и проверяем их на наличие в b (set или unordered_set).
Написали ж сразу, что хеши (см хеши со строками на e-maxx, если не знакомы).
Задачу можно интерпретировать как поиск максимального k такого, что можно взять подстроки длины k из A и B дающие в сумме палиндром.
Если нужна подсказка, а не решение, то дальше смотреть осторожно.
Как вариант решать так:
Для того, чтобы не было коллизий, можно, кстати, просто использовать два хеша или большой хеш (у меня порядка $$$10^{13}$$$ зашел).
Подзадачу про поиск палиндрома наибольшей длины можно было решать в тупую за квадрат, спасибо тестам
http://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-spb-2022-standings-day1.html http://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-lo-2022-standings-day1.html
Санкт-Петербург: http://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-spb-2022-standings.html
Ленинградская область: http://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-lo-2022-standings.html
До апелляций и добавления тех, кто писал в Сириусе
Таблица результатов для регионов, которые писали на Codeforces:
https://codeforces.com/spectator/ranklist/01ee6bf8e561980c5201d4b494ad5e8d
Добрый вечер. А яндекс.контест сегодня-завтра покажет результаты своих городов, не знаете?
Сводная таблица для регионов, которые писали на Codeforces, по двум дням:
https://codeforces.com/spectator/ranklist/6ab02a1660b6b40e3baae60b689299fb
Добрый вечер. Не могли бы вы пожалуйста сделать контест с задачами регионального этапа на кф?
В тренировки уже залили
А есть дорешка?
Предварительные результаты первого тура на Яндекс.Контесте: https://contest.yandex.ru/roiarchive/results/
Результаты Липецкой области, похоже, тут: https://ejudge.strategy48.ru/ejudge-new-standings/regional/regional-2022-day1-wonaumokicasakoome
Есть у кого-нибудь мысли по B? У меня так и не получилось придумать ничего стоящего. 10e7 платформ. Я даже не уверен, что алгоритм отработает за секунду при O(n).
O(n) на C++ даже при n <= 1e8 заходит.
Это радует) У тебя есть какие-либо мысли по задаче?
Я не решил последнюю подзадачу, но мысль есть. Там m = min(n, 1e5), Так что, наверное, нужно задачу решить для Первых m элементов, как в подзадаче (f = 1, n <= 1e5, на 20 баллов) за O(nlogn), а потом эти подсчеты использовать для решения последней подзадачи. Я подумал, что может старт начинается с этой же платформы, с которой найдет наш алгоритм для первых m. Но это не так, я пробовал.
В полном решении при f = 2 я просто восстанавливаю массив d по формулам, так что я даже не знаю зачем это сделано, может быть для более простого создания тестов.
Это сделано что бы отсечь решения за nlogn. Отсечь n от nlogn с обычным вводом не представляется возможным, потому-что сам ввод занимает примерно столько же времени что и nlogn алгоритм
Напиши решение за O(n^2) и посмотри для каждого элемента, сколько нам нужно, если начать с него. Дальше посмотри на получившийся массив с конца и вроде становится очевидно как писать за O(n).
Там максимум на префиксе и cуффиксе. Вот формула подсчета: dp1[i] = max(dp1[i-1]+1, d[i-1] — n +1) , dp2 = max(dp2[i+1]-1, d[i+1]-1). Ответ: Минимум по всем max(dp1[i], dp2[i+1]).
Можно проще, записать в массив d все расстояния из входных данных, и обойти этот массив с конца в начало по формуле d[i] = max(d[i], d[i+1]-1). Потом найти минимум среди этих значений, это и есть ответ. Зашло на 100
dp[i] = max(d[i], dp[i+1]-1), почему нигде не пишут про это решение?
А второй день легче будет или такой же? В прошлом году второй полегче был.
легче)
Сириус оба тура: https://codeforces.com/spectator/ranklist/5f4cc0619f438b5f63a971d579965905
Ура-ура-ура, цпм
Сделай вид, что это потому что это в ШЦПМ крутой кружок по олимпиадной проге
Предварительные результаты второго тура на Яндекс.Контесте: https://contest.yandex.ru/roiarchive/results/
Сводная таблица по двум турам для регионов, принимавших участие на codeforces: https://codeforces.com/spectator/ranklist/6ab02a1660b6b40e3baae60b689299fb
Липецкая область https://ejudge.strategy48.ru/ejudge-new-standings/regional/regional-2022-summary-jazikotargarikusaz
Разбор задач http://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-tutorial.pdf
Видеоразбор https://www.youtube.com/playlist?list=PLHX_ZgKaM8sJ2pV66jLr5N5QaBsTi1Yql
Как же я люблю $$$O(nk^2log)$$$ в $$$D$$$ на сто баллов)
Так сказать
if (1.0 * clock() / CLOCKS_PER_SEC > 0.9)47->100Чел, у меня nklog не зашло на 100 (на 86), как ты nk^2log на 100 загнал?
Написал в коментарии до этого)
Публичный контест на Яндекс.Контесте:
Добавил оба тура в тренировки: