Во вторник закончился необычный 48-часовой контест Time Limit Exceeded (TLE ‘10).

Было 8 задач, в большинстве суть задания сводилась к написанию программы минимальной длины на C (gcc 4.3.4; по правилам можно было и на C++, но с ним шансов на победу не было). Похожая идея для Perl, PHP, Python, Ruby реализована на Code Golf. Задания на любителя — не всем нравится гоняться за лишним байтиком в коде (например, пробелом в конце строки) и эксплуатировать особенности конкретной версии определенного компилятора.

В целом, контест прошел хорошо, мне понравилось. Были огрехи в организации и задачах, но не критичные.

Результат моего участия не самый лучший — 29 место из 114 команд (114 — это те, кто сдал хоть одну задачу; а вообще зарегистрировалось более 500 команд).

Подробнее о задачах.
Super Palindrome. Не совсем понятно, почему организаторы поставили эту задачу первой — по статистике она оказалась самой трудной. Я тоже не решил. Надо было определять nⁿ%p для n и p до 10¹⁸, причем программа должна иметь определенную форму (но это просто).

Super Palindrome — 2. Похоже на предыдущую программу, только ограничение на n и p до 10⁵ и другая форма программы — она должна состоять из трех одинаковых фрагментов. Придать форму просто — ставим в конце комментарий // и копируем три раза. Но в этой задаче сначала неправильно работала проверяющая программа на сервере организаторов, так что я потратил несколько часов на отчаянные поиски ошибки в моем коде или понимании задачи… В общем, моя единственная серьезная претензия к организации. Мое итоговое решение — http://felicity.iiit.ac.in/tle/judge/show.py?id=7906.

The Preprocessor Problem. Эта задача мне понравилась больше всего — нужно было вывести результаты FizzBuzz для чисел от 1 до 1000 с использованием только C-препроцессора. Буквально до последних минут мое решение (http://felicity.iiit.ac.in/tle/judge/show.py?id=7021) было в лидерах, но в последний момент его перебили более коротким, с использованием макроса __COUNTER__. У меня были мысли насчет использования этого макроса, но на моем компьютере стоит Ubuntu Linux 8.04 (со всеми обновлениями) и gcc 4.2, а __COUNTER__ появился только с gcc 4.3 — мне все лень/некогда поставить последнюю версию Ubuntu 9.10.

Carmichael Numbers. Надо было написать программу максимум в 4096 байт, выводящую как можно больше кармайкловых чисел с их простыми множителями за 7 секунд. Я что-то написал, но не очень удачное. А вот некий товарищ Sirius написал программу (http://felicity.iiit.ac.in/tle/judge/show.py?id=5512), которая выводила числа, которые не могла обработать за приемлемое время тестирующая программа организаторов, так что им пришлось ввести в условие искусственное ограничение на размер числа :-D

Compress the Text. Надо было написать программу минимальной длины, выводящую заданный текст с ASCII-графикой — т.е. специализированный архиватор, заточенный под конкретный текст. Я толком не успел ничего сделать, отправил программу с простым puts() заданного текста.

Play with Code. Надо было понять, что делает очень запутанная программа, и переписать коротко. Я пытался разобраться, но в итоге свел к ерунде типа замены двухбуквенных идентификаторов на однобуквенные, удалению неиспользуемых переменных, пробелов и т.д. - много баллов не получилось. После контеста выяснилось, что программа была решением для задачи http://www.spoj.pl/problems/BRCKTS/.

Key to C. Толком разобраться с этой задачей времени не оставалось.

Chain Quine!. Нужно было написать нечто вроде bi-quine. Задачу я решил, но код получился уж очень монструозным.

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