27-ого апреля состоялся финал соревнования КРОК-2012. Я трагически прогулял 1-ый раунд, и я наверное единственный, кто не нервничал на ивэнте.
Московский офис компании КРОК пустил корни между метро Курская и Площадью Ильича.
После регистрации участников, Михаил Мирзаянов толкнул бодрящую вступительную речь, которую я, к сожалению, проспал :(
Состав участников получился очень молодым: почти все папки укатили на Challenge24 (что не повлияло на хавку: в середине дня был фуршет)
Сам финал должен был начаться в 5 вечера, а до этого участников развлекли Code Game Challenge-эм. Нужно было написать бота, который бы перемещался по полю, пил поушены маны и здоровья, швырял в противников всякие нехорошие заклинания или просто бил их посохом (что большинство времени и делал занявший 8-ое место MyasnoyRobot).
Бот vepifanov выиграл для Сергея Рогуленко (SergeyRogulenko) 11-дюймовый макбуку эйр. Бот Епифанова (vepifanov) SergeiRogulenko вылетел из 1/8. Трёхчасовой кодинг бота и послефуршетный просмотр боёв поставили в равные условия невыспавшихся красноглазиков и свеженьких участников финала.
Как раз перед началом турнира дружно крякнули вай-фай сети, но мужественное решение Миши экспроприировать ещё и гостевую сеть позволило стартовать вовремя.
И вот, турнир начался!
Участники открыли задачи, почесали репу (каждый свою, чужую чесать запрещено) и принялись кормить недружелюбный гостевой вайфай высокоинтеллектуальным траффиком.
В этот раз соревнование обошлось без травм головы о задачи, и без характерной боли в закостеневшей за 3 часов сидения тазовой части наборщика кода.
Условия были ясные, тесты корректные, а решения безшаманские. Авторы МОЛОДЦЫ.
Когда соревнование закончилось, все собрались в конференц-руме (в отличие от румов на CF он был один) и упёрлись взглядом в табло (а вот их было два).
Систесты сидели на цепи и угрожающе рычали.
Миша отзвонился Геральду (Gerald), тот спустил собак и они принялись грызть решения на прочность.
На награждении побидетелям дали призы: 100.000 рублей, и два макбука эйр разного весу, зачем-то забрав при этом паспорта.
Победителями стали ( в скобках указаны ники на Codeforces.ru).
1. Эмиль Лернер, Россия, Москва (neex.emil)
2. Дмитрий Егоров, Россия, Санкт-Петербург (Dmitry_Egorov)
3. Владислав Епифанов, Россия, Нижний Новгород (vepifanov)
Немного самокритики от Романа Андреева (romanandreev) — победителя facebook Hacker Cup 2012!
Остальные видео с контеста смотрите в моем канале youtube.
И еще фотографии:
http://www.youtube.com/watch?v=NnX1sin1XqE
Вход тут: http://188.127.224.127/ http://bombermine.ru/
Для проверки игрового движка на Java/HTML5 использую простую игру, написанную на нём за одну неделю.
Интересно, сколько человек выдержит мой игровой сервер. Извините за периодические падения, стектрейсы я коллекционирую :)
Для игры нужен Google Chrome, Firefox 11 или Опера (opera:config, и в user prefs должно быть enable websockets.).
UPD. Текущий рекорд — 50 человек.
UPD2. Некоторые браузеры не поддерживающие WebSockets теперь могут быть использованы для игры. Но Internet Explorer 9 показывает какую-то хрень.
Идеи сюда: http://bombermine.reformal.ru/
UPD3. Понифицировали.
Накопилось много идей, решил сделать движок для браузерных РТС (свой, с покером и шахматистиками). Работа уже идёт, описание оставил на gamedev: http://www.gamedev.ru/projects/forum/?id=160559
Стек технологий: Java, GWT, HTML5. Если тут кто фанатеет серией Dune и C&C, могу принять в команду. Задача — быстро разработать игру, которая займёт свою нишу, аналогично Minecraft.
UPD. Мне уже писал сценарист. В результате обсуждения его бреда, я его послал и сам всё придумал. По этому вопросу можете больше не писать.
Let my contribution to increase.
Competition will held at 9 february 16:00 GMT (20:00 Saratov).
May the Force be with you!
- Pi = ((A*Pi-1 + B) mod M) + 1
- Wi = ((C*Wi-1 + D) mod K) + 1
- Где M, K ≤ 107, P1, W1, A, B, C, D заданы.
- Требуется найти:
- Количество пар (Pi, Wi) таких что не существует пары (Pj, Wj) такой что Pj ≤ Pi и Wj < Wi либо Pj < Pi и Wj ≤ Wi
- Количество пар (Pi, Wi) таких что не существует пары (Pj, Wj) такой что Pj ≥ Pi и Wj > Wi либо Pj > Pi и Wj ≥ Wi
- Разбить цикл из w на орбиты элементов которые идут через A и на каждой использовать RMQ. Это O(max(M, K) * logN) по времени. Можно улучшить до O( max(M, K) ) используя RMQ за O(1) два раза, ведь последовательности могут иметь длины ⌈ N1 / A⌉ и ⌊ N1 / A⌋.
- Cчитать минимум и количество минимумов среди элементов w проиндексированных (i + j * A)%B , 0 ≤ j < 2k для каждого k, и использовать на этом двоичный подъём, "перемножая" массив как при быстром возведении в степень. Это O(max(M, K) * logN) по времени
Бывает же такое...
It's time to restore my contrib points.
One person from Russian Code Cup finalists said that he code slow in early morning. We have a chance, don't miss it!
Competition will held at 18:00 EDT (5:00 Moscow)
May the Force be with you!
Coding begins in 12:00 PM EDT (20:00 Moscow time)
May the Force be with you!
Кросспост (нажмите сюда чтобы перейти на оригинал)
В рамках проекта SnarkNews стартовала летняя серия индивидуальных соревнований по программированию SnarkNews Summer Series - 2011. Серия состоит из 5 раундов. При этом каждый раунд проходит по правилам TCM/Time. Участвовать в серии могут те, кто или уже зарегистрирован на сервере личных соревнований SnarkNews (список зарегистрированных доступен по ссылке "Пользователи" в верхнем меню), или подал заявку на участие в SNSS-2011 согласно правилам серии по адресу sn_register(собака)snarknews(точка)info.
Участвовать в SNSS-2011 можно, начиная с любого раунда.
01.08.2011 (пн) 15:00. Стартовал первый раунд SnarkNews summer series-2011. Окончание первого раунда - 10.08.2011 15:00.
Отсебятина: Просим на время каждого из раундов не обсуждать задачи.
Congratulations to Petr Mitrichev impressive victory!
We need to assign some number from 0 to 6 to each of the 14 squares. Note that if you take the solution and apply some permutation of digits to the field, you obtain another correct solution. So, the solution is characterized by division of 14 squares to pairs. If we have such a partition, then it is possible to generate a 7! corresponding solutions. Count of possible partitions is 13!! = 13·11·9·7·5·3 = 135135 . It is easily to verify the correctness for each of the 100k options.
With up to rotations, count of all field configurations that have solutions is about 6000. The largest number of solutions - 22·7!.
Подколки:
1) If you do not optimize the solution in 7! time, you can get a TL. As was shown in the comments it’s enough to optimize 7 times.
2) You would think that the squares are divided into two classes - 7 squares that have double dominoes, and 7, in which it is not present. If we talk in terms of graphs there are 7 vertices with degree 2, and 7 with degree of 4. Clearly, two vertices of degree 2 can not correspond to a single digit, otherwise we get two double dominoes. With this division is sufficient to iterate over 7! possible matches vertices of the second type to vertices of the first type.
Double domino 4-4 split between the two squares. There are 6 vertices of degree 2 and 8 vertices of degree. Challenge Succeeded.
Furthermore:
Here for two double dominoes lie between squares!
And bonus, one of the most beautiful configurations with several holes:
Disconnected configuration with solutions don’t exist :(
> The IPSC 2011 contest will be held from June 5, noon CEST to June 5, 5:00 pm CEST.
I inspired by team "Never Retired" and Problem Q from practice,
Team list
Onine standings
Lets discuss it here, but not in the time of event.
Сегодня на Открытом Кубке мне впервые удалось успешно применить в спортивной практике метод графического дебага, и об этой success story дальше и пойдет повествование :)
Смотреть задачу O
В задаче требуется найти, с какой скоростью (от 0 до 300 м/с) должна выстрелить пушка, направленная под углом d (от 0 до 78°), чтобы из точки (xu,yu) попасть в (xo,yo), если на снаряд действует ускорение свободного падения g и ускорение силы ветра w, либо вернуть −1, если это невозможно.
Если просто записать уравнения по x и y, придется решать квадратное уравнение по t, и можно застрять в неприятных выкладках. К счастью, достаточно воспользоваться понятием равнодействующей и повернуть мир на соответствующий угол (косинус угла после этого все равно останется положительным, что благотворно влияет на его положение в знаменателе).
Руководствуясь этими несложными соображениями, я написал такой код с несколькими отсечениями:
{
double omega = atan(w / g);
d -= omega;
double xx = x * cos(omega) + y * sin(omega);
double yy = x * -sin(omega) + y * cos(omega);
double a = sqrt(g * g + w * w);
if (xx < 0.0) return -1;
if (xx * tan(d) <= y) return -1;
double v2 = a * xx * xx / 2.0 / (xx * tan(d) - yy) / cos(d) / cos(d);
if (v2 < 0.0) return -1;
double v = sqrt(v2);
if (v >= 0.0 && v <= 300.0) {
return v;
}
return -1;
}
И получил WA2. Самые внимательные, конечно, уже заметили ошибку, но я в их число никогда не входил и принялся дебажить :) Однако придумать подходящий тест не получилось. «А хорошо бы посмотреть для большого количества пар (x,y), как летят снаряды» — подумал я. Но стандартные средства, используемые на контестах, типа силовой отладки или логов не особо удобны для обнаружения багов в подобных задачах. Несколько удобнее была бы псевдографика, но все же она недостаточно наглядна. Хорошо бы подошел BMP, но по памяти его написать не очень просто. И тут я вспомнил о самом простом графическом формате — portable pixmap format (PPM), обнаруженном в процессе игр с AGG. Его открывают, например, XnView, Lister@Total, Photoshop. Скопирую пример из википедии:
# The P3 means colors are in ASCII, then 3 columns and 2 rows,
# then 255 for max color, then RGB triplets
3 2
255
255 0 0 0 255 0 0 0 255
255 255 0 255 255 255 0 0 0
За пару минут я написал визуализацию ответов программы на протабулированные координаты, подкрасил горизонталь, начало координат, обозначил скорость яркостью цвета, выделил среднюю скорость, и получил правдоподобно выглядящие картинки:
Немного поиграв с w и d, на одной из картинок я увидел странный артефакт — видимо, сработало какое-то отсечение, «испортившее» параболу:
Подкрасив разные отсечения разными цветами, я нашел ошибочную строку :)
Исправил и получил AC :)
К слову, метод графического дебага, пожалуй, единственно возможный в написании рендеров. Кто видел геймдевелоперов-рендеристов за работой, тот под LSD скучает!
Discuss it here.
Предлагаю обсудить сей эпичный пост:
http://sharpc.livejournal.com/67583.html
Многие начинающие программисты, особенно обучающиеся в провинциальных вузах, часто не знают, в какую сторону им развиваться, и что они должны знать для того, чтобы эффективно работать по специальности. Удивительно, но каждый день используя продукты и технологии, созданные другими программистами на основании развитых областей знания, они даже не догадываются о том, как они устроены.
And may The Force be with you.
Добрые люди, пишите мне в личку.
UPD. Спасибо хорошим и добрым людям. Прошу больше не комментировать эту тему, чтобы не висела в топе.
UPD 2. У меня самого уже не первый год есть акк на хабре. Писать сам боюсь, вдруг засмеют :)
And may The Force be with you.
Участвовать в SNWS-2011 можно, начиная с любого раунда.
SN contests
| Name | Type | Registration deadline | Start | Finish | |
|---|---|---|---|---|---|
| SNWS-11,R1 | TCM/SE (1,1,4) | - | 01.01.2011 20:00 | 10.01.2011 14:30 | |
| SNWS-11,R2 | TCM/SE (1,1,4) | - | 06.01.2011 14:00 | 12.01.2011 14:00 | |
| SNWS-11,R3 | TCM/SE (1,1,4) | - | 12.01.2011 14:00 | 18.01.2011 14:00 | |
| SNWS-11,R4 | TCM/SE (1,1,4) | - | 18.01.2011 14:00 | 24.01.2011 14:00 | |
| SNWS-11,R5 | TCM/SE (1,1,4) | - | 24.01.2011 14:00 | 31.01.2011 18:00 |
Завершился первый раунд SnarkNews winter series-2011. Первое место занял Геннадий Короткевич (Беларусь, Гомель), второе - Пётр Митричев (Россия, Москва), третье - Дмитрий Джулгаков (Украина, НТУ "Харьковский ПИ").
При составлении первого тура были использованы задачи локальных контестов североамериканских университетов.
Прошу до конца раунда не обсуждать задачи в комментариях.
"...сюда в двенадцать часов новогодней ночи, прорвавшись через пургу, пришли люди, которым было интереснее доводить до конца или начинать сызнова какое-нибудь полезное дело, чем глушить себя водкой, бессмысленно дрыгать ногами, играть в фанты и заниматься флиртом разных степеней легкости... Они были магами потому, что очень много знали, так много, что количество перешло у них наконец в качество, и они стали с миром в другие отношения, нежели обычные люди".
Традиционно Новогодний Контест состоит из двух номинаций: командной и личной. В каждой из номинаций подводится отдельный зачёт.
7-й Простой Новогодний Контест проводится с 5:00 31.12.2010 по 16:30 10.01.2010, время московское. Задачи данного контеста выбраны из числа тех, которые уже предлагались на командных соревнованиях по программированию в 2010 году, но так и не были решены. Идея "простого контеста" принадлежит А. Лопатину и Н. Дурову.
Участвовать в 7-м Простом Новогоднем Контесте могут команды, зарегистрированные для участия в VIII Открытом Кубке им. Е.В. Панкратьева по программированию (с теми же логином и паролем).
6-й Новогодний Экспресс-Контест проводится с 20:00 31.12.2010 по 8:00 1.1.2011. Контест будет состоять из 6-7 задач различной сложности. Штрафное время по каждой сданной задаче в Новогодних Экспресс-Контестах начисляется как расстояние от момента её сдачи до Нового Года (то есть задача, сданная в 21:00, получает штрафное время 180 - так же, как задача, сданная в 3-00).
Участвовать в Новогоднем Экспресс-Контесте могут пользователи, зарегистрированные на сервере личных соревнований SnarkNews.
Задача E. Multithreading
Придётся разобрать несколько случаев. Пусть S это сумма всех ni. Если W ≤ 0 или W > S то, очевидно, ответ IMPOSSIBLE. В случае N = 1 ответ существует только при W = S, это S итераций единственного потока.Запишем вместо номеров потока скобки разных видов, расставить открывающие и закрывающие просто - соответствующие пары скобок одного типа должны идти последовательно, не пересекаяся. Если в программе есть подпоследовательность типа [(]) то можно заменить её на ([]), понятно, что результат будет тот же. Таким образом, достаточно помещать итерации разных потоков одну в другую, как скобки.
Получить W = 1 можно только поместив все пары скобок внутрь какой-то одной. Поскольку пара скобок не может содержать пару такого же типа, найти найти такой i, что ni = 1. Если же такого i нету, ответ IMPOSSIBLE.