Пушистая смерть здесь. Наглядный пример.

В пятницу вернулись с полуфинала NEERC, который благополучно слили. С первыми тремя задачами худо-бедно справились в начале соревнования, но с F и J возникли проблемы. Набажил в реализации, набажил немного, но как-то очень хитро, так что баги искали очень долго и даже сделали несколько дебаг-сабмитов. Поэтому так оказалось, что практически очевидные по идее и простые в реализации задачи были сданы с +4 каждая на 243й и 248й минутах. В результате - 5 задач с ужасным штрафным временем, 33-е место... "Сияющие повелители", как говорит ilyaraz :)
Как вы наверно уже догадались, в финал мы не прошли. Поэтому торжественно заявляю об окончании выступлении великой и ужасной команды NNSU: Top Lamers ( alapshin , mmatrosov , dark_lamer ) в соревнованиях по программированию! Ура, товарищи!

Немного о самой поездке... В этот раз у нас была программа-минимум. Не провели в Питере ни лишней минуты, приехали как можно позже (в частности, пропустили открытие из-за этого), прогуляли экскурсию, не сделали практически ни одной фотки, не купили ни одной книжки. Всё-таки 3-я поездка уже как-никак :) Зато по сравнению с ЧФ потратили на поездку гораздо меньше времени, пообщались с Саньком Смирновым (он просто нереально крут!) и посмотрели с командой МГУ Южный Парк.

Несколько запоминающихся фактов:
Saratov SU 2 зачем-то проиграл команде Saratov SU 1
Команда SPb IFMO 2 обошла на 16 минут первую команду этого университета, занявшую абсолютное первое место в финале ACM ICPC прошлого года. Атцы!
Южный Парк rocks!
Ну и главное - встреча с А. Смирновым и его повесть о том, почему он оказался в роддоме :-D

Пользуясь случаем, поздравляю команду MSU Unpredictable со вторым местом и проходом в финал!! Отповелевали всех, кроме команды ПетрГУ, выигравшей полуфинал.

Как и в прошлом году, компания ООО "МераНН" проводит игровой конкурс GameRace.
Более подробную информацию можно найти на сайте компании: 
http://www.meranetworks.ru/news_and_eve ... e_race.php

Приглашаю всех поучаствовать в конкурсе - это бесплатно и безопасно для здоровья. К тому же можно еще какие-нибудь призы выиграть. Огромная просьба ко всем участвующим в течение выходных проверить работоспособность GDK на своих компьютерах - пока мы еще не уехали на полуфинал в Питер.

Ну и удачи всем, разумеется! :) 

Вчера последний раз сходил в "Меру" в качестве сотрудника, а именно уволился из сей чудо-конторы. Думаю, жалеть об этом решении не придется... практически единственное, что хотелось бы отметить хорошего - это коллектив, в котором приходилось работать. Практически все - адекватные, добрые люди и обстановка была спокойной и благоприятной. С некоторыми бывшими коллегами даже жалко расставаться :) Зато теперь список видящих в аське сократился почти в 2 раза.
В понедельник пойду уже папствовать в другую контору. Бойся, НПП "Прима" - я иду!

Еще мы сегодня немного слили 5-й этап OpenCup. Бывает. (Влад - АТЕЦ!!!)
Зато на паре после кубка у меня уж очень заладилась игра в Crimsonland. Поставил рекорды времени на 8 уровнях, причем на HardCore!

Dead Space rocks!

Несколько фактов из повседневной жизни...

1. Никогда бы не подумал, что БПшки (продукты "быстрого приготовления") надо искать в отделе "Здоровое питание". Забавно :) С другой стороны, чтобы съесть среднестатистическую БПшку надо действительно обладать отличным здоровьем!

2. Посмотрел свой Random Coder Stats . По этой статистике получается, что все темы я знаю примерно одинаково, только чуть лучше результаты по геометрии (Geom) и значительно хуже по математике (Math). Странно, вроде все должно быть наоборот... Геометрию я вообще не умею писать, а математику вроде немного знаю, хотя бы на олимпиадном уровне. Вообще, странно как-то я на topcoder выступаю (:

3. Примерно на том же сайте сравнил себя с burunduk1 . По задачам у нас счет 0-11 (не в мою пользу, разумеется), причем по матчам, на которых решались эти задачи, счет 3-4 :))

Такие дела.

Прошедшие выходные снова удались! Обо всем по порядку...

В субботу вместе с dagon1  писали Уральскую школьную командную олимпиаду (УРКОП), на тимусе, разумеется. Сдали все 10 задач примерно за 1ч 15мин до конца. В одной из них очень долго тупили, из-за чего получили большое количество штрафа... В результате - 5-е место с отставанием от лидера почти на 300 минут. Результат, будем считать, довольно неплохой. Очень приятно писать контест вместе с человеком, который может быстро и без ошибок закодить геометрию, да и вообще прогать умеет :)

Теперь о жизни... В эту же субботу вечером проходил SRM450, в котором, разумеется, надо было поучаствовать ("что может быть важнее SRM?"). Сильно повезло с проблемсетом, в результате чего удалось решить 250 и 500-point со средним временем, но главное - то что ничего не упало! Еще повезло с комнатой, что дало +75 очков на Challenge Phase. В результате +148 к рейтингу, первое место в комнате и первое в жизни попадание в топ10 по дивизиону (8 место). Ура!!! Теперь я "красный"! С этого момента можно утверждать, что жизнь уже прожита не зря!

В воскресенье собравшись с Владом Епифановым, dagon1   и mmatrosov  , решали интернет-тур на задачах ЧФ московского подрегиона. Список команд, участвовавших в этом соревновании, был не самым сильным, посему почти весь контест мы лидировали с отрывом в 2 задачи. В итоге довольно убедительное первое место. Однако, на этот раз весь контест лично я ничего не делал, поэтому понтоваться тут особо нечем :) Влад и Вася - АТЦЫ!
С учетом команд самого четвертьфинала наше первое место плавно переходит во второе - проиграли 1 задачу MSU Unpredictable (поздравляю еще раз с победой!). Это, правда, не возбраняется, особенно с учётом того, какую резню они устроили на самом ЧФ. 

"Такие дела" (с)

P.S.: замечание для любителей Южного Парка. "Пушистая Смерть" - это когда MSU Unpredictable в хорошей форме пишет контест. И даже перуанские группы тут не помогут!

Всё чаще идут дожди... Да и воздух на улице не такой уже теплый, особенно после 11. Темнеет тоже рано... и довольно некстати. Из-за этого попытки избежать луж, идя после рабочего дня по унылой дороге от Деловой до Родионова, становятся абсолютно бесполезными. Завтра асфальт будет снова устилан пожелтевшей листвой, упрямо прилипающей к замечательным кроссовкам asics. Да, господа, на дворе осень - пора четвертьфиналов NEERC.

Завтра состоится четвертьфинал Московского подрегиона.. Братия, пожелаем же удачи команде MSU Unpredictable, в составе которой завтра будут жечь и убивать Gusakov, ilyakor , ilyaraz . 

Удачи, АТЦЫ!

P.S.: Илюхи и Лёха - надо наказать MSU Cubic, а то Аким на последнем SRM неправ был :)

 Вчера наша грозная команда, в составе mmatrosov ,  alapshin  и меня, вернулась из Саратова, где проводился четвертьфинал Южного подрегиона. Свободного времени было навалом, поскольку делать было особо нечего, развлекали себя бесконечными приколами над Михой (aka Kenny) и поглощением всевозможной пищи в огромных количествах. Миха довольно часто обижался и пытался нам что-то сказать, но мы его не понимали из-за невнятности речи нашего капитана. Бездарно убив таким образом 3 дня и зарядившись вечером перед контестом Южным Парком, потопали мы на основной тур...
Проблемсет был довольно удачный - не было геометрии, алгоритмов на строках и сложных структур на графах (кроме одного гроба, который мы все равно никогда не решили бы). В этот раз нас подвело неумение быстро решать задачи средней сложности - очень долго не было разумных идей по нерешенным задачам в середине контеста. Ну и по мелочи, разумеется, ошибались/тупили достаточно много (боюсь, всевозможных глупостей можно вспомнить не один десяток). Всё же, несмотря на это, удалось сдать 7 задач - всё таки что-то решать умеем, да и опыт какой-никакой уже есть. В результате вполне нейтральное, довольно ожидаемое 5-е место и диплом 2-й степени. Результат, конечно, не выдающийся, но и не совсем уж провальный, особенно на фоне результатов других команд этого четвертьфинала.
11 ноября будет полуфинал в Питере... Пока попадание в финал нам нисколько не грозит, но всякое бывает, посмотрим, что мы там изобразим :)

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

Хотя временами было скучновато, да и выступление наше нельзя назвать идеальным, в целом можно считать, что поездка удалась. "ACM rocks" (c), да и для разнообразия - самое то!

Миха - Человек-Краб

В среду ходил на собеседование в Интел. ( Read More... )

Завтра (т.е. уже сегодня) состоится 4-й раунд OpenCup. По планам, мы должны на этот раз обойти MSU Unpredictable, да и вообще пора бы уже занять 1-е место)) Послендние 2 события, полагаю, равновероятны, хоть одно и является частью другого.

Послезавтра уезжаем на неделю в Саратов, на четвертьфинал ACM ICPC. Свято верю в то, что мы сможем пробиться в полуфинал) неплохо бы на этот раз и на Code Game Challenge что-нибудь нормальное изобразить. Трансляцию ЧФ можно будет увидеть 9 октбяря (с 9.00 до 13.00 - до заморозки) на сайте четвертьфинала.

Сейчас всем надо собраться и поболеть за НН.

Последние выходные были просто шикарными! Как в субботу, так и в воскресенье удалось поучаствовать в 5-часовых контестах в составе сильных команд. Даже не смотря на небольшой слив и косяки с моей стороны, такой вид отдыха очень-очень понравился. Кроме того, удалось в ночь с субботы на воскресенье попроталкивать/поподгонять задачу с субботнего тура OpenCup. Занятие тоже весьма интересное и увлекательное, а полученный в 3.34 ночи Accepted хорошо поднял настроение (в процессе проталкивания получилось, что AC - это среднее арифметическое WA и TLE). 
Еще в эти выходные были дни рождения родных и близких, на которые, правда, я благополучно забил. Пользуясь случаем, поздравляю dukovinka  еще раз!

Перед сборами решал задачу. После AC немного задумался над асимптотикой ответа... Потом вспомнил решение, сданное почти 2 года назад под другим аккаунтом, и понял, что подгон, присутствовавший в нем ради того, чтобы избежать TLE, не работает на большом количестве тестов (тогда я думал, что подгон верный, но доказать, разумеется, не мог). Поэтому написал админам в соответствующем форуме, что можно бы добавить несколько тестов...
Сегодня посмотрел результаты сего действа. На форуме написали "Some new tests were added. Read site news.", а в новостях сообщение:

24.08.2009. Changes in problem 1223 Chernobyl’ Eagle on a Roof
...
... // корректировка условий
...
New tests were added. 157 authors have lost AC after rejudge.

Вот такой я нехороший человек. Мелочь, а приятно :)

Вчера вернулся из Петрозаводска, где провел почти 2 недели на сборах по программированию. Как и прошлые 2 раза, сиё мероприятие мне весьма понравилось.
В этот раз мы выступали только вдвоем с Михой - "порешали" прикольные задачки, попроталкивали подгоны + один из дней отдыха сходили на рафтинг . Кроме того, несколько раз ходили с MSU Unpredictable: ilyaraz [ ilyakor , Gusakov ] в заведение с кодовым названием "Чайная Ложка", в котором предлагались очень вкусные блины и ароматный чай разных сортов. Всё это на порядок лучше бесполезного просиживания на парах в универе или проведения времени на работе.
Отдельно напишу про рафтинг: хоть нам и не удалось перевернуться и получить от прогулки максимум ощущений/повреждений, всё равно удалось частично искупаться в волнах, а так же поперебрызгиваться водой с другими рафтами. Жаль было только замерзнувшего японца, он наверно не понимал, почему, догнав чужой рафт, нужно обязательно развенуться боком и забрызгать этот рафт вместе с японцем водой (температуры ~ 15 C).
Результаты наши тоже показались мне вполне приемлемыми. Разумеется, мы не рвали все московские и питерские команды на части, не сдавали по 6 задач в час и не набирали каждый контест по 150 рейтинга. Выступали довольно ровно и не опускались уж ОЧЕНЬ низко, как любили делать это раньше. 3 раза показали хороший результат (13, 13 и 14 места), а на остальных 6 турах были 17-22. Итог: 19 место с 38 решенными задачами.
Кроме того, в этот раз серьезно поработали на дорешивании. Практически каждый день тратили несколько часов на проталкивание нерешенных на туре задач. В итоге, после 6 туров у нас было 22 дорешанных задачи при 24 сданных на контестах. Ещё можно похвастаться тем, что мы сдали одну сложную задачу на туре + одну на дорешивании.
В последние 2 дня произошли довольно забавные события:
1) в 8 туре (APTU Contest) нашей великой команде впервые в жизни удалось полидировать (примерно 30 минут)
( Фото )

2) В последнем туре (Rybinsk SAAT Contest) последняя попытка по задаче J, сделанная нами во время 18000 секунд (т.е. ровно 5 часов) оказалось верной, но не была засчитана, потому что задачи можно сдавать с 0 по 17999 секунды :)
( Фото )

В результате вместо +14 по этой задаче мы получили -14 и надпись Solution stored, not tested

В общем впечатления самые наилучшие, думаю, с удовольствием бы остался в Петрозаводске еще на пару недель. Всё-таки интересно решать задачи и соревноваться, особенно приятно, когда узнаешь какие-нибудь новые забавные вещи.

P.S.: Миха не умеет гамать в цивилу...

Сегодня стали известны результаты Marathon Match 54. Всё-таки я попал в Топ10 (10-е место), причем опередил 11-е место на 0.005% (т.е. отношение его очков к моим ~= 0.99995 :) ). Сиё событие меня весьма порадовало - наконец-то в соревнованиях по программированию попал в топN, где N не очень большое число, кроме того, занял первое место среди российских программистов.

Всего было 1000 тестов - вот мои результаты (для сравнения - в первой строке статистика победителя марафона):

POS HANDLE          COUNTRY             SCORE BESTS UNIQUES PERFECTS ZEROS 
  1 aminallam       Egypt              962.61   331      76       82     0 
 10 ashmelev        Russian Federation 951.80   116       4       86     0

BESTS - кол-во тестов, на которых решение показало лучший результат среди участников
UNIQUES - кол-во тестов, где решение показало единственный лучший результат
PERFECTS - кол-во тестов, на которых получено максимальное число баллов (1.00)
ZEROS - догадайтесь сами :)

Следующий марафон стартует 22 июля - посмотрим, что за задача будет.

P.S.: тем, кто считают, что разбираются в CS и/или программировании, рекомендую прочитать пост ilyaraz  об оптимизации под кэш.

Сегодня решил забить на работу и потратить своё драгоценнейшее время на топкодер. В 15.00 начался SRM444. Соображал очень медленно, кодил еще медленнее и с большим количеством ошибок... Решил 2 задачи, но с очень плохим временем, зато на этот раз ничего не упало - в итоге нейтральное 91-е место и +97 к рейтингу. Теперь мой рейтинг равен году моего рождения :)
Кроме того, до и после SRM развлекал себя дописыванием своего первого марафона (Marathon Match 54), который закончился сегодня в 21.00. Вообще он начался еще 2 недели назад, но с учетом работы и ICFPC 2009 по-нормальному сел за него только в прошедшие выходные. Всего потратил на него довольно много времени, даже без учёта честно написанных нескольких тысяч строк кода, который в итоге был удален/не использован, последний сабмит содержал 1207 строк различных переборов/жадностей/подгонов. Теперь осталось дождаться результатов (на данный момент протестировалось уже 2.28% решений), судя по результатам тестовых примеров, у меня есть шансы даже попасть в топ10... ждем-с
Следующий SRM будет только через 2 недели - самое время порешать что-нибудь с тимуса или почитать, наконец, теорию.

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

( Что случилось )

В целом соревнование порадовало. Очень понравилась командная работа - в конференции в обществе крутых папок можно обсудить жизненные вопросы, вспомнить эксцентриситет орбиты Земли, поругать организаторов за измененные в 9-й раз правила и поздравить ilyaraz с заслуженным Днём Рождения! Получил много положительных эмоций.

Это полный %%здец! Давно так отстойно не прогал - написал две задачи (250 и 550) и обе получили Failed Challenge.
( Read more... )
Результат - 0 баллов и -254 к рейтингу (при том что теоретически нельзя было получить меньше, чем -265)
Чтобы такое счастье отыграть нужно очень хорошо выступить в 4-6 SRM. Зато теперь у меня огромное значение Volatility (647) - так что может побыстрее получиться нормальный рейтинг набрать, если мудить снова не начну.
В общем, не очкуем!

Сегодня прошёл игру Call of Duty 4: Modern Warfare.  Игра просто отличная! Выделю 2 ключевых момента, которые мне понравились:
1). Превосходная графика
2). Это первая игра из тех, в которые я гамал, где сделано что-то похожее на боевые действия. ( Read more... )
В общем, оценка игре - прев. (5.5)

Видимо, оттого что много гамаю + болею совсем разучился решать задачи. Не смог сразу решить 500-point с SRM415 и SRM416. К завтрашнему SRM442 подошел в ужасной форме... Посмотрим, чё из этого выйдет :-)

 Сходил сегодня на награждение за областные студенческие олимпиады - дали еще две двухгиговые флэшки (итого, мне их подарили уже 6 штук за последнее время) - типо такое символичное завершение учебного года.
Каждый день радуюсь, что учёба закончилась. В прошлый четверг "защитил" бакалаврскую и теперь можно забыть об университете до сентября (точнее до декабря, полагаю). Куча бесполезных зачётов, неинтересных лабораторных, курсовых + презентаций хоть и не требовали очень много внимания, но сильно надоели. В итоге, впервые за 2 года возникла такая ситуация, что я ненавижу учёбу еще больше, чем работу.
Теперь можно в своё удовольствие порешать задачки, набрать физическую форму и заняться личной жизнью (создать аккаунт в google, поставить XP на ноут и т.п.)

Вчера написал, пожалуй, самую ужасную программу в своей жизни, когда решал задачу. Надо было всего лишь найти путь кубика между двумя клетками, минимизировав сумму чисел на нижней грани кубика. Задача далеко не самая сложная, да и код не такой уж большой (программа получилась ровно на 200 строк), но такой ереси, насквозь пропитанной STL я еще не писал... Как и полагается в таких случаях пишу предупреждение: приведенный код не рекомендуется для просмотра детям до 6 лет (animashcki , skyrly ) , беременным женщинам (jasminnik , dukovinka ) и людям со слабой психикой (smirnovumret , justdasha ).

( Подробности... )

Возможно это называется "некачественное проектирование" :-) Уже который раз пишу код, а потом только думаю, зачем такой отстой написал. Порадовало, что это чудо протолкнулось с первого раза. Хотя код был более, чем кривой, да и поиск в ширину был совсем не к месту.

Потом пришло некоторое осознание того, как писать подобные задачи по-человечески:

1. Создаем класс, хранящий полное состояние (в данном случае координаты + состояние кубика) = вершина
2. Создаем map<Class, int> - искомые расстояния + надо указать компаратор, который будет две разных вершины сравнивать (различать)
3. Создаем set из вершин с компаратором, сравнивающим соответствующие значения в map
4. Запускаем дейкстру - пока set не пуст обрабатываем его первый элемент (получаем смежные вершины и добавляем их в set).

Пишется довольно просто и понятно. Сложность m * log(n), причем код довольно общий, годится для многих случаев.
Есть какие-нибудь идеи, как можно как-нибудь еще это реализовать?

Наконец дошли руки написать про SRM441.
Задачи были довольно простые, даже третья оказалась вполне решаемой. Всё было бы здорово, если бы не один косяк с моей стороны...
( Read more... )

В итоге 3-е место в комнате и 94-е в дивизионе (забавный факт: однокомандник Миха Матросов тоже занял 94-е место, но в див2)
Хоть и получил +39 к рейтингу, но всё равно можно было выступить лучше, поэтому до 13 июня ставлю себе статус лошара :-)