Предисловие

За последнее время было предложено достаточно много различных способов, методов и советов по борьбе с читерами, которые отчасти могут дать положительные результаты на короткой дистанции, но на перспективе ситуация может перейти в другую плоскость, в которой читеры станут только умнее и найдут нужные "ключи" к тому, чтобы продолжить быть безнаказанными на этой платформе.

Почему основные идеи не работают в долгосрочной перспективе

Анти-плагиат и тайминги

Быстрый код от LLM выглядит "человечески" за счёт стандартизации стиля кода, заготовок кода функций, использования сокращенных названий переменных и т.д., а адекватные задержки между отправками довольно легко эмитировать, контролируя время отправки других участников.

SMS-верификация

Онлайн-сервисы одноразовых номеров, аренда дополнительных внутренних номеров у операторов связи сводят её к формальности. Поймите, что, кто заходит на CodeForces или хотя бы имеет немного желания в чём-то разобраться, точно догадается, что уже давно на рынке практикуются онлайн-сервисы для одноразовых смс-активаций или верификации по звонку при необходимости. Стоит это сущие копейки, можно арендовать номер на N-ый период времени или даже в том же МегаФоне (кто из России, тот возможно понимает) выпустить дополнительные номера на родную сим карту за какие-то 2 рубля в сутки. Такая система защиты по номеру телефона не будет на текущий момент совершенной и точно не сдержит нарушителя.

Жёсткий бан

Пользователь, потеряв рейтинг на начале его пути, просто создаст новый аккаунт и вся история начнётся заново, а те, кто этим промышляют уже давно и имеют высокий рейтинг, уже в курсе о ключевых моментах, на которые стоит обращать внимание, чтобы не отправиться в бан.

Основная идея — не банить, а скрывать!

Идея про введение системы репортов ранее уже выдвигалась, но я хочу её форсировать. Давайте введём систему отложенных репортов и лайков от доверенных пользователей (>2000 elo), благодаря которым будет коррелироваться траст фактор условного подозреваемого. Мы не будем банить пользователя за то, что он проявил подозрительную активность в каком-то из раундов. Какой смысл нам это делать, заставлять думать, на какой задаче и в чём именно он "прокололся", когда можно просто заставить его верить в то, что он в очередной раз не попался в руки правосудия и ему удалось всех обмануть. В то же время его аккаунт будет скрыто помечаться так называемой меткой и все последующие соревнования в его лице будут проходить отдельно от общего пула участников, но при этом читер продолжит видеть "свой" рейтинг и место в общем топе. Его очки не будут учитываться в основной таблице при подсчёте позиций и рейтинга честных участников. Аномальные участники будут перемещаться в "скрытый пул", в котором будут соревноваться только между собой.

Система доверенных репортов

Кто сможет репортить?

• Участники с рейтингом более 2000 очков

• Пользователи с высоким уровнем вклада в сообщество платформы

• Доверенные участники и координаторы

Форма репорта

1. Подозрение в использовании ИИ? [Да/Нет]
2. Ключевые аномалии (тайминги, стиль кода, нетипичное решение)
3. Краткий комментарий

Взвешивание репортов

Репортящий получает "вес", который будет зависеть от его текущего рейтинга, даты регистрации, вклада, точности прошлых репортов и чем выше будут его показатели, тем больше уровень доверия. Соответственно репорты на участников с высоким уровнем доверия не будут сильно влиять на их репутацию, если их не репортят точно такие же участники.

Система лайков и репутации

1. Лайки могут ставить абсолютно любые участники с рейтингом и регистрацией не менее 7-ми дней, после окончания раунда.
2. Оценка по понятности и читаемости кода, наличии комментариев и их полноте

Механика скрытого пула

