(a * b) % c
0На сайте TopCoder появилась очередная статья из раздела Feature Article – Primality Testing : Non-deterministic Algorithms, в начале которой описан любопытный метод вычисления произведения a * b % c, если все числа 64-битные и длинная арифметика не используется. Метод похож на быстрое возведение в степень и работает за O(log b).
Вот, собственно, код, немного оптимизированный мною:
long long multiply(long long a, long long b, long long c) { long long x = 0, y = a % c; b %= c; while (b > 0) { if (b & 1) { x += y; if (x >= c) x -= c; } y <<= 1; if (y >= c) y -= c; b >>= 1; } return x; }
SnarkNews winter series – 2008. Round 3
0Завершился третий раунд SNWS 2008. Очередной странный контест, в котором даже такие небезызвестные люди как Gennady Korotkevich, Marek Cygan и Dmitry Zhukov решили всего 3 задачи.
SnarkNews winter series – 2008. Round 2
0Завершился второй раунд SNWS 2008. Получилось лучше, чем в прошлый раз, но все же не так, как хотелось бы. Отчасти виноват провайдер, который в течение 10-15 минут не давал скачать условия 
.
TopCoder SRM 388
0Прошел очередной TopCoder SRM. 250 и 500 были довольно стандартные: первая на факторизацию чисел, а вторая на простую динамику по подмножествам. 1000 сдали немногие. В итоге – 74-е место и +10 к рейтингу.
TopCoder Open 2008
0Наконец-то началась регистрация на TCO 2008. Следует отметить, что в этот раз количество онсайт-участников увеличено на 50%, а следовательно стало равно 72 (!). Регистрируемся и надеемся на удачу…
TopCoder SRM 387
0Завершился очередной TopCoder SRM. Довольно странным было распределение баллов – 300 за первую и 950 за третью, что, по-моему, оказало лишь психологическое влияние. Неожиданно было также то, что у меня упала 950, а не 300, как я ожидал, написав что-то очень простое и, как мне тогда казалось, бездоказательное. В результате получилось все же не так плохо, как могло быть – 55-е место в дивизионе и +1 к рейтингу.
SnarkNews winter series – 2008. Round 1
0Закончился первый раунд SnarkNews winter series – 2008, который я удачно слил . К сожалению в последнее время это входит в привычку, хотя может быть помешали гости и проблемы с wifi…
SnarkNews: статистика участников в TopCoder SRM's Division 1
0На SnarkNews опубликовали «некоторые статистические результаты по итогам года в TopCoder«, получилось довольно интересно:
- участники, занимавшие первые 3 места в SRM – отсутствую ;
- участники из СНГ и стран Балтии, занимавшие первые 10 мест в SRM – 27-32 место (двойное 8-е место);
- количество участий в SRM – 13-19 место (45 (!!) участий);
- участники, занимавшие первые 3 места в комнатах в SRM – 120 место, (3 раза первое, 7 раз второе и 10 раз третье);
- статистика по потерям во время фазы Systest – 32 место (-5454.34 (!!) балла );
- статистика по полученным во время фазы Challenge очкам – 121-131 место (500 баллов);
- статистика по потерянным во время фазы Challenge очкам – 30 место (-5556.42 (!!) балла ).
Налицо экстенсивный подход, надо будет «интенсифицироваться». Хотя с другой стороны это можно классифицировать как упорство…
Итоги 2007 года: события, удачи и неудачи
0Ну начать стоит с финала ACM ICPC 2007. Это одновременно главная удача и одна из главных неудач. Удача, потому что пройти в финал в нашем регионе довольно тяжело, но мы это сделали, а неудача, потому что во время самого финала мозги объявили забастовку .
Главной неудачей можно считать непрохождение в финал ACM ICPC 2008. Странно, что даже не то, что мы не прошли, хотя по мнению многих вполне могли бы, а то, что случилась та же ситуация, что и на финале – мозги отказали работать, что можно видеть по времени сдачи задачи B. Надеюсь в следующем году такого не будет.
Относительно небольшие, «обычные» неудачи: пролет в TCO’07 (объясняемый тем, что раунд я писал в санатории недалеко от города Кокшетау, условий не было никаких, и весь день перед этим занимался подготовкой республиканской олимпиады школьников), и TCCC’07 (не объяснимый 
).
Радует двойное попадание в десятку на TopCoder и хорошее повышение рейтинга, что позволяет надеятся на хороший результат в TCO’08 .
Ну и просто интересные события:
- в марте съездил в г. Кокшетау, где проходила республиканская олимпиада школьников, на которой впервые большая часть задач была моего авторства (так же попутно познакомился с несколькими интересными людьми )
- в мае съездил в Москву по приглашению Google, от собеседования пока отказался, но возможно в будущем…
- в августе в третий раз был на сборах в Петрозаводске, выступал совместно со знаменитой командой MSU SE, получилось довольно неплохо .
