Привет, Codeforces!
Скоро начнётся XXII Открытая Всесибирская олимпиада им. И. В. Поттосина — соревнование по программированию, в котором принимают участие студенты вузов со всей России, а также стран СНГ. Основной язык олимпиады, на котором написаны условия задач и происходит общение с жюри, — русский.
Олимпиада состоит из отборочного и финального этапов. Отборочный этап (известный также как "интернет-тур") проходит через интернет, и участвовать в нём могут все желающие команды. В этом году по-прежнему финальный этап будет проходить в режиме онлайн, участникам не придётся ехать в Новосибирск. При отборе команд в финал для команд от Сибири и Дальнего Востока выделяется квота не менее 50% от общего числа финалистов.
Финальный этап традиционно состоит из двух туров. Один из них проходит по правилам ICPC-олимпиад: 8-12 задач, на решение которых отводится 5 часов. На другом туре участникам предлагается решать одну "большую" задачу в течение 5 часов. Пример такой задачи с прошлого года можно увидеть здесь. Более подробно правила и положение олимпиады можно прочитать здесь.
Отборочный тур состоится в воскресенье, 10 октября, в 10:00 по московскому времени. Очный тур пройдёт с 5 ноября по 8 ноября.
Регистрация в системе тестирования открыта здесь. После регистрации можно порешать пробный тур.
Мир спортивного программирования всё ещё лихорадит от коронавирусных ограничений — шутка ли, привычное время проведения интернет-тура в этом году оказалось занято финалом ICPC позапрошлого сезона! Так что мы решили поддержать общую неразбериху и в качестве эксперимента изменили формат отборочного тура. Кроме того, мы против общей тенденции по использованию трёх компьютеров.
Согласно правилам олимпиады, каждая команда может использовать только один компьютер. Разрешается использовать дополнительные компьютеры только для связи с сокомандниками и для чтения условий задач.
В любой момент времени может быть только один активный компьютер, на котором вы можете писать, компилировать, запускать программы. Активный компьютер может переключаться во время тура, например чтобы следующую задачу писал другой член команды. Однако нельзя проявлять активность больше чем на одном компьютере одновременно.
Использовать интернет разрешается.
Использовать предварительно написанный код разрешается.
В этом году отборочный тур будет длиться 5 часов, но в туре будут задачи разного формата:
- Первые 6 задач обычного формата ICPC. Если решение полностью правильное, то задача засчитывается, и в рейтинг идёт одна зачётная единица.
- Последние 2 задачи оптимизационные. В каждой из них есть несколько уровней сложности, за преодоление каждого уровня даётся какое-то количество зачётных единиц.
Штрафное время по оптимизационным задачам начисляется отдельно за каждый уровень за максимальный решённый уровень — по первой посылке, которая преодолела соответствующий барьер.
Количество зачётных единиц по задачам:
| 1 | 2 | 3 | 4 | 5 | 6 | 7E | 7M | 7H | 8E | 8M | 8H | 8X |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 0.5 | 0.5 | 1 | 0.5 | 0.5 | 0.5 | 0.5 |
Опенкап отменился. Будет какое-нибудь ещё зеркало?
Нет, другого зеркала не планируется. Вам оно зачем?
Я забыл, чем обычно занимаются люди утром по воскресеньям. Но если нет, то не запаривайтесь, наша команда всё равно скорее всего хотела бы отдохнуть
Автокомментарий: текст был обновлен пользователем stgatilov (предыдущая версия, новая версия, сравнить).
Автокомментарий: текст был обновлен пользователем stgatilov (предыдущая версия, новая версия, сравнить).
Текущий рейтинг
Как задача 6 отборочного решалась?
Допустим, направление на восход луны — это ось X. Отсортируем все камни по координате Y. Можно доказать, что оптимальный ответ обязательно встретится среди пары соседних камней.
Получается, что решение — отсортировать камни по векторному произведению положения на направление луны, затем просто перебрать и проверить все пары соседей.
Дорешивание откроют?
Чтобы попасть в дорешивание, в системе nsuts выберите олимпиаду "Тренировки" (если надо, зарегистрируйтесь на неё), дальше выберите тур "Интернет-тур всесибирской 2021: дорешивание".
Вроде бы даже дорешивание оптимизационных задач работает...
Что с разбором?
Боюсь, централизованного разбора в ближайшее время не планируется.
Думаю, лучше всего просто обсуждать задачи здесь.
7 на больше чем 0.5 как решается?
Думаю, самый простой способ такой. Проигнорируем уже известные камни. Разобъём изображение на прямоугольные блоки примерно одинакового размера: 44 блока по каждому измерению. В каждом блоке определим цвет центрального пикселя (если их в блоке несколько, лучше выбрать случайный из них). Умножаем цвет каждого пикселя на площадь блока, суммируем по всем блокам, делим на площадь изображения.
Зачем во второй задаче просить вывести точный ответ, если он не влезает в 64-битный тип, и ваша система не поддерживает int128? Это просто добавляет к задаче необходимость найти в интернете хорошую реализацию int128/бигинта.
Казалось бы можно попросить ответ по модулю, и от этого задача не изменится.
Как решить 4 задачу?
Неравенство про показательную и степенную функцию можно переписать как $$$x / ln(x) <= b / ln(a)$$$. Функция $$$x / ln(x)$$$ убывает при $$$x < e$$$ и возрастает при $$$x > e$$$. Значит можно найти обе границы интервала по x бинарным поиском.
Когда есть интервал, остаётся посчитать количество дробей. Количество дробей p/q для фиксированного q считается элементарно, но надо ещё убрать сократимые дроби. Например, можно вычесть из всех дробей p/q количество несократимых дробей вида a/b для всех b, являющихся делителями q. Так получается решение за $$$O(Q \sqrt{Q})$$$.
Хмм, понятно, я во время контеста понял, что найдя точки пересечения можно легко найти ответ. В конце уже думал, что нужно использовать числ. методы. Спасибо большое!
Можно и через численные методы найти x1 и x2 при которых x^b — a^x = 0. Например x1 итерационным методом, а x2 через форумулу (-b * W_-1(-log(a)/b))/log(a), где W_-1(z) = ln(-z/ln(-z/ln(-z/ln(-z... И далее как в предложенном решении
а 2 задачу?
Идем справа налево, поддерживаем два массива — $$$A_x$$$ — максимум на отрезке $$$[i;x]$$$, $$$B_x$$$ — минимум на отрезке $$$[i;x]$$$ ($$$i$$$ — текущий индекс). При сдвиге $$$i$$$ на один влево в массивах $$$A$$$ и $$$B$$$ происходят присвоения на отрезке, и надо уметь их обрабатывать и уметь брать на каком-то отрезке сумму $$$A_j \cdot B_j$$$. Это можно делать деревом отрезков, храня в вершине три числа — сумму $$$A_j$$$, $$$B_j$$$ и сумму $$$A_j \cdot B_j$$$