flowchart LR
  A[Участник] --> B[Соревнование]
  B --> C{Сбор данных}
  C --> D[Trusted Reports]
  C --> E[Лайки/Дизлайки]
  C --> F[Телеметрия]
  D & E & F --> G[Байес. модель]
  G --> H{TF ≥ 0.5?}
  H -- Да --> I[Скрытый пул]
  H -- Нет --> J[Основной пул]
  I --> K[Визуализация (только для читера)]
  J --> L[Реальные результаты]

1. До контеста собираются репорты и исторические данные
2. Во время контеста проводим телеметрию: время разработки, частота отправок программ, навигация по страницам
3. После байесовский движок, работающий на базе вероятностей, отталкиваясь от критериев, принимает окончательное решение о выборе пула

UI/UX для "скрытых" и "честных"

• Честный участник видит привычный топ и не замечает скрытых "признаков"

• Скрытый участник видит фейковые рейтинг и место в общем топе

• Модераторы видят график траст фактора в динамике, карточки подозреваемых с подробным логом телеметрии

Система автоматического расчёта траст фактора

Траст фактор будет повышаться или понижаться после каждого завершенного контеста по итогу рассчитанной репутации за отведённый промежуток времени или повышаться в результате ручной проверки модератора.

Как вам идея? Пишите в комментариях, что думаете.

Теоретическая база

Если вы давно решаете задачи Div1-Div2 на Codeforces, то наверняка уже слышали про дерево отрезков. Звучит возможно для кого-то страшно и не понятно, но на деле это очень полезная структура данных. Проще говоря, дерево отрезков — это такое бинарное дерево, в узлах которого хранятся агрегированные данные о каком-то отрезке массива. За счёт этой древовидной структуры мы можем быстро отвечать на запросы о произвольных сегментах массива да и не только отвечать, но и обновлять элементы.

Представьте, что у нас есть массив, и требуется многократно узнавать что-то про подотрезки этого массива, например, сумму элементов, минимум, максимум, количество каких-то значений и т.д. Дерево отрезков позволяет делать такие запросы очень быстро — обычно за O(log n) на каждый запрос вместо тривиального O(n) перебора. При этом оно достаточно гибкое, поддерживает изменение отдельных элементов, а с дополнительными трюками (ленивые пропагации) может даже массово обновлять целые диапазоны за то же логарифмическое время​. В общем, дерево отрезков может довольно хорошо оптимизировать алгоритм программы, когда обычных массивов и сортировок уже не хватает.

Пример дерева отрезков, построенного для массива arr = {1, 3, 5, 7, 9, 11}. Каждый узел хранит сумму на соответствующем отрезке: корень содержит 36 (сумма на всём отрезке [0;5]), его дети – суммы на [0;2] и [3;5] (9 и 27) и так далее.

Как это работает?

Мы рекурсивно делим массив пополам, пока не дойдём до отдельных элементов. Эти элементы — листья дерева. Затем начинаем “склеивать” информацию снизу вверх: каждый внутренний узел вычисляется из двух дочерних. Например, если нам нужны суммы, то значение узла = сумма левого сына + сумма правого сына. Если нужны минимумы — берём минимум из двух детей, и т.д. В итоге корень хранит агрегат (сумму/мин/макс и пр.) по всему массиву, а путь от корня к листу соответствует делению отрезка на подотрезки.

Когда это нужно?

Дерево отрезков может быть использовано, когда:

1. Нужно эффективно отвечать на запросы о подмножествах элементов массива (сумма на отрезке, максимум на отрезке, НОД на отрезке и т.п.) и при этом между запросами могут происходить изменения отдельных элементов или целых диапазонов, то есть данные динамические. В таком случае простое предвычисление всех ответов не поможет
2. Запросов и обновлений много (десятки и сотни тысяч) и делать их за линейное время слишком долго

Дерево отрезков обеспечивает (log n) на один запрос или обновление, что обычно укладывается в лимиты при n и количестве запросов порядка 10^5. При этом его память ~4*n элементов для массива размера n — тоже вполне ок.

Примеры задач, решаемых деревом отрезков

