На этих выходных ходил на Chrome Hackathon & Contest. Подробнее о мероприятии с фото и видео: http://www.developers.org.ua/lenta/articles/chrome-hackathon-contest-kyiv-part-i/ и http://www.developers.org.ua/lenta/events/chrome-hackathon-contest-kyiv-part-ii/.

Я делал расширения для Google Chrome для перевода дат/времен на сайтах во временную зону пользователя с форматированием по заданному шаблону. Странно, но такого расширения нет ни для Chrome (есть с похожей идеей, но только для континентальных штатов США, без форматирования, без перевода дня и требующее дополнительных действий для пользователя), ни для Firefox. А будет полезно в том числе мне, для перевода кучи топкодеровских “08.28.2011 08:55 AM”.

Видео моей презентации расширения на Хакатоне — http://www.youtube.com/watch?v=6ZHpOASnr0I.

Код сейчас по адресу https://github.com/kit1980/chrome-handytd. Расширение работает, но пока это только прототип, многое надо доделывать. Уже после хакатона нашлась ошибка в одной из используемых библиотек — время типа 12:XX AM определяется неверно. В общем, надо тестировать и дорабатывать.

Вообще, мероприятие понравилось, хоть я был и один в своей “команде”. Дома я бы явно не успел за полтора дня сделать такое расширение от идеи до реализации (не имея опыта разработки расширений).

Сегодня участвовал в — 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.