Хотел поделиться своими впечатлениями еще давно, но никак не мог найти время. И вот по истечении двух месяцев, оно все-таки нашлось. На борту самолета из Сан-Франциско в Париж. Лучше поздно, чем никогда :)

Так, вот! Мы, команда Saratov SU2 (уже Retired), решили после пятилетнего перерыва вспомнить молодость и поучаствовать в соревновании под названием Challenge 24. Это ежегодное командное соревнование проводимое на базе BME university, отличается своими нестандартными задачами (гибрид ipsc, токподеровского марафона, acm icpc с открытыми тестами, и codegame challenge) и достаточно хардкорным онсайт финалом, который проходит 24 часа нон-стоп! Причем команде выдают лишь две розетки - эзернет и сеть 220V, а все остальное должно быть с собой (ноутбуки, хабы/раутеры, провода, спальники, и т.д.) Ах да, чуть не забыл, если вы вышли в онсайт, то проезд и проживание за ваш счет :)

Она из прелестей соревнования заключается в том, что на пути к 24-часовому финалу есть всего лишь одна преграда - отборочный тур по интернету, который идет 5 часов. В онсайт финал приглашаются лучшие 27 команд, плюс топ 3 прошлого года. Мы подумали что это хороший повод поучаствовать и написать отборочный тур. Собственно, о нем и рассказ.

На момент интернет тура Иван с Игорем были в Швейцарии, а я в Калифорнии. Поэтому связь было решено держать по скайпу. У меня шел первый час ночи, у ребят утро. За пол часа до начала пришлось усердно попотеть и заняться установкой явы, идеи, а так же написанием шаблона. Все это мы успешно преодолели, и даже спустя 10 минут после того как соревнование началось, нам удалось невероятными телепатическими усилиями найти пароли к задачам в IRC канале, распаковать два вложенных запароленных архива и приступить к прочтению условий :)

После прочтениях всех 6-ти задач, стало понятно что ничего не понятно. Недолго подумав, мы все же вспомнили как проверять изоморфизм деревьев, и было решено писать задачу "B" вдвоем. Я же начал заниматься "D", где нужно было уметь проматывать вперед линейный конгруэнтный генератор. В итоге спустя где-то час-полтора после начала, ребята сдали "B", а я сдал лишь несколько первых тестов от "D" потому как долго возился даже с тривиальным решением (получались другие ответы), а ничего умнее так и не придумал.

По причине тотального отсутствия идей по "D", было принято решение переключить меня на задачу "A", где предлагалось разделить 100 чисел от 0 до 100 на 3 кучки с одинаковой суммой (которую нужно было максимизировать), возможно использовав не все элементы. А ребята стали решать "C", где по изображению пластинки данной в виде .png файла, нужно было понять в каком формате на ней записан звук, воспроизвести его, послушать, и в качестве ответа послать набор цифр которые там проговаривают голосом.
 
С задачей "A" я мучался достаточно долго, пытаясь придумать динамику. Но мозг никак не хотел включаться в 3 часа ночи, поэтому я сдал опять же тривиальным решением несколько первых тестов, чтобы не терять баллы из-за удешевления задачи, и стал думать дальше. Иван с Игорем усиленно писали "C", попутно изучая API явы для работы со звуком и картинками. Тут мне в голову пришла идея - попробовать в "A" поаппроксимировать ответ рандомом (перебираем сумму/ответ сверху вниз, пытаемся 10^5 раз взять случайную перестановку, и попробовать жадно набрать данную сумму три раза; если получилось, то у нас есть кандидат на ответ). Рандом показывал удивительно хорошие результаты близкие к правде, но было понятно что отсылать в таком виде ответы нельзя из-за риска получить WA и штрафные баллы. Было принято решение модифицировать тривиальное решение, чтобы учитывать проаппроксимированный ответ во время перебора, таким образом уменьшив количество состояний.

Тем временем ребята начали с завидной периодичностью звонить по скайпу, ставя послушать звуки которые им удалось проиграть с пластинки. Звук шел, проигрывалось все отлично! Но было одно маленькое "но" -- все записи были похожи на соревнования скретч диджеев, а в ответ нужно было все-таки отослать набор цифр :) Короче говоря мы продолжили заниматься задачами. Я не питал больших надежд на "A", потому что упихать 4^100 не представлялось реальным. Но удивительный факт, после модификации перебора у меня супер быстро отработали все тесты (самый большой работал секунд 15, а количество состояний разрослось всего лишь до 4 * 10^8). Было понятно что ответы правильные, задача успешно сдалась! Позднее в разборе расскажут про правильную динамику, и напишут что перебор пройти ну никак не мог из-за дикого количества состояний :D

Ребята продолжали работать над пластинками, я сразу начал писать марафонную задачу "E", благо было понятно что в ней нужно делать. Минут за 40 до конца нас настиг успех - получилось правильно проиграть первую пластинку и успешно отослать правильный ответ! У меня к этому времени был готов парсинг городов и кое-какие вспомогательные методы. Минут за 15 до конца, написанное впопыхах самое первое решение задачи "E" получило около 45% возможных баллов. И у нас уже было 9 из 10 правильно проигранных пластинок! К сожалению последняя пластинка оказалось немного кривоватой, наш парсер все время сходил с дорожки, и так и не удалось ее проиграть. Но зато получилось улучшить решение "E" до 75% возможных баллов, отослав последний ответ за пол минуты до конца.

Вот так, в очень плотной борьбе, мы и заняли почетное 4-е место, пробившись в онсайт :) Сегодня вечером рейсы из Парижа и Цюриха соберут нас втроем в Будапеште, а завтра и послезавтра (30 апреля и 1 мая) можно будет поболеть за нас, и не только! Надеюсь монитор будет доступен.

P.S.
Ссылка на задачи отборочного раунда: http://ch24.org/ec/html/
Итоговое положение после отборочного раунда: http://ch24.org/team/list
Отчет с прошлогоднего финала: http://codeforces.me/blog/entry/360

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

В итоге убил пол дня на дебаг нестабильной программы, и оказалось баг в JVM! Если в функцию передаешь Integer.MAX_VALUE и пытаешься его использовать справа в сравнении на меньше или равно, в цикле, иногда возвращается false.

Вот минимальный код на котором происходит проблема.

 public class Test {
 
     public static void main(String[] args) {
         for (int i = 0; ; i++) {
             try {
                 go(Integer.MAX_VALUE);
             } catch (Exception e) {
                 System.err.println("Failed after " + i + " iterations");
                 throw new IllegalStateException(e.getMessage());
             }
         }
     }
 
     private static void go(int maxSteps) {
         int count = 1;
         while (count <= maxSteps) {
             if (count >= 10) {
                 break;
             }
             count++;
         }
 
         if (count != 10) {
             throw new IllegalStateException("Count = " + count);
         }
 
     }
 
 }

Выводит примерно следующее:

  Failed after 2402 iterations
  Exception in thread "main" java.lang.IllegalStateException: Count = 2
  	  at Test.main(Test.java:9)

Java:
java version "1.6.0_22"
Java(TM) SE Runtime Environment (build 1.6.0_22-b04-307-10M3261)
Java HotSpot(TM) 64-Bit Server VM (build 17.1-b03-307, mixed mode)

Был бы благодарен, если бы кто-нибудь потестил под разными системами - винда, линукс и отписался о результатах указывая OS и Java version.

UPD: спасибо всем откликнувшимся. видимо проблема в 64-битной JVM, проявляется на всех платформах. баг репорт отправлен в оракл, проходит скрининг http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7007863.

Сегодня я решил написать квалификацию TCO со своего MacBook Pro. До этого мне такая бредовая затея в голову не приходила, но сегодняшний день оказался для меня богат на подвиги.

За пол часа до начала контеста я понял что у меня в апплете не настроен ExampleBuilder, не установлена idea, не говоря уж о том что отсутствует дефолтный проект в котором решаются задачи. Одновременно с этим пришло осознание того, что на маке я ни разу не писал соревнования, а мой последний СРМ был 2 июля 2009.

Но не беда подумал я. Idea скачалась и установилась быстро, плагин настроился, а проект создался... как раз к началу соревнования.

Первая неприятность подстерегла меня после отрытия 250й задачи. Выяснилось что hotkeys для виндовой intellij idea не работают на маке... Предсказуемый сюрприз. Поэтому первую задачу я сдавал долго и мучительно, и сдалась она за 199.66.

Вторая задача сдалась лучше, за 406.29. Но неприятность поджидала за другим углом. Систем тест выявил, что программа работающая за 90ms на моем макбуке превышает лимит в 2 cекунды на топкодеровской конфигурации. Все дело, видимо, в различиях между ява машинами для mac os и linux, либо в том что topcoder использует linux с 2.4 ядром (хотя во вторую причину верится с трудом). Я конечно понимаю что глупо рассчитывать на оптимизации в JRE, и 200 млн. раз в цикле делать обращения к листу (ans += result.get(result.size() - 1)), тем более что можно вообще обойтись операцией умножения сделав все за O(1). Но тестирование на макбуке перед посылкой показало результат в 90ms именно на этом максимальном тесте, поэтому решение было послано без колебаний. В топкодер арене, естественно, решение на максимальном тесте запущено не было, т.к. подозрения на TL отпали после получения мгновенных ответов на локальном тестировании.

for (int i = 0; i < 2 * 10^8; i++) {
   ans += result.get(result.size() - 1);
}

Local: (Mac OS 10.6.3, JRE 1.5 or 1.6 - проверил обе, версия не имеет значения): 100ms
Topcoder (Linux w/2.4 kernel, JRE 1.5.0_03): ~5000ms судя по ответу админов

Обидно блин.

Последняя задача оказалась довольно таки легкой, и бинарный поиск был написан за 10 минут до конца соревнования. Запуск семпл тестов выявил пару неправильных ответов из-за обидного бага, закравшегося в решение. Освоение горячих клавиш для дебага программы оказалось за гранью разумного, поэтому последние 10 минут были потрачены не очень продуктивно. Как водится, баг был найден сразу после окончания соревнования.

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

FML

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

1) Интерпретировать TeX при написание записи в блог или комментария, как оказывается, вполне рискованная затея. Это открывает широкие возможности, начиная от Denial-of-Service атак (проверено) и заканчивая потенциально более неприятными последствиями

2) Cross-Site Scripting (XSS) в поле "Искать по тегу". Заставив участника
сходить по заранее сформированной ссылке (послав ссылку в почту или разместив в посте/комментарии) можно выполнить определенные команды от его имени - это могут быть невинные шалости, а могут быть вещи посерьезнее, такие как кража чужого аккаунта

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