В своём предыдущем посте я рассказал, что знаю, как работает Flash-компонент Codeforces для показа решений во время контеста, и собираюсь рассказать другим. Не для того, чтобы эту информацию использовали для нарушения правил, а чтобы в контестах можно было участвовать наравне со всеми без Flash. Реакция со стороны администрации была весьма болезненной — как будто я собираюсь сломать Codeforces, то есть сделать так, чтобы он не мог нормально работать. Я не согласен с подобной оценкой. Более того, я сомневаюсь, что те усилия, которые прикладывает Codeforces для защиты кода решений от копирования, вообще оправданы.

Я считаю, что когда MikeMirzayanov придумывал систему защиты от копирования кода (или оценивал, если эту систему придумал кто-то другой), он совершил две ошибки. Первая из них чисто техническая: он решил, что то, что алгоритм шифрования реализован с помощью Flash, само по себе является серьёзным препятствием для реверс-инжиниринга. Никакой другой защиты там нет: алгоритм очень простой, код легко читается, а для расшифровки не нужно даже знать ключ. Как я уже писал, это не работает — декомпиляторы для Flash легко находятся в Google. Так что почти никакой реальной защиты и не было, только видимость защиты.

Вторая ошибка скорее стратегическая: в попытке сделать систему максимально защищённой MikeMirzayanov решил пожертвовать удобством участников и продолжал настаивать на своём решении, даже когда участники неоднократно озвучивали своё несогласие. Ни для кого не секрет, что полностью исключить возможность читерства на соревнованиях невозможно. Особенно это касается онлайн-соревнований, где есть методы читерства, которые просто реализовать и сложно предотвратить. Например, совместное участие в личном контесте нескольких человек под одним аккаунтом. По сравнению с этим варианты читерства, которые возникают в результате возможности копировать код, не выглядят захватывающими: чтобы читать чужой код, необходимо уже иметь своё решение, которое проходит претесты, а значит, идею решения всё равно нужно придумать самому (да и, чтобы понять идею чужого решения, не нужно его никуда копировать — достаточно его прочитать). А чтобы использовать скопированный код чужого решения для взломов, нужно не только уметь его запускать, но и иметь нетривиальные тесты — ведь это решение уже прошло претесты. В общем, нужно достаточно много возни, а в результате на одних взломах всё равно далеко не уедешь.

При планировании системы защиты стоит предполагать, что большинство участников не будут пытаться нарушить правила, по крайней мере, преднамеренно. Потому что если это не так, то у сообщества серьёзные проблемы, которые не решить техническими средствами. Так что большинство участников вообще не будет пытаться скопировать текст решений, некоторые могут попробовать просто его выделить и скопировать (возможно, не зная, что это против правил — кто же их читает?), отдельные участники могут попробовать влезть в инструменты разработчика. Но если кто-то дошёл до того, чтобы вытаскивать текст, рисуемый на canvas-е, то у меня для вас плохие новости: он действительно хочет скопировать код, и он его скопирует. Потому что аналоговая дыра остаётся всегда, OCR — это не rocket science, а склеить изображение всего кода из видео его прокрутки — если подумать, то не такая уж и сложная задача.

Исходя из вышесказанного, я считаю, что нынешняя система на основе Flash в целом не приносит пользу. Да, она может не дать небольшому количеству участников считерить, но для большинства она создаёт неудобства. Целевой аудиторией Codeforces являются честные участники, так что о них нужно думать в первую очередь. В этом плане показателен пример TopCoder: их браузерная арена не использует Flash, и код оттуда извлекается вводом одной строчки в консоль. Их Java-арена вообще передаёт код открытым текстом — бери и копируй. И при всём при этом у них, судя по всему, нет серьёзных проблем с читерами (иначе бы они что-нибудь изменили). Лично мне их подход нравится намного больше.

Всем привет. Я решил ещё раз поднять тему Flash Player в контексте его использования на Codeforces для взломов.

