opukittpceno_hhr's blog

By opukittpceno_hhr, history, 2 weeks ago, In Russian,

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

By opukittpceno_hhr, history, 2 months ago, In Russian,

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +72
  • Vote: I do not like it

By opukittpceno_hhr, 2 months ago, In Russian,

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

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

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +212
  • Vote: I do not like it

By opukittpceno_hhr, history, 3 months ago, In Russian,

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By opukittpceno_hhr, history, 8 months ago, In Russian,

1106A - Лунный новый год и подсчет крестов

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

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

Код:49284766

1106B - Лунный новый год и заказ еды

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

Асимптотика

Код:49285005

1106C - Лунный новый год и разделение чисел

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

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

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

Асимптотика

Код:49285168

1106D - Лунный новый год и прогулка

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

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

Асимптотика

Код:49285447

1106E - Лунный новый год и красные конверты

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

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

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

Асимптотика

Код:49285694

1106F - Лунный новый год и рекурсивная последовательность

Допустим fk = x и fi = xyi. По малой теореме Ферма . Значит мы можем считать yi по модулю p - 1. Найдем yn с помощью возведения матрицы в степень.

Причем

Тогда

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

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

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

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

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

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

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

Преобразуем

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

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

Код:49321335

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it