There are many blogs about subtasks. After almost every round the participants discuss the subtasks and their scoring distribution. Sometimes even contest author doesn't want to see subtasks in his round, but they show up there against his opinion.

But so far people who don't like subtasks have not received a worthy answer from administration or MikeMirzayanov.

I want the administration to understand that many authoritative users are against subtasks(If it is not clear from this blog).

So I encourage everyone who reads this blog and who doesn't like subtasks to write "+" in comments. Also if you like subtasks please respect other opinions and don't dislike comments. You can just dislike this blog.

UPD I am really sorry you got so many dislikes. I can guess that this dislikes were put by bots.

UPD2 Definitely it was bots. Every comment got +9 in couple minutes.

Система лайков/дизлайков на анонсе не может правильно отобразить качество раунда.

Например, у раунда 589Div2 1300 лайков до его начала, которые люди поставили за хорошо написанный анонс, хотя это никак не влияет на качество раунда. И если этим людям не понравится раунд, они уже не смогут поставить ему дизлайк.

Также, на обычных раундах лайков намного меньше, чем на 589Div2:

• 583Div1+Div2 — 224 лайка

• 576Div1+Div2 — 192 лайка

• 562Div1+Div2 — 340 лайков

• 581Div2 — 353 лайка

Мои предложения по улучшению системы оценки:

1. Открывать возможность оценки раунда только после его окончания.

2. Сделать вес голоса участника пропорциональным его рейтингу — большинство участников раунда решают AB и не могут оценить раунд полностью. В раунде 589Div2 крайне неприятная последняя задача, которая портит раунд, но многие участники до нее не дойдут.

3. Не учитывать голоса участников, у которых изменение рейтинга по модулю было больше определенной константы(например, 80)

Вчера вечером Ибрагим blyat Мамилов написал свой юмористический блог под названием "I AM GREEN ON CODECHEF (Я ИНДУС НА CODECHEF)", и дал право редактировать его моему другу Юрию tryhard Пустовалову.

Спустя некоторое время, как это часто бывает, блог удалили, а Ибрагиму дали read-only.

Юрий вечером с удивлением заметил, что он может заново опубликовать удаленный пост, что он и сделал, так как считал, что он был удален несправедливо.

Очевидно, что возможности соавторам заново публиковать удаленные блоги не должно быть — это баг codeforces.

Сегодня утром tryhard, попытавшись зайти на codeforces, обнаружил, что его аккаунт заблокировала администрация:

То есть, по факту, аккаунт Юрия заблокировали из-за бага codeforces!

UPD1 Друзья Юры создали петицию адресованную лично MikeMirzayanov с требованием немедленной разблокировки аккаунта tryhard на codeforces (ссылка на петицию)

Сегодня я бы хотел обсудить тему цензуры.

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

На текущий момент причиной выдачи read-only, согласно администрации Codeforces, могут быть такие комментарии:

1. мусорные
2. оскорбительные
3. нарушающие иные общепринятые этические нормы цивилизованного общения

В данный момент это правило не соблюдается. Например, мой популярный блог под названием "Проблема зеленых индусов в сообществе codeforces" был удален. Я считаю, что он не был мусорным, так как набрал +52 и не был оскорбительным — с первого предложения становилось понятно, что блог юмористический.

Также был удален мой комментарий к анонсу раунда 568, в котором я отметил, что авторы раунда имеют недостаточно высокий рейтинг для его проведения. Этот комментарий не нарушал перечисленных правил, но, видимо, не понравился лично MikeMirzayanov, ведь раунд был составлен под его руководством. В итоге, качество раунда соответствовало рейтингу авторов.

При этом половина комментариев к раундам до их начала совершенно бессмысленны, но их не удаляют и их авторам не дают read-only.

Цензура порождает множество фейковых аккаунтов для написания комметариев, на которых не страшно получить read-only.

Прошу MikeMirzayanov обьяснить по каким принципам сейчас выдают read-only.

В последнее время люди с рейтингом 1900-2100 могут писать раунды обоих дивизионов. Я, как участник многих div1 раундов, считаю, что задачи на этих раундах слишком сложны для людей с рейтингом <2100. Мне, например, чтобы сохранять свой рейтинг приходиться упражняться в скорости сдачи первой задачи (обычно это занимает около 10 минут). После 10 минут раунда я отправляюсь думать над следующими задачами, но, к сожалению, обычно мне не удается придумать ни одной задачи. Таким образом, контест идет для меня всего 10 минут.

Я верю, что не только у меня возникает такая проблема, поэтому предлагаю поднять границу div1 до 2100.

1106A - Lunar New Year and Cross Counting

Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.

Асимптотика O(n²)

Код:49284766

1106B - Lunar New Year and Food Ordering

Заметим, что каждый человек получит либо d_j блюд типа t_j, либо r_tj блюд типа t_j и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.

Асимптотика

Код:49285005

1106C - Lunar New Year and Number Division

Для начала заметим, что в каждой группе должно быть ровно два элемента, так как (a + b)² > a² + b² для положительных a и b

Покажем, что a_i и b_i должны стоять на "противоположных" позициях в отсортированном массиве, так как

То есть нам надо минимизировать третье слагаемое. Теперь такой выбор a_i и b_i следует из транснеравенства (доказательтво).

Асимптотика

Код:49285168

1106D - Lunar New Year and a Wander

Допустим, мы знаем префикс ответа длины i. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером.

Это можно сделать используя bfs с приоритетной очередью.

Асимптотика

Код:49285447

1106E - Lunar New Year and Red Envelopes

Задача решается методом динамического программирования. Обозначим за dp[i][j] минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени i и Алиса уже отвлекла его j раз.

Тогда из dp[i][j] можно перейти в dp[i + 1][j + 1] (если Алиса отвлекает его на i-том ходе) и в dp[d_choice + 1][j], где d_choice — d конверта, который выберет Боб.

Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию w. Тогда мы сможем узнавать выбор Боба на каждой итерации за .

Асимптотика

Код:49285694

1106F - Lunar New Year and a Recursive Sequence

Допустим f_k = x и f_i = x^y_i. По малой теореме Ферма . Значит мы можем считать y_i по модулю p - 1. Найдем y_n с помощью возведения матрицы в степень.

Причем

Тогда

После того, как мы нашли y_n используя бинарное возведение матрицы в степень, нам надо решить

Заметим, что число 3 является первообразным корнем числа 998244353 (степени тройки имеют все возможные остатки по модулю p)

Значит для какого-либо k выполняется

Из этого следует что для такого k верно и а значит и

Найдем k, которое подходит под эти свойства.

Обозначим за inv(i) элемент, обратный i по модулю p.

Число k представимо в виде k = f * d + s, где f > s. Возьмем число f примерно равное и будем перебирать d. Для каждого d необходимо проверить, существует ли подходящее s. Для этого мы предподсчитаем остатки от деления всех степеней от 0 до f - 1 числа 3^y_n на p.

Преобразуем

Теперь чтобы проверить, что для данного d есть подходящее s надо просто посмотреть, был ли у какой-то степени s числа 3^y_n такой остаток от деления на p, и если был, то найти такое s. Тогда k = f * d + s, a .

Если же после всех итераций по d такого k не нашлось, то ответ —  - 1

Код:49321335