Эту тему уже поднимали неоднократно, давно и не очень. Все ответы администрации сводились к двум утверждениям: что Flash работает и что систему, основанную на Flash, трудно обойти. Оба эти утверждения ‒ ложь.

В последнее время я несколько раз пытался смотреть код других участников во время контеста, и у меня не разу не получилось. Каждый раз показывалось что-то такое. При этом я использовал последнюю версию Flash. При этом процесс plugin-container, в котором работает Flash, падал с необработанным исключением (SIGSEGV). Это то, что может произойти, если, например, решение задачи на C++ выходит за границы массива. Видимо, Flash Player по качеству кода недалеко ушёл от таких решений.

При таком качестве кода не удивительно, что у Flash плохо с безопасностью. MikeMirzayanov, конечно, скажет, что уязвимости есть не только в Flash. Но если в Chrome или Firefox найдут уязвимость, которая будет активно эксплуатироваться, то Google и Mozilla выпустят обновление как можно быстрее, а Adobe (как и Microsoft) будут ждать до следующего планируемого выпуска патчей (патчи выпускаются во второй вторник каждого месяца). Кроме того, использование Flash добавляет все его уязвимости к тем, что уже есть в браузере (это одна из причин, по которой браузеры отказываются от поддержки вообще всех плагинов, а не только Flash).

В общем, как я уже написал, Flash небезопасен. Flash не работает ‒ по крайней мере, под Linux. Из-за лицензионных ограничений, Flash под Linux нельзя скачать из репозитория, нужно качать и ставить обновления вручную (но это не важно, так как он всё равно не работает). Можно, конечно, специально для взломов использовать виртуальную машину с Windows (там Flash работает), но это неудобно. Я считаю, что необходимость в подобных действиях для полноценного участия в контестах ‒ свинство со стороны администрации.

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

И наконец: MikeMirzayanov почему-то считает, что новички для того, чтобы нарушить правила, с лёгкостью установят Firebug, но при этом не додумаются установить декомпилятор для Flash. Так вот: декомпиляторы для Flash существуют, их легко найти, и первый же найденный декомпилятор легко декомпилирует Flash-файлы с Codeforces. И я удивлюсь, если ещё никто ни разу не копировал чужой код через функцию взлома. Впрочем, если это и так, то это скорей говорит о честности участников.

Теперь к главному. Я изучил, как работают Flash-файлы с Codeforces и, в частности, как они расшифровывают решения. Я собираюсь выложить эту информацию, чтобы показать, что «защита» на основе Flash не имеет преимуществ перед «защитой» на основе Javascript, и таким образом подтолкнуть администрацию к тому, чтобы отказаться от Flash. Также я сделал расширение для Chrome и Firefox, которое позволяет читать код без Flash. Его я тоже собираюсь выложить. Так или иначе, я избавлю себя и других участников от необходимости держать Flash ради Codeforces. Других сайтов, где без Flash что-то не работает, я не встречал уже давно.

UPD Продолжение: Почему Codeforces не нужен Flash.

Hi all!

There are two changes that Code Jam team have just announced.

The first change is that it is now possible to upsolve this year's problems. To do this, you need to be logged in. Open any past problem and press the "switch to practice mode" button at the top right. Practice mode will be available 24/7 except during official Code Jam rounds. There is also a site-wide limit of 10 submits within any 10 minute window.

The second change is that it is now possible to view and download other participant's code after the contest. To do this, click on the participant's nick in the scoreboard.

Hi all!

Soon thousands of people will participate in Google Code Jam qualification round. There is a problem though: Code Jam website doesn't offer a good place to discuss the problems afterwards. There is an official Google group, but it is a poor place for discussion: not only is it premoderated, but they also reject/delete useful posts, like this one.

There is a solution: point people at Codeforces, the best place to discuss programming competitions! If we just start posting messages about Codeforces to the Google group, they will probably delete them. But there is something else that people (sometimes) read: your code. For many years, Code Jam allowed anyone to read any participant's code after the contest. While the current system doesn't support this yet, this is something that Code Jam team is willing to resolve. So, my idea is for as many people as possible to add a comment like this to every Code Jam submission:

