Привет, Codeforces!

Помните этот пост?

Если нет, кратко напомню. Последние 3–4 дня я делаю расширение для Codeforces, которое показывает ваше чистое место в standings без подозрительных участников.

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

Идея довольно простая:

1. Расширение берёт standings соревнования на Codeforces.
2. Проходит по каждому handle.
3. Делает предсказание с помощью ML-модели, используя историю выступлений пользователя в предыдущих соревнованиях.

Среди признаков: наличие skipped contests, резкие rating deltas вроде +100 или +200 после более стабильных изменений типа +10/+20, поведение рейтинга после первых 5 соревнований, когда он становится более устойчивым, и другие признаки.

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

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

Примеры использования

Покажу несколько примеров:

Возьмём пользователя с высоким score. Чем выше score, тем увереннее модель. Например: studyyyzz.

Посмотрим его профиль:

Можно подумать, что модель находит только очевидные случаи. Поэтому возьмём пользователя с более низким score, например HubRis504.

Как видно, расширение уже работает достаточно неплохо.

FAQ

• Как установить расширение?
  Инструкция по установке есть в этом посте.

• Модель всегда права?
  Нет. Это ML-модель, а ML-модели не могут предсказывать со 100% точностью. Пожалуйста, не обвиняйте людей только потому, что модель пометила их как подозрительных.

• Можно ли улучшить расширение?
  Да, конечно. Проект open-source. Вы можете посмотреть реализацию и предложить улучшения здесь: тык

Хотели ли бы вы видеть свое место без читеров?

Я задался этим вопросом, поэтому создал Besterds — расширение для Codeforces, которое позволяет видеть ваше место без читеров.

Как установить?

1. Заходите по ссылке GitHub: https://github.com/nileqq/besterds

2. Закидываете звезду, а дальше скачиваете: нажимаем Code => Download ZIP

3. Распаковка ZIP-файла

4. Запускаете сервер: python -m src.app.backend.server

5. Заходите в Google/Firefox:

• Для Google: chrome://extensions => Load unpacked => выбери папку ..\besterds\src\app\dist\chrome

• Для Firefox: about:debugging#/runtime/this-firefox => Load Temporary Add-on => ..\besterds\src\app\dist\firefox\manifest.json

❗ Besterds — ML-модель (бинарный классификатор), а значит он может допускать ошибки. Советую не доверять ему полностью и не обвинять человека в том то что он читер, когда расширение показало, что он cheated.

И да, расширение прям очень сырое пока, и не делает то что я хочу, но будет полезно я думаю. Кстати, скоро соревнование. Будете участвовать?

Привет, codeforces!

Я начинаю свой путь по спортивному программированию до 1600 рейтинга. В период этого времени я не буду участвовать в любых соревнованиях, только теория и практика. Ежедневно я буду выкладывать свой прогресс сюда — что изучил, что знал до этого, поэтому если интересно следите.

(P.S Если вы опытнее меня в спортивном программировании — буду рад любой помощи, совету или рекомендации. Можете подсказать интересные задачи, что можно изменить в плане по изучению и так далее. Ваш опыт для меня очень важен, особенно в начале пути.)

Также не забудьте посмотреть прогресс моего друга autaons!

План по изучению

2-я неделя:

- 2 дня: подтянуть базовые техники: 
    • бинарный поиск по ответу
    • два указателя
    • хэш-таблицы
    • повторить C++

3-я неделя:

- 1-2 дня: работа с мышлением 
    • Комбинаторика
    • Решение и разбор задач с нетривиальными идеями (можете посоветовать?)
- 2-6 дней: рекурсия, динамическое программирование и обратный ход
    • Рекурсия и подобные алгоритмы 
    • Обратный ход
    • Динамическое программирование
- 7 день: повторение

4-я неделя:

В процессе..

Неделя #1

Суббота: повторил двоичный поиск по ответу, два указателя (sliding window) и различные техники.

- Список решенных задач (23): Sphere Online Judge (AGGRCOW, задача о дровосеке), codeforces (Наидлиннейший k-хороший подотрезок, сотовая связь..) и Leetcode (типовые задачи на два указателя)
- В процессе изучения: комбинаторика (Формула размещения и сочетания; Выводил формулы сам на основе задач о шарах); 
- Разбор задачи Div2B - [Gellyfish and Baby's Breath](https://codeforces.me/problemset/problem/2116/B?locale=en)

Неделя #2

Перед началом этого поста хотелось бы сказать: да-да, я знаю, что я обещал обновлять пост ежедневно, но кто из нас не человек? Надеюсь вы меня простите =).

Что ж.. с чего начать? За эту неделю произошло довольно многое.. во-первых, я не совсем следовал плану, который я написал выше. Прежде всего я работал над мышлением, то есть над моими problem solving issue и statement reading issue. Из этого всего я выделил несколько паттернов, которые часто встречаются в задачах:

- Сначала читай входные и выходные данные, быстро пробегаясь по сюжету, так как часто в задачах вся информация там сжатая (попробуйте потренироваться и вы увидите насколько я прав (не всегда)). 
- При чтении условии задумывайся о каждой детали, которое может подтолкнуть к решению. Оно странное? Возможно, это и есть тот ключ!
- Записывайте частые паттерны. Например, лично я завел специальный файл, где описываю паттерны, что я заметил и насколько я был близок. 
- Разбирал абсолютно весь Div2-контест. Причем, не просто: "я понял, пойду дальше..", а думал как на самом соревновании я мог прийти к этому. Может, надо было посмотреть повнимательнее на формулу или перебрать числа и заметить закономерность. 
- НИКОГДА НЕ СМОТРЕЛ КОД ИЗ EDITORIAL!! Возможно, прозвучит странно, но я всегда стараюсь написать сам. Даже когда есть мощнейшее желание посмотреть решение автора я понимаю, что для моего развития это плохо.

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

↓ Если вам интересно, как всё пойдёт (как и мне), не забудьте поставить лайк!