Диапазонные суммы, поиск минимума/максимума на отрезке, количество определённых элементов на отрезке, проверка упорядоченности сегмента, даже поиск k-го по счёту элемента. Например, с помощью дерева отрезков можно легко узнать, сколько нулей в заданном диапазоне или найти индекс k-го нуля в массиве​. Кстати, именно такую задачу мы сейчас рассмотрим на практике.

Практическая часть

Давайте на примере рассмотрим задачу 2075F - Красивая последовательность возвращается с недавнего контеста Educational Codeforces Round 176 (Rated for Div. 2), решив её при помощи дерева отрезков и проведём аналогию в сравнении с решением "в лоб".

Рассмотрим решение данной задачи от wishgoodluck — 311252841. Идея данного алгоритма основана на «событийном подходе». Мы предварительно вычисляем два массива (назовём их l и r), которые фиксируют важные границы в исходной последовательности. Эти массивы помогают определить, для каких отрезков происходит «изменение» (увеличение или уменьшение вклада в итоговый ответ). Затем формируется вектор событий — каждый элемент этого вектора задаёт, что на определённом отрезке надо добавить или убрать некоторое значение. В финале итоговая длина искомой последовательности получается как максимальное суммарное изменение.

Ключевая задача заключается в том, чтобы быстро и эффективно обрабатывать множество событий, которые влияют на диапазоны индексов. Именно для этого и используется дерево отрезков.

В данном решении дерево отрезков применяется для двух операций:

• Диапазонное обновление (Range Update). Каждое событие из вектора v задаёт, что на отрезке [l,r] нужно прибавить либо +1, либо -1. Дерево отрезков с ленивыми обновлениями позволяет за O(log n) за одно событие обновить сразу весь отрезок, не проходясь по каждому элементу отдельно.
• Запрос максимума (Range Query). После каждого обновления нам нужно быстро узнать, каково максимальное значение на всём диапазоне. Корень дерева (Tree[1].v) всегда хранит максимум среди всех элементов. Это позволяет мгновенно (за O(1) после O(log n) обновлений) узнать текущее оптимальное значение, которое потом используется для вычисления ответа.

Таким образом, дерево отрезков здесь выступает как «агрегатор» всех событий, аккумулируя их влияние на заданных отрезках и позволяя быстро находить максимум.

Представьте себе задачу, где нужно на каждом шаге для каждого события обновить все элементы отрезка. Если диапазон имеет длину m, то наивное обновление занимает O(m) операций. При m∼n и O(n) событиях получаем O(n^2) операций. Это решение быстро станет неприемлемым по времени даже для средних размеров входных данных.

В отличие от этого, дерево отрезков позволяет обновлять целые диапазоны за O(log n) благодаря ленивой пропагации. Таким образом, даже если событий много, общая сложность становится O(n*log n).

Подводные камни и советы

Дерево отрезков — штука мощная, но при реализации можно допустить несколько типовых ошибок:

• Неправильное слияние результатов. Забудете, что нужно суммировать детей, или перепутаете левый/правый и вся логика разрушится. Внимательно определяйте, что хранит узел, и как это получается из информации детей.
• Границы отрезков. Легко ошибиться с индексами left, right и middle. Условились, что сегмент [left..right] включительный. Тогда middle = (left+right)/2 – левая часть [left..middle], правая [middle+1..right]. Если забудете +1 где нужно – получите перекрывающиеся или пропущенные индексы. Совет: отладьте на маленьком массиве, например, n=4 и выпишите на бумажке сегменты каждого узла, проверьте, что покрывают массив без пробелов и наложений.
• Рекурсия vs итерация. Мы рассмотрели рекурсивное решение для простоты понимания, но при n ~ 10^5 глубина рекурсии ~17 – это ок, а вот если бы n ~ 10^7, глубина ~24, всё ещё ок. При сильно больших n и особенно при большом количестве операций иногда предпочитают итеративные реализации во избежание накладных расходов и риска переполнения стека.
• Ленивые обновления. В нашем примере мы как раз их использовали, обновляя сразу целый диапазон. Обратите внимание, что реализация ленивых тегов сложнее — легко напутать с распространением изменений на детей. Если задача требует дерево отрезков с lazy, тестируйте на более простых примерах. Типичные ошибки: забыли запушить лейзи-тег перед дальнейшим спуском или перед подсчётом в узле — получите некорректные данные. Совет: написать отдельную функцию push(v) для распространения тега из узла v на детей, и вызывать где нужно, например перед переходом в поддеревья.
• Выбор между Fenwick (BIT) и деревом отрезков. Часто они взаимозаменяемы для простых задач на суммы, порядковую статистику. Fenwick легче кодится и требует памяти, но дерево отрезков более универсально, поддерживает сложные операций слияния. Если задача допускает Fenwick и вы не хотите тратить время на реализацию дерева — дерзайте с Fenwick, однако дерево отрезков must know для Div1-Div2 уровня.

Напоследок дам небольшой лайфхак — если задача просто требует многократных запросов суммы на отрезке без обновлений, то и дерево отрезков не нужно, достаточно просто будет заранее посчитать префиксные суммы за O(n) и потом каждый запрос обрабатывать за O(1).

Спасибо тем, кто дошёл до конца, удачного программирования :)

Предлагайте в комментариях, о чём мне ещё написать в следующем посту и какие темы ещё стоит изучить.

Анекдот 1^n

На соревновании Codeforces участник отправляет каждую задачу с первой попытки, даже не читая условия. Его спрашивают:

– Как ты это делаешь?! Даже условия задач не читаешь!

Он отвечает:

– А я уже давно задачи не читаю, сразу в ChatGPT отправляю.

– А если GPT ошибётся?

– Ну, тогда будет два виноватых: я и нейросеть.

Анекдот sqrt(4)

Приходит как-то больной к врачу после завершения сложного раунда на Codeforces, на котором он занял первое место, решив все задачи за 1 час.

Врач:

– Здравствуйте, на что жалуетесь?

Больной молчит и что-то быстро печатает на телефоне.

Врач (удивлённо повторяет):

– Молодой человек, так на что жалуетесь-то?

Участник (читает с телефона):

– Здравствуйте, доктор. У меня наблюдается повышенная латентность ответа, сложности с когнитивной функцией, периодически возникает необходимость уточнять детали входных данных...

Врач недоумевает:

– А вы можете по-человечески объяснить?

Участник снова печатает и зачитывает:

– Простите, я не совсем вас понял, могли бы вы переформулировать свой вопрос?

Врач:

– Вы что, не можете без этого ChatGPT говорить совсем?!

Участник смотрит в телефон и читает:

– К сожалению, я — языковая модель и не могу посещать врачей лично.

Врач:

– Ясно, у вас серьёзный случай...

Пишет в диагнозе: «Хроническая нейросетевая зависимость. Рекомендуется срочная блокировка аккаунта на Codeforces».

Задача B. «GPT-помощник»

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Ввод: стандартный ввод

Вывод: стандартный вывод

Вася активно использует ChatGPT во время соревнований на Codeforces и это уже вошло у него в привычку. Перед каждой задачей он обязательно отправляет её условия нейросети. Если ChatGPT не справляется, Вася отправляет новый запрос: «Что делать, если ChatGPT не знает решения задачи?». Обычно после этого нейросеть даёт ему советы по самостоятельному поиску решения.

Однако сегодня Васю забанили и он больше не может принимать участия в контестах. Вася снова обратился к ChatGPT за помощью:

Вася: «Меня забанили на Codeforces за использование ИИ, что делать?»
ChatGPT: «Я не могу вам помочь с данной проблемой, обратитесь в администрацию Codeforces.»
Васе стало грустно, что впервые ИИ не помог ему с задачей.