// Discuss this problem on Codeforces: http://codeforces.net/

Or better, use a link to a post about the specific round. This way, those who try to learn by looking at other's code will find out about Codeforces, which is good.

Do you have any similar ideas?

Google Code Jam 2018 qualification round will start soon and run for 27 hours. Don't miss it!

Before you start, you may have a look at an old version of the new Code Jam system. Looks like the admins have just forgotten to take it down. If this page doesn't open, you can at least look at some screenshots.

Java 10 has been released a few days ago, just six months after Java 9. In this version, I found only one new feature which is useful for competitive programming: Local-Variable Type Inferrence. It works similarly to auto keyword in C++. So now you can write something like this:

var map = new HashMap<Integer, List<String>>();
for (var entry : map.entrySet()) {
    var key = entry.getKey();
    for (var element : entry.getValue()) {
        System.out.println(key + " " + element);
    }
}

If you find any other relevant enhancements, please post them here.

Иногда в таблице результатов появляются непонятные вещи:

Причём возникает это недетерминировано и при обновлении страницы пропадает. У кого-нибудь ещё такое бывало?

A few weeks ago, I participated in Google Code Jam and Distributed Code Jam finals. Later, the finalists were asked to provide some feedback. I think that my feedback may be interesting for other people as well, so I post it here (I also posted it on Google Code Jam group).

After reading the editorial for RCC Elimination round problem E, I thought of an easier problem of merging two strings such that the result is lexicographically minimal. Formally, a merge of two strings a and b is a string s of length |a| + |b| such that there exist two strictly increasing sequences of indices i₁, i₂, ..., i_|a| and j₁, j₂, ..., j_|b| such that a = s_i1s_i2... s_i|a|, b = s_j1s_j2... s_j|b| and each index in s appears exactly once in i₁, ..., i_|a|, j₁, ..., j_|b|.

The above mentioned editorial provides an algorithm for solving this problem that works in time and uses hashes. Actually, this problem can be solved in linear time. The solution works roughly like this: maintain current position p_a in a and p_b in b. On each step, lexicographically compare the suffix of a starting at p_a with the suffix of b starting at p_b, and take a character from the suffix that is smaller (actually, for this to work, it is necessary to terminate each string with a character that is greater than any character in the strings, so that if one of the suffixes is a prefix of the other, the shorter suffix is considered larger, not smaller). The author proposes to compare the suffixes by using binary search and hashing, which takes time. However, this can be done in constant time.

Actually, this is a well known Longest Common Extension problem. One of the constant-time solutions is as follows: construct a suffix tree from the strings, then preprocess it using one of Lowest Common Ancestor algorithms that can answer LCA queries in constant time. It is easy to see that the lowest common ancestor of two leaves in a suffix tree that correspond to two suffixes can be used to find the length of the longest common prefix of those suffixes. From that, performing lexicographical comparison is easy.

It is possible to build and preprocess a suffix tree in linear time, so the overall running time is O(n), but the algorithm is quite complex. Does anyone know of a simpler algorithm with the (asymptotically) same running time?

Finally, TopCoder announced the dates of TopCoder Open 2017 Algorithm and Marathon Competitions. Since it is not trivial to find this information on their website, I will reproduce it here.

TCO17 Algorithm Competition will have a usual structure with three online rounds and two onsite rounds. The location and the dates of onsite rounds have yet to be announced, but the dates of online rounds are already known:

• Round 1A: April 1, 2017 at 16:00 UTC.
• Round 1B: April 8, 2017 at 16:00 UTC.
• Round 1C: May 6, 2017 at 16:00 UTC.
• Round 2A: May 20, 2017 at 16:00 UTC.
• Round 2B: July 8, 2017 at 16:00 UTC.
• Round 2C: July 22, 2017 at 16:00 UTC.
• Round 3A: August 5, 2017 at 16:00 UTC.
• Round 3B: September 9, 2017 at 16:00 UTC.

This year, 750 top contestants will advance from each sub-round of Round 1, 40 will advance from each sub-round of Round 2, and five from each sub-round of Round 3. Also, 250 TopCoder members with the highest rating advance to Round 2 automatically, as long as they competed in at least three rated TopCoder Algorithm rounds in total and in at least one such round between January 1 and Marth 31, 2017.

In addition to these online rounds, there will be six regional onsite rounds. To compete in any of them, it is necessary to be present at the event. These events are currently planned:

• Regional event in Austin, TX: April 29, 2017.
• Regional event in Saint Petersburg, Russia: May 7, 2017 (third year in a row).
• Regional event in Beijing, China: June 24, 2017 (second year in a row).
• Regional event in Bangalore, India: August 20, 2017.
• Regional event in Warsaw, Poland: September 2, 2017.
• Regional event in Pittsburgh, PA: September 7, 2017.

From each of these rounds, 10 top contestants will advance to a special Wildcard Round, which will be held on September 10, 2017 at 16:00 UTC. From this round, two highest-scoring contestants will advance to the onsite round. So, in total, 12 contestants will advance to TCO17 Algorithm onsite round.

In TCO17 Marathon Competition, there will be three regular online rounds plus some number of Lightning Rounds. The dates for the regular rounds are as follows:

• Round 1: from April 12, 2017 17:00 UTC to April 26, 2017 17:00 UTC.
• Round 2: from May 10, 2017 17:00 UTC to May 24, 2017 17:00 UTC.
• Round 3: from July 5, 2017 17:00 UTC to July 19, 2017 17:00 UTC.

In each regular round, top 30 contestants will be awarded points based on their place. Lightning Rounds, of which none is currently announced, will award fewer points. Top ten contestants who accumulate the most total points will advance to the onsite round.

... испытываю я после второго полуфинала TCO16.
С одной стороны, я не прошёл в финал. Это плохо.
С другой стороны, я выступил лучше, чем tourist. Это хорошо.

TopCoder Open 2016 Round 2C starts today at 17:00 UTC. Top 40 contestants will advance to Round 3. This is the last chance to advance. Those who have already advanced will be able to compete in a parallel round.

Good news for those who participate in IPSC: TopCoder has apparently decided to move this round so that it doesn't clash with it. Don't forget to register in time, registration closes five minutes before the round.

Скоро начнётся Facebook Hacker Cup 2016. Не пропустите квалификационный раунд, который начнётся в 3:00 по Москве и продлится трое суток. Чтобы пройти в следующий раунд, нужно решить хотя бы одну задачу.

В этом году финал пройдёт в Лондоне, так что это ещё один шанс для тех, кто не прошёл на финал GCJ в 2013 году.

Для участия в раунде пройдите по этой ссылке, но сначала нужно войти в Facebook.

Недавно мне, как финалисту Яндекс.Алгоритма, пришло письмо с документом, который мне предлагается подписать (английская версия). Насторожило меня уже то, как выглядит этот файл в их же собственном просмотровщике:

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

Содержимое меня, однако, опечалило. Вы там в Яндексе вообще читаете то, что предлагаете нам подписать? Или думаете, что мы, финалисты, подмахнём, не глядя? А то уже в первом пункте:

1.я ознакомлен и согласен с Положением о конкурсе «Яндекс.Алгоритм-2015», размещенным в сети интернет по адресу: algorithm.contest.yandex.ru/terms/ (далее — «Положение»)

Ну предположим, что то, что предложения обычно начинают с заглавной буквы, можно на время проигнорировать. Кому они нужны, эти правила? Больше беспокоит то, что по указанному адресу находится страница с ошибкой 404. Согласен ли я с тем, что там написано? Не уверен. Продолжим:

а также с Правилами конкурса «Яндекс.Алгоритм-2015», содержащими условия и правила проведения мероприятия – конкурса «Яндекс.Алгоритм-2014», проводимого ООО «ЯНДЕКС» (далее – Организатор) в срок с 21 апреля 2015 года по 6 августа 2015 года (далее- «Конкурс») по адресу: algorithm.contest.yandex.ru.

Даже не знаю, что более странно: то, что правила Яндекс.Алгоритма 2015 содержат правила Яндекс.Алгоритма 2014, или то, что Яндекс.Алгоритм 2014 проводится в 2015 году?

3.В случае своей победы в Конкурсе (занятия одного из призовых мест, дающих, в соответствии с правилами проведения Конкурса, право на получение приза), я получу денежный приз, предусмотренный п. 10.3. Положения, в зависимости от занятого места.

Смотрим этот пункт:

10.3. Победители обязаны предоставить Организатору Конкурса указанные в п. 10.2 Положения документы в течение 14 календарных дней после определения Организатором Победителей конкурса в порядке, предусмотренном п. 7.3 Положения.

Не очень понятно, что за денежный приз он предусматривает.

4.Я осознаю, что денежный приз мне будет выплачен в российских рублях за вычетом налога на доходы физических лиц в размере _____, исчисленного в соответствии со ст. 224 Налогового Кодекса РФ.

Это вообще что, проверка того, знаю ли я налоговое законодательство? Кстати, в англоязычной версии ставку налога вписывать не нужно. Видимо, англоязычным финалистам для участия знать налоговый кодекс РФ необязательно.

В общем, повнимательнее нужно относиться к документам.

В этом году TopCoder Open содержит, помимо финального онсайт-раунда, четыре онсайт-этапа, проводимых в разных городах мира одновременно с подраундами раунда 2. Из-за этого время проведения этих раундов становится известно позже, чем обычно. Ранее уже было объявлено время проведения раундов 2A, 2B и 2D. Наконец, пришло время и для раунда 2C.

Раунд 2C пройдёт 18 июля в Токио, в офисе компании Dwango.

Как и на остальных онсайт-этапах, будет хакатон и футболки. В отличие от остальных онсайт-этапов, будет разбор задач, его проведут iwiwi и rng_58. Мероприятия начнутся в 11:00 по местному времени, а сам раунд — в 15:00 (9:00 по московскому времени). Параллельный раунд будет как для участников онсайта, которые не прошли в раунд 2, так и для всех тех, кто уже прошёл в раунд 3. Если вы собираетесь участвовать в онсайт-этапе, не забудьте зарегистрироваться — сделать это смогут всего 100 участников.

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

TopCoder объявил время проведения раундов 2B и 2D TopCoder Open 2015, а также место проведения соответствующих онсайт-этапов. Раунд 2B пройдёт 20 июня в Сан-Франциско, в штаб-квартире MemSQL.

Мероприятия начинаются в 10:00 по местному времени, а сам раунд — в 14:00 (21 июня в 0:00 по московскому времени). Также на мероприятии пройдёт хакатон с денежными призами. Все участники онсайт-этапа получат специальные футболки от MemSQL. Спешите зарегистрироваться — у MemSQL нашлось место только для 125 участников.

Раунд 2D пройдёт 22 августа в Джайпуре, в университете Manipal.

Начало мероприятий в 8:00 по местному времени, раунд начнётся в 12:00 (9:30 по московскому времени). Там тоже будет хакатон и футболки.

Также во всех этих раундах (но не в хакатонах) можно участвовать онлайн.

Скоро начнётся квалификационный раунд Яндекс.Алгоритм 2015. Это последняя возможность для тех, кто не участвовал в тренировочном раунде или не решил в нём ни одной задачи, пройти на отборочные раунды, которые состоятся 24 и 30 мая и 6 июня.

Сам квалификационный раунд продлится 100 минут и пройдёт в виде виртуального контеста: каждый участник сам может выбрать время начала в периоде между 17 мая 0:00 и 18 мая 0:00 МСК. Это значит, что некоторые участники потенциально смогут продолжать участвовать до 1:40 МСК, поэтому не стоит обсуждать задачи до этого времени. Для прохождения в отборочный раунд необходимо решить хотя бы одну задачу.

Два с половиной месяца назад прошёл Rockethon 2015, 150 лучшим участникам которого обещали футболки. И вот 21 апреля звонят мне из UPS и говорят, что меня ждёт футболка от Rocket Fuel. Ждёт на таможне. Чтобы её пропустили, нужно зайти на сайт, заполнить там форму, отправить скан паспорта, подтверждение заказа и прочие документы. Странно, ведь другие футболки я получал безо всяких сложностей — получаешь извещение, приходишь на почту и забираешь.

Сайт для отправки документов какой-то кривой: своё имя ввести не даёт, вместо этого предлагает выбрать из трёх вариантов (и все три неправильные). Судя по всему, все футболки были оформлены одним заказом, и там видны данные других получателей. Ну и пароль он почему-то не всегда принимает. Ещё там можно посмотреть список остальных футболок и кто там чего навводил.

P.S. Отдельное спасибо UPS за паспортные данные участников sexyprincess91, Milanin и Igor_Kudryashov, которые имели неосторожность эти самые данные ввести. Правильным путём идёте, товарищи!

P.P.S. Не успел.

Недавно стало известно, что в этом году TopCoder собирается проводить региональные онсайт-этапы, совпадающие со вторым раундом TCO 2015. А теперь стало известно время и место проведения первого из них: раунд 2A пройдёт 31 мая в Санкт-Петербурге, в университете ИТМО.

Кроме самого раунда, программа мероприятия включает в себя хакатон с призами на 5000 долларов, а первые 150 участников, прибывших на мероприятие, получат футболки (необходима регистрация). Мероприятия начнутся в 9:00 по московскому времени, а сам раунд — в 15:00. Для тех, кто не пройдёт во второй раунд, будет открыт параллельный раунд. Если вы хотите принять участие в хакатоне, на него необходимо зарегистрироваться не позднее 28 мая (по московскому времени).

Кстати, если копнуть глубже, можно узнать, где пройдут остальные онсайт-этапы: раунд 2B пройдёт в Токио, 2C — в Сан-Франциско, а 2D — в Джайпуре.

Сегодня в 13:00 состоится тренировочный раунд Russian Code Cup 2015. Результаты этого раунда никак не влияют на дальнейшее участие в RCC 2015, поэтому можно рассматривать этот раунд как тренировку перед квалификационными раундами. Продолжительность раунда — 2 часа. Квалификационные раунды состоятся 28 марта, 25 апреля и 31 мая 2015 года.

Ровно через неделю после раунда 2 — 1 февраля, в полночь по Москве — состоится третий раунд Facebook Hacker Cup 2015. Продолжительность раунда — 3 часа. 25 лучших участников выиграют поездку в Менло-Парк для участия в финальном раунде, который пройдёт в офисе Facebook 6 марта.

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

Два часа назад TopCoder разослал всем присутствующим на онсайте TCO14 письмо. Содержание письма не столь важно, а важно то, что в поле "Копия" перечислены e-mail'ы всех присутствующих на онсайте, в общей сложности 557 адресов. Спасибо тебе, TopCoder!

Сегодня в 18:00 состоится третий раунд Google Code Jam. 25 лучших участников выиграют поездку в Нью Йорк на финальный раунд (и возможность не ждать, пока Почта России не привезёт им уже выигранную футболку).

Сегодня начинается ICPC Challenge — дополнительное соревнование для участников финала ICPC, в котором за две недели нужно решить одну игровую задачу. Затем между решениями участников проводится турнир по системе double elimination, результаты которого объявляются на самом финале. Участникам, занявшим лучшие места, выдаются призы.

Решения можно сдавать на C++ и Java. К сожалению, внеконкурсное участие не допускается, хотя условия доступны всем желающим. Недавно ACM проводил открытое соревнование по задаче ICPC Challenge прошлого года, но оно уже закончилось.