Некоторое время назад написал интерпретатор HQ9+ на новом языке/платформе Opa для конкурса Opa Developer Challenge (результаты конкурса — http://blog.opalang.org/2011/11/opa-developer-challenge-results.html).

Интерпретатор, конечно, сильно громко сказано (HQ9+ — очень примитивный язык): хотелось написать что-то очень простое и быстро, так что там в сумме меньше ста строк, включая HTML-интерфейс, README и куплет из песни “99 бутылок пива”: https://github.com/kit1980/opa-hq9plus.

В конкурсе призового места не занял. У победителей, правда, сильно глючные какие-то программы, но они явно приложили больше усилий и потратили больше времени, чем я на свой “интерпретатор”.

Сама платформа Opa (написана на OCaml, кстати) довольно интересна. Но очевидно, что не взлетит: сомнительная идея использования строго типизированный функциональный язык для массовой веб-разработки (не поймут); попытка включить весь веб-стек, в том числе веб-сервер и СУБД, в одну платформу (и даже один исполняемый файл), которая уже провалилась (отказались от встроенной базы данных и делают интерфейс к внешним базам); странная расстановка приоритетов — до сих пор есть версия только для Linux, причем только для 64-битных систем.

Сегодня участвовал в — Codeforces Beta Round #83 (второй дивизион). Решал все на Python.

Первую и вторую задачу решил без особых проблем, плюс по второй 4 успешных взлома. Третья задача не понравилась, не решал.

С четвертой (D. Баскетбольная команда) получилось так. Формулу для решения я вывел, вроде бы все верно. Но проблема в том, что там дробь, где в числителе и знаменателе — примерно равные по величине произведения сотни довольно больших целых чисел.

Длинная арифметика для целых в Python из коробки, так что при умножении переполнения не будет. Но для деления двух больших целых чисел в Python 2.6 надо привести их к float (иначе получится обязательно целое) — и имеем OverflowError:

>>> 1.0 * (1000 ** 200) / (1001 ** 200)
OverflowError: long int too large to convert to float

По хорошему, чтобы этого избежать, надо не считать отдельно числитель и знаменатель, а умножать на одно число — делить на одно число (во float) и т.д.

Но в Python 3 можно поделить целые числа и получить float, без проблем переполнения в случае подсчета отдельно числителя и знаменателя:

>>> (1000 ** 200) / (1001 ** 200)
0.8188125757004808

Еще в Python 2.6 можно было бы использовать тип Decimal:

>>> from decimal import Decimal
>>> Decimal(1000 ** 200) / Decimal(1001 ** 200)
Decimal(‘0.8188125757004809207789472534’)

Интересно, что в C++ при включенных оптимизациях (по крайней мере в g++ с -O2) при вычислении отдельно числителя и знаменателя не происходит переполнения double, т.к. используются регистры сопроцессора с большей разрядностью без пересылки промежуточных результатов в память.

Ночью участвовал в SRM 514, в первом дивизионе.

Повезло, что задача на 250 баллов была похожа на задачу, которую я уже решал в 2009 году на контесте “Potyczki Algorytmiczne”. Так что отправил решение я довольно быстро, но потом увидел у себя ошибку, связанную с отрицательными числами — пришлось править и снова посылать. Вторую задачу не смотрел, третья показалась уж очень сложной.

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

Из-за ошибок с отрицательными числами первая задача у многих упала, так что одной решенной задачи даже с учетом повторной отправки мне хватило на +89 баллов рейтинга, и теперь у меня максимальной рейтинг в алгоритмах за все время моего участия — 1298.

После почти трехмесячного перерыва написал SRM на TopCoder — SRM 511. Решил две задачки во втором дивизионе и завалил одно чужое решение — снова вышел в первый дивизион.

А еще в моей комнате был какой-то очень тупой читер с 249.99 и 499.95 баллами за первую и вторую задачи (из 250 и 500 соответственно).

Вернулись из Будапешта с финала Challenge24 2011.

На замену Ренату (он еще давно нам сказал, что на финал не поедет) взяли бразильца Кауэ (kauesilv на TopCoder), хороший парень.

Общая организация контеста была так себе (менялись условия заданий, запланированное время проведения отдельных раундов, во всех документах фигурировали имена давно замененных участников, много проблем с техникой), зато кормили просто отлично.

Задания были довольно разнообразные и интересные, условия и разбор должны скоро опубликовать.

В итоге заняли 22 место среди 27 приехавших команд. Неплохо, учитывая, что без Рената мы бы вообще не прошли на финал, скорее всего.

Кроме контеста, было три дня на посмотреть Будапешт — очень симпатичный город.

В общем, поездка понравилась.

Вчера участвовал в юбилейном SRM 500 на TopCoder (во втором дивизионе).

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

Я первую задачу писал долго, взломать никого тоже не успел — минус 63 балла рейтинга.

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

Сегодня в первый раз участвовал в соревновании на Codeforces — Codeforces Beta Round #62.

За приемлемое время решил две простых задачи, так что теперь я там “капитан” с рейтингом 1660, в первом дивизионе — http://codeforces.ru/profile/kit1980.

Немного необычно читать условия задач на русском… Еще надо бы разобраться, как там взломы чужих решений работают: очень сильно отличается от TopCoder.

Сегодня участвовал в SRM 498 на TopCoder, во втором дивизионе.

Впервые правильно решил третью задачу в контесте, но гордиться особо нечем — “самая сложная” третья задача оказалась совершенно элементарной (я оправлял свое примитивное решение без особой надежды на успех, на всякий случай).

Во второй задаче допустил логическую ошибку — решение не прошло системные тесты. Первую сделал довольно быстро.

Итоговых +16 баллов немного не хватило для очередного выхода в первый дивизион.

Думал, после провала квалификационного раунда организаторы исправятся.

Но нет: Facebook Hacker Cup Round 1A — это кромешный беспросветный пиздец. Условия задач кардинально меняются налету и втихаря; формат реальных данных не такой, как в примерах; официальное решение для второй задачи неправильное… Ну и самое главное — у большинства решения теряются при отправке: “Some people have experienced issues submitting their output. We are aware of the issue and are working on a resolution.”

Сегодня прошел SRM 490 на TopCoder.

Первая задача была легкой, решил довольно быстро.

Вторую задачу решил, но совершенно неоптимальным способом — было очевидно, что не проходит по времени. А математического решения так и не придумал. Зато на этой задаче набил +200 очков в challenge-фазе очевидным тестом.

В итоге — рейтинг 1227, и я снова выбрался в первый дивизион.