Задача: Определите, какое количество задач Вася успел отправить, если известно, что нейросеть отказалась помочь ему ровно после того, как он отправил своё решение к пятой задаче контеста.

Входные данные

Входные данные отсутствуют.

Выходные данные

Выведите единственное целое число — номер задачи, на которой Васю подвёл ChatGPT.

Пример

Входные данные

Выходные данные

5

Примечание

Пожалуйста, не пользуйтесь нейросетями во время соревнований!

Привет всем участникам Codeforces и MikeMirzayanov!

Последнее время очень часто сталкиваюсь с обсуждениями использования AI на соревнованиях. Решил поделиться мыслями и личным опытом по этому вопросу, а также внести несколько предложений, которые могли бы помочь в обеспечении честности проведения соревнований.

В качестве эксперимента я протестировал несколько моделей ChatGPT на платной основе, чтобы понять, насколько они способны эффективно решать контестные задачи на различные алгоритмы с точки зрения правильности решений и оптимизации.

• o3-mini отлично справляется с задачами уровня div2 A–C, но, начиная с div2 D модель без явно заданной идеи решения зачастую генерирует неоптимальный код, неверно определяя оптимальную асимптотику алгоритма. Особенно заметны проблемы в задачах на динамическое программирование при составлении рекуррентной формулы и в интерактивных задачах.
• o3-mini-high показывает лучшее понимание задач, глубже рассуждает, но тоже допускает ошибки на сложных задачах div2 E–F, особенно связанных с динамическим программированием. Зачастую для получения правильного и оптимального решения приходится вручную описывать модельный алгоритм с указанием точной формулы и асимптотики.

На своём опыте, разумеется, в исключительно экспериментальных и научных целях заметил одну интересную вещь — ChatGPT в стандартных условиях без подробных объяснений алгоритма обычно генерирует однотипный паттерн кода, содержащий примерно одинаковую структуру функций и их названия, схожий стиль переменных и повторяющиеся комментарии, частое использование одних и тех же заготовок и шаблонов, особенно для типовых алгоритмов. Да, безусловно обычный пользователь может написать подобный алгоритм, но будет явное отличие от ИИ в оформлении и структуре кода.

Именно это, на мой взгляд, можно использовать как один из уровней защиты для автоматической модерации решений на платформе. Уже сейчас модерация на Codeforces иногда успешно обнаруживает подозрительно похожие решения именно по такому признаку. Но это на самом деле контрится сейчас очень легко путём обфускации кода, добавления "мусорных" и не нужных функций, из-за чего в конечном итоге код будет сложно прочесть. На этот счёт можно продумать ещё несколько уровней защиты, которые будут работать параллельно с основным.

Основная идея заключается в поведенческом анализе действий пользователя в реалтайме. Можно внедрить следующий функционал:

1. Анализ в реальном времени разницы между моментом открытия условия задачи и первой отправкой решения
2. Отслеживание резких изменений в скорости решения задач, например, слишком быстрое решение сложной задачи после долгого простоя без активности
3. Фиксация абсолютно всех действий пользователя на странице контеста с пакетной отправкой зашифрованных данных на сервер для модуля антифрода, без которого дальнейшее действие на сайте будет невозможно, будем учитывать особо внимательно события копирования условия задачи со страницы

Отдельным и ключевым решением будет реализация клиентского приложения Client <-> Server. Основной его задачей будет мониторинг подозрительных действий. Чем-то его логика будет схожа с работой проктора при проведении, например, онлайн-экзамена.

1. Анализ процессов, запущенных во время контеста
2. Анализ входящего/исходящего траффика для контроля запросов к ИИ-сервисам
3. Создание и отправка на сервер случайных скриншотов экрана пользователя только при подозрительной активности

Конечно, с точки зрения конфиденциальности, такое решение будет не очень верным, поэтому стоит ещё подумать, как правильно его можно реализовать.

Пишите в комментариях ваши мысли и идеи, будет интересно послушать!