ItsNear's blog

By ItsNear, 8 years ago, translation, In English,

TopCoder Open 2011 keeps going.

Yesterday we were supposed to hold a poker tournament with a grand prize MacBook Air. There were a lot of people willing to participate, which forced us to split the tournament into two elimination rounds and one final. Out of 16 people who registered for the tournament, 8 were russian-speaking, and all of them appeared to be in the same elimination round. Petr and MikhaelOK advanced from that round, while 7ania7 and theycallhimtom advanced from another one, which was non-russian-speaking. Unfortunately I don't have any pictures of the elimination rounds, however, we played more poker that day, in the same place, so this picture gives you pretty good understanding of how it looked like (during the elimination round it was a little bit more crowded though):


Last time I didn't publish any pictures of a hotel, except one view out of the window. The hotel is called The Westin Diplomat.


It is located in a Hollywood city. The city is in 20 minutes of driving from Miami, however it looks like a small village with a lot of palms. The hotel looks weird in such a setting, since essentially it is 36-storey skyscraper. It is located right next to the Ocean shore, such that the moment you leave the hotel, you find yourself on the beach.

Read more »

Tags tco
 
 
 
 
  • Vote: I like it
  • +91
  • Vote: I do not like it

By ItsNear, 8 years ago, translation, In English,

Today I and Eric, CEO of MemSQL, went to Florida, to the Hollywood city, to visit TopCoder Open 2011, which we sponsor. Intel and Facebook are two other sponsors.
We left San Francisco at 8 AM. In SFO we saw Petr. That made us believe, that he moved to the Valley, which turned out not to be the case.
First thing you see in the hotel is TopCoder banner. Do you know the company, which is listed third in the sponsors list? :о


We went to a Ballroom, where we needed to install our booth. Intel has entire corner in the ballroom, while we and Facebook have small table and a screen. This is how it looks like:


When booth had been installed, we checked in to the room. According to what I heard from competitors, TopCoder provided them with rooms with no ocean view. Since we didn't have room provided by topcoder, for ourselves we got the one with the view.


In 2008, when I was visiting all the programming events, I was taking pictures of all the TopCoders, and other people, who were related to the community, with a stuffed pig. Some of those pictures you can find in my blog here. This time three more people didn't manage to avoid my camera. One of them is Ivan Metelsky, who is working on topcoder SRMs, and also is a judge on the TCO:

Two other are Artem Rakhov and Mike Mirzayanov, who are well known on this website :)


Read more »

Tags tco
 
 
 
 
  • Vote: I like it
  • +92
  • Vote: I do not like it

By ItsNear, 8 years ago, In Russian,
http://www.diofant.ru/problem/1975/

Вот задача. Как не крути, у меня получается, что король выигрывает за один ход только если он стоит в соседней клетке со слоном. Шанс, что при случайной расстановке две фигуры будут стоять в соседних (по углу или стороне) клетках -- 5/48. Но это не правильный ответ.
Кто может подсказать что я упускаю?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By ItsNear, 8 years ago, In Russian,
Давно я не задавал тут старых классических задачек.

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

Задача -- выработать узникам такую стратегию (допустим, что перед началом всей этой истоии, им дан один вечер собраться вместе и обсудить ее), при которой один из них в какой-то момент времени сможет сказать с вероятность 100%, что каждый из них уже побывал в этой комнате хотя бы раз.

У задачи два варианта -- в одном в начале лампочка выключена, во втором в случайном состоянии.

Read more »

 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it

By ItsNear, 8 years ago, In Russian,

Как и в прошлом году, в этом году готовиться к ICFPC мы начали заранее. Основная проблема прошлого года была зоопарк языков программирования. В этом мы заранее договорились, что будем писать на Java, но позже, из-за того, что некоторые ребята умели писать только на С++, поменяли выбор на С++. Всем было понятно, что этот язык не подходит для такого рода соревнования, но идея писать в crazy mode и тратить время на memory leaks и другие чудеса С++ в принципе всех устраивала. Потом это немного выйдет боком – просранная инициализация переменной заставит нас поломать голову над тем, почему решение падает один раз из 20 посылок :о) А еще надо было писать под Linux, так что для меня это было еще и первое серьезное знакомство с vim.
Умные ребята заметили, что картинка на сайте с символом lambda содержит в себе JAR архив, в котором лежит другая картинка, с изображением MTG-карты с лямбдой. Было понятно, что условие будет связано с lambda calculus и с Magic: The Gathering. Это так и оказалось.

Условие.
Условие можно пропустить, если вы его знаете, или прочитать по диагонали (особенно описание карт). Вникать не обязательно.
Играют два игрока. У каждого есть 256 слотов. Каждый слот характеризуется его хп (в начале 10К) и его содержимым. Содержимое – либо число, либо функция.
Также у каждого игрока есть неограниченный набор карт. Каждая карта – это тоже либо число (такая карта всего одна -- zero), либо функция. На своем ходу игрок выбирает одну карту, и один свой слот. Если у слота ноль хп, ход сразу завершается, и ничего не происходит. Иначе, игрок говорит, хочет он сыграть слот на карту, или карту на слот. В первом случае, если в слоте функция, то она вызывается, и в качестве параметра ей передается выбранная карта, а если в слоте было число, то ход завершается с ошибкой. Во втором случае все происходит наоборот – значение в слоте передается в качестве параметра функции на карте. В обоих случаях результат выполнения заносится в выбранный слот.
Например, пусть в слоте лежит фукцния I (функция, которая принимает один аргумент, и возвращает его). Пусть игрок выбрал этот слот, и выбрал карту zero, а затем выбрал, что он играет слот на карту. Тогда значение на карте (ноль) будет передано функции в слоте (I) в качестве аргумента. Результат (который, очевидно ноль) будет помещен в слот.
Далее по тексту ход “revive 5” будет обозначать игру карты revive на слот 5, а ход “5 revive” – игру слота пять на карту revive (номер слота и название карты выбраны для примера).
Игра кончается либо когда у одного из игроков все слоты имеют 0хп, либо после 100К ходов.
Кратко пробежимся по картам:
I(x) – функция, которая возвращает x.
Zero – число ноль
Succ(x) – возвращает x + 1
Dbl(x) – возвращает x*2
Inc(x) – увеличивает хп в своем слоте x на один.
Dec(x) – уменьшает хп в слоте оппонента с номером 255-x на один.
Attack(i,j,n) – наносит в свой слот номер i n урона, а в слот оппонента с номером 255-j n*9/10 урона. То есть себе наносится урона больше. При этом если в своей клетке меньше чем n хп, то атака не пройдет – это важный момент. При этом если в слоте оппонента меньше хп, то атака пройдет, просто оставив в клетке 0 хп.
Help(i,j,n) – наносит в свой слот номер i n урона, и свой же слот j лечит на 11*n/10. Опять же, если хп не хватает в i-ой клетке, то ничего не сработает.
Put(x) – возвращает I.
Get(x) – возвращает содержимое своей клетки с номером x. Очень удобная функция :о)
Copy(x) – возвращает содержимое клетки оппонента с номером x.
Revive(x) – если в своей клетке x ноль хп (она мертва), делает в ней 1 хп.
Это все были скучные функции. Еще две функции выносили мозг:
K(x,y) – возвращает x
S(x,y,z) – вычисляет h=x(z), вычисляет g=y(z), возвращает h(g).
И одна функция делает всю эту игру втройне интереснее:
Zombie(i,f) – если у оппонента слот 255-i мертв, то делает ей -1 хп, и помещает туда функцию f.
Сразу же после этого, перед ходом оппонента, все клетки, у которых -1 хп, автоматически вызывают содержащуюся в них функцию (и кол-во хп меняется обратно на ноль), передав ей в качестве параметра I. При этом (и это самое крутое) в этот момент значение функций inc, dec, attack и help меняют знак в своем позитивном эффекте. Так, inc наносит урон вместо лечения, dec лечит вместо нанесения урона, attack лечит вместо нанесения урона врагу (но по прежнему наносит урон себе), help наносит урон дважды вместо нанесения урона и лечения.
Теперь к повествованию.

Первый день, четверг.
Контест начался в пять вечера по моему времени. Я ошибся с переводом времени, и был уверен, что он начнется только в пятницу. Случайно открыв сайт в восемь вечера я был очень неприятно удивлен.
О стратегии пока думать было рано. В любом случае будет нужен эмулятор игры, поэтому сначала я написал классы карты, слота, игры, и вбил эффекты всех карт. С++ для этого оказался не самым лучшим выбором, но было поздно идти назад :о) Потом написал небольшой интерпретатор, который позволяет играть двумя игроками. Жюри предоставляло свой, но он был ужасно неудобен в плане управления, и добавления AI. День примерно так и кончился. Ребята за ночь хорошо проанализировали разные комбирации, и составили целую страницу идей.

День второй. Пятница.
Теперь, когда небольшой набор инструментов есть, можно пытаться думать о стратегии. Первая мысль, которую мы проверяем, это бесконечные циклы. Получается написать функцию, которая вызывает inc(0), то есть лечит нулевую клетку, а потом вызывает саму себя. Неприятность в том, что если в течение хода выполняется более 1000 функций, то ход останавливается с ошибкой (при этом выполненные эффекты не отменяются). Из-за этого лечащая функция успевает полечить только на 200. При стартовом ХП у клетеки в 10000 сразу видно, что inc и dec бесполезные функции (dec может быть разве что полезен добивать слот, который оживили revive-ом, так как у слота в этот момент 0 хп, но это мы так и не применили почти).
Несколько важных моментов еще: 0-ой слот стратегически очень важен, потому что к нему легко обращаться. Допустим, чтобы его оживить достаточно сделать x revive; x zero, где x – номер любого другого слота. И, в тоже время, нулевой слот очень сложно убить, потому что все функции, которые общаются к клетке оппонента, обращаются к клетке с номером 255-i, поэтому чтобы нанести урон в нулевую клетку, надо передать 255 в качестве аргумента, а набрать 255 используя только succ и dbl очень сложно. Ближе к середине контеста станет понятно, что тот, кто убивает нулевую клетку быстрее, побеждает, потому что оппонент теряет возможность эффективно играть.
Значит первая идея стратегии такая. Сначала мы набираем с помощью dbl число 8192 в 0-ом слоте. Потом мы делаем attack(0,0,get(0)), что значит, напомню
1. Нанести себе get(0) = 8192 урона в нулевой слот (он останется жив)
2. Нанести оппоненту 8192*0.9 урона в 255-0=255 слот
Затем сразу делаем attack(1,0,get(0)), что наносит нам 8192 урона уже в первый слот, а оппоненту опять 9/10 от 8К опять в 255. Это убивает 255-ый слот оппонента. А в убитый слот, как мы знаем, можно посадить зомби. А зомби вызывается от имени оппонента, и не имеет проблемы с 255-x. В зомби закладываем функцию, которая делает help(0,0,8192), которая, как мы помним, если выполняется от имени зомби, имеет другой эффект, и просто наносит два раза 8192 урона в нулевую клетку, что ее благополучно убивает. Затем строим функцию help(1,1,8192), которая убивает первую клетку таким же образом.
Сложность в реализации была в том, что не любую функцию легко построить. Например, пусть мы хотим получить attack(get(0),get(0)). Мы играем 0 get, получаем get (в нулевом слоте была функция I, мы передали ей get в качестве аргумента, и она вернула get). Мы играем 0 zero, получаем get(0). Мы играем attack 0, получаем attack(get(0)). Как теперь сделать attack(get(0),get(0))? Чтобы это сделать, надо сделать K 0, S 0, 0 get, 0 zero. Не тривиально? А что, если нужная нам функция гораздо сложнее? Поэтому пришлось потратить не маленькое количество времени на то, чтобы написать раскрывалку скобок – программу, которая берет на вход строку, и возвращает ходы, которые эту строку позволят получить. С таким функционалом писать ботов стало проще. Для не интерактивного бота (который просто за ранее вычисляет свои ходы, и играет их игнорируя действия оппонента) мы просто складываем в вектор результаты работы раскрывателя скобок.
Для первого бота мы просто написали функции вызова зомби последовательно с функциями help(0,0,8192), help(1,1,8192), доверив раскрывателю скобок их построить, и не думая об оптимизации этого процесса с помощью функции get совсем.
Такой бот за ночь с пятницы на субботу в неофициальной турнирной таблице, предоставленной организаторами,  занял третье место.

День третий. Суббота.
Но конкуренты придумывали более крутых ботов, и наш бот постепенно падал вниз. Надо было оптимизировать. Благодаря использованию метода get, и просто оптимизации всех частей кода, получилось убивать нулевую клетку на 50-ый ход. Но кто-то умел делать это быстрее – потому что проигрывали мы в конце с такой тактикой всем топовым командам. Но для этой стратегии улучшить этот аспект уже не получилось. Все, что мы смогли улучшить сильнее, это убийство последующих слотов – за счет, опять же, грамотного использования команды get, мы убивали последующие слоты раз в три хода, убивая все за 1200. Лучшее что я видел в дуэлях, это алгоритм, убивающий нас за 500 ходов с чем-то. Он был на первом месте очень долгое время. Но было понятно, что не важно, как быстро ты убиваешь все. Важно было как быстро ты убиваешь нулевую. Потому наш алгоритм, который работает за 1200, часто убивали за 70К ходов, просто потому, что убивали нам нулевую быстрее – а без нулевой мы не могли сделать ничего.
Вечером я забил на развитие алгоритма с зомби, и начал исследовать новую идею, бота под кодовым названием healer. Если набрать число 8192 в первом слоте, а затем сделать help(0,0,get(1)), то мы нанесем себе в нулевой слот 8192 урона, а потом полечим его на 11/10 от 8192, то есть в итоге мы полечим клетку на 800 хп. Если это делать в бесконечной рекурсии, то она успевает поличить до максимума – до 65К (любые числа больше 65К в игре делались равными 65К насильно) прежде чем падает из-за вызова 1000 функций. Полагая, что все оппоненты, как и мы, будут пытаться слепо нанести 10К урона в нулевой слот, это должно было делать его неуязвимым. Такое получалось сделать уже на 36-ой ход.
Идея интересная, но час был поздний. Развивать ее времени бы не хватило, а проверить концепт как-то было надо. В качестве проверки я написал простой алгоритм, который после лечения до 65К нулевой клетки лечил по очереди все остальные, а затем начинал делать attack(get(0),get(0),get(1)), храня в первом слоте 16К, а в нулевом счетчик, который после каждой атаки увеличивался на один. Таким образом каждый ход я наносил 16К урона себе в очередную клетку (в которой 65К хп – ей это как комариный укус) и 9/10 от 16К оппоненту в очередной слот. Полагая, что оппонент не лечился, это убьет ему слот.
В таком виде я бота заслал. Он убивал все слоты оппонента за 4К ходов, если оппонент бездействовал или не учитывал, что у нас может быть 65К хп. Healer играл хуже чем зомби (но это и ожидаемо – это проверка концепта). Для зомби все шаги были оптимизированы до фанатизма, а в этом боте просто вбиты в том виде, в каком приходили в голову. Некоторые топовые боты его рвали как грелку. Это тоже ожидаемо. Но в остальном он дал некоторую пищу для размышления.
1. Он часто побеждал после 100К хода со счетом 255-1. То есть у нашего бота был убит один слот, а у оппонента один оставался жив. Легко понять, что это значит, что против нас играет что-то похожее на нашего зомби – оно убивает 255 клетку нам (мы ее лечим очень поздно), а затем пытается убить что-то еще, но не ожидает, что там 65К хп. В тоже время мы отлечиваем все наши клетки кроме 255-ой (которую нам убили), а потом убиваем оппоненту все клетки кроме нулевой, потому что наша 255, об которую мы бы это делали, мертва.
2. Часто мы проигрывали после 100К хода со счетом, допустим, 96-160. Не сложно заметить, что сумма чисел равна 256. Это, как опять же легко понять, оппоненты, которые просто пытаются быстро убивать слоты по порядку с конца, в то время как мы лечимся по порядку с начала. И, так как они убивают быстрее, чем мы лечим, то в итоге счет в их пользу (одно лечение занимает шесть ходов в нашей реализации, а одно убийство – четыре в лучшей, которую я могу представить).
Я ушел спать, а ребята оптимизировали healer’а.

День последний. Воскресенье.
Утром восресения до конца контеста оставалось еще 8 часов, но это было воскресенье, и на него уже были планы, поэтому я вышел из игры. Позже ребята допилили нового helper’а, который убивал оппонента быстрее, но в итоге в неофициальной таблице результатов зомби выигрывал чаще, чем healer, и именно его мы заслали как наше финальное решение.


Все наши боты были не интерактивные – мы предпросчитывали последовательность ходов, и просто ее выполняли. Поэтому написанный мной в начале эмулятор, который позволял поддерживать по набору ходов текущее состояние поля, по большому счету оказался бесполезным.
Контест не оставил такого же ощущения удовлетворения, как прошлогодний. В основном потому, что в этом году из-за большого количества отвлекающий факторов, и планов, не получалось посвятить все три дня целиком контесту. Это очень обидно. Написать симулируемый отжиг, чтобы найти короткую последовательность убийства нулевой клетки, или какую-то модель машинного обучения, чтобы менять тактики на ходу в зависимости от действий оппонента, было бы очень интересно, но я даже не брался за это, потому что понимал, что времени не хватит. И писать это на С++ в vim было бы очень смело.
В следующем году придется очень заранее думать над тем, чтобы планов никаких не было. Надо отметить, что соревнования посередине ICFPC написать хорошо не получается. TCO Round 1 был в восемь утра, но за день до этого я лег в четыре, потому что дописывал бота. В итоге место в третьей сотне – событие, которого не происходило очень долгое время. А на раунд mail.ru я вообще забил, потому что был увлечен ICFPC. В любом случае я бы не полетел в Россию на онсайт :о(

 

Read more »

 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,

Ферлонам, Хаустовым Павлам и сочувствующим -- можно ниже не читать :о)

 

Для остальных -- отличная задача.

Дан массив длины 2N. Первые N элементов и последние N элементов отсортированы по возрастанию. Надо отсортировать весь массив за линейное время с константой памяти.

 

Я предполагаю, что это не классика, потому что существует (неверное) (распространенное) мнение, что лучшая реализация Merge Sort требует O(N) памяти. Сам факт, что описанная выше задача имеет решение, очевидно, опровергает это.

 

UPD: Ваши решения можно проверить на случаях

6 7 8 9 10 1 2 3 4 5

и

1 3 5 7 9 2 4 6 8 10.

Почти любое наивное решение не способно решить один из них.

 

Read more »

 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,

Условия: http://contests.snarknews.info/files/snws11/probs/day5.pdf 
Результаты: http://contests.snarknews.info/index.cgi?data=snws11/standing5&menu=index&head=index&mod=snws11&class=snws11 

Задача А.
Сначала заменим все числа на A%mod, так как понятно нас интересует только остаток, затем добавляем сначала все числа с одним остатком, затем с другим итд. Допустим, что сейчас добавляются числа с отстатком m, а до этого уже были добавлены какие-то числа с другими остатками. Поддерживаем динамику d от двух параметров, где d[v][q] = количество последовательностей из уже добавленных чисел таких, что есть ровно v пар чисел с одинаковым остатком, НЕ равным m, стоящих рядом, и q пар чисел с остатком, равным m, стоящих рядом.
Кроме того, двигаясь вправо поддерживаем: n - сколько уже вообще добавлено чисел, и r - сколько уже вообще добавлено чисел с текущим остатком. Теперь, закрепим v и q. У нас есть три опции:
1. Поставить число между двумя одинаковыми числами, не имеющими остаток m. Таких вариантов, очевидно, v, и такое действие уменьшит v
nd[v-1][q] += d[v][q] * v
2. Поставить число между или рядом с числом с остатком m. Это увеличит q. Таких вариантов, если подумать, 2*r-q:
nd[v][q+1] += d[v][q] * (r*2-q)
Наконец, поставить число в любую другую позицию. Это не изменит ни q ни v. Это все оставшиеся варианты, то есть n+1 - v - (r*2-q)
nd[v][q] += d[v][q] * ( n + 1 - v - (r*2-q) ).
Потом, когда остаток от деления меняется, добавляем числа с предыдущим остатком к старым:
nd[v+q][0] += d[v][q];
В конце ответ будет в d[0][0] - потому что не должно быть никаких чисел с равным остатком рядом.


Задача B.
Я занумеровал вершины в порядке выхода из DFS, и вывел их по убыванию этой величины.

Задача C.
Единственное ограничение, данное нам -- это то, что кратность ребер не превышает четырех. В частном слуачае, когда вес всех ребер равен единице, это будет задача на матричную теорему Кирхгофа, которая решается за N^3.
Я упускаю что-то очень важное :о)

Задача F.
Очевидно, сами числа не важны, важна только их длина. Нам надо понять, сколько битов понадобится, чтобы представить число с записью 10^K в системе счисления B. Это, если я правильно помню, равно floor( K*log(B)/log(2)+1 ).

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,

Я расскажу как я решал задачи, которые я сдал.
Мне, в свою очередь, интересно, как решать B :о)

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

Результаты с тимуса: http://acm.timus.ru/monitor.aspx?id=83

Результаты с петрозаводска: http://karelia.snarknews.info/index.cgi?data=macros/run&menu=index&head=index&round=01&sbname=2010s&class=2010s

 

Задача C.
Можно заметить, что окружность вписывается тогда и только тогда, когда произведение радиусов окружностей, между которыми мы ее вставляем, является квадратом рационального числа. Более того, если их радиусы равны A/(B^2) и A/(C^2), то радиус впихнутой окружности будет A/((B+C)^2). То есть если с самого начала можно впихнуть окружность, то можно будет и на каждой следующей итерации, и наоборот. Отсюда, сначала проверим, является ли произведение данных нам радиусов квадратом рационального числа, и, если да, представим радиусы в виде
r1 = (a) / (b)
r2 = (a) / (c)
Где a = r1*r2/gcd(r1,r2). После этого будем на каждой итерации вычислять радиус центрального шарика, и смотреть, с какой стороны относительно центрального шарика нужный нам - и продолжать рекурсивно.
Отдельно надо рассмотреть крайний случай, когда впихнуть шарик нельзя, но запрашивается один из крайних.

Задача G.
Решим по очереди для каждого делителя N, и в конце для N, так, чтобы к моменту, когда мы решаем для некоторого делителя, для всех меньших делителей мы уже знали ответ.
Теперь, чтобы решить для N перебираем все делители N, для каждого делителя смотрим, каков шанс нарваться на этот делитель в интервале [1,10^18], причем так, чтобы при этом не делилось ни на какой больший делитель. Это делается с помощью включения-исключения. Допустим, что мы решаем для числа 12, и хотим узнать, каков шанс нарваться на число, кратное двум, но не кратное четырем или шести. Ответ будет
chance = ( 10^18 / 2 - 10^18 / 4 - 10^18 / 6 + 10^18 / 12 ) / 10^18
Для каждого делителя A прибавляем к ответу ( ans[A] + ans[N / A] ) * chance.
В конце в ответе надо учесть, что, прежде, чем попасть в любой такой делитель, мы сколько-то раз потыкаемся в взаимнопростые числа. Это учитывается как-то так:
ret = ( ret + 1 ) / (allChances);
Где allChances - это сумма всех chance для всех делителей N.

Задача I.
Надо найти N такое, что следующая формула вернет ноль:
- a[n - 1] + (n-1)/n * (- a[n - 2] + (n-1)/n * (- a[n - 3] + (n-1)/n * (...) % n) % n) % n
Восстанавливать надо с конца, получается
ret = 0;
ret += a[n - 1];
ret %= n;
ret *= n
ret /= (n-1)
ret += a[n - 2];
ret %= n^2;
ret *= n;
ret /= (n-1)
...
То есть, тоже самое псевдокодом
for(i from N-1 to 0) {
 ret = (ret + a[i]) % mod;
 if( i == 0 ) break;
 ret *= N;
 mod *= N;
 ret /= (N-1);
}
Тут самое сложное - это сделать это все быстро. Особенно деление по непростому модулю. Так как это длинная арифметика, и решать надо все равно на Java, кажется очевидным попользовать модный modInverse, но такое решение ловит TLE. Я в конце концов пропихнул такое решение:
for(i from N-1 to 0) {
 ret = (ret + a[i] * mul) % (mod_mul);
 if( i == 0 ) break;
 ret *= N;
 mod *= N;
 mul *= (N-1);
 mod_mul *= N*(N-1)
}
ret = ret * mul.modInverse(mod_mul) % mod;


Задача H вроде тривиальная - ДП по подмножествам.
В задаче D строим для первых 100 элементов, и мучительно угадываем закономерность.

Read more »

 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,

На сайте TopCoder.com опубликовали даты и место проведения TopCoder Open 2011

We are excited to announce the 2011 TopCoder Open! The TCO11 will take place September 25 - 28, 2011 at the Westin Diplomat Resort & Spa, Hollywood, Florida, USA. More details about this awesome event to come in March. So if you went to compete, better start practicing now!

(Это не тот Голливуд, где снимают кино. "Тот" Голливуд находится  в другом конце Америки в Los Angeles).

То, что TCO пройдет во Флориде, примечательно, так как последние несколько лет TopCoder Open неизменно проходил в городе развлечений Las Vegas, в отеле Mirage. Удивительно, что место проведения поменяли в этом году.
florida

Несколько слов об отборочных
Отбор проходит каждый раз в несколько этапов (я думаю почти все хотя бы раз пытались отобраться на TCO). Первые несколько раундов для опытных участников обычно являются формальностью -- не проспать, убедиться, что интернет не упадет, написать.
Самое опасное начинается раунда с третьего, где количество проходящих участников уже сравнительно небольшое, а на ТопКодере, как известно, цена ошибки очень велика. Чтобы отобраться на финал мало уметь решать сложные задачи, и мало решать их быстро. Надо на протяжении пяти онлайн раундов ни разу не допустить ошибку. Один пропущенный ноль в константе, int вместо long long, и вы вылетаете.

Как проходит сам онсайт.

В своей жизни я был на нескольких различных соревнованиях. Значительно меньше, чем Петя, или создатель этого сайта, но на приличном количестве, чтобы иметь представление. И с этого ракурса я могу сказать: TopCoder Open -- это то, как чемпионат мира по программированию должен быть проведен.
Во-первых, само место проведения -- это одна большая сказка (это я про Лас-Вегас, но я надеюсь, что во Флориде это не хуже). Вы выходите из отеля, и сразу погружаетесь в невероятную атмосферу. Можно гулять, бухать и веселиться целыми днями, за исключением пары часов на непосредственно тур.
Но даже если вы решите остаться в отведенных под соревнование ballroom'ах, вам не будет там скучно. Все соревнования проводятся очень открыто: зрители ходят прямо между компьютерами участников, и обсуждают на месте. В центре стоят мониторы, которые показывают, что происходит на экранах игроков. Пару лет назад все участники разбивались на несколько полуфинальных групп, и можно было смотреть за другими полуфинальными группами. Сейчас это, вероятно, не так круто, так как участников меньше. Но можно понаблюдать за соревнованиями в других номинациях (что, конечно, поскучнее).
Участники, чтобы не отвлекаться на толпу, сидят в наушниках, или в берушах. Вокруг стоят столы спонсоров, где можно потырить бесплатных прикольных сувениров, поболтать с представителями. Иногда можно найти попкорн, всегда есть энергетики и напитки.

Главное -- нет никаких тупых открытий и закрытий. Все организаторы соревнований, будь то воронежская пародия на олимпиаду или финал ACM ICPC, почему-то считают, что нам очень интересно послушать "какие мы умные, как (оратор) гордится находиться с нами в одной комнате", а также выслушать полный граф поздравлений всех ораторов друг другу. На ТопКодер Open этого говна нет. Есть выступления спонсоров. Но они если и скучные, то авторы могут притянуть ваше внимание. Так, в 2007 и 2008 годах (а может и после этого) компания Eli Lilly после своего представления задавала вопросы по только что рассказанному, и за каждый правильный ответ давала iPod. Казалось бы, как бы скучно не было, слушать надо :о)

Для меня единственный TopCoder Open на котором я был, остался самым незабываемым с точки зрения организации и атмосферы соревнованием, и я бы пожелал каждому из всех вас попасть на него хотя бы раз. Соревнование в сентябре, а сегодня только январь -- поэтому советую последовать совету из новости на topcoder.com и начать усиленно готовиться уже сегодня!

Read more »

 
 
 
 
  • Vote: I like it
  • +48
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Наконец-то мне удалось заставить себя проснуться в 7 утра, и я смог написать первый в своей жизни раунд по крутой системе.
Как я и ожидал, система очень крутая :о)
Очень понравилось то, что когда становится тяжело думать, можно отдохнуть, прогулявшись по решениям в комнате.

Стало интересно, какие есть стратегии на таких раундах.
На первый взгляд, после того, как задача сдана, надо сразу начинать по ней ломать -- потом эти легкие взломы уже кто-то заберет. Пока другая задача не открыта, время по ней, как я понимаю, не течет. Шанс, что в конце не хватит пяти минут, тоже ничтожно мал. А главное - каждый взлом в начале заметно поднимает настроение.
Поэтому я так и играл.
Из минусов я вижу один - так как я оттягиваю свою сдачу сложных задач, я могу потерять простые взломы по ним. Но казалось бы,
а) Где шанс получить простой влом выше - на задаче А или на задаче C? Очевидно, на задаче А их должно быть больше.
б) Я предполагаю, что даже с учетом пяти минут на взломы после каждой сданой задачи, я все равно сдам сложную задачу быстрее среднего участника, которого я мог бы взломать.
в) Когда я сдам задачу С, я очень сомневаюсь, что я захочу ее сразу залочить.

Попутно я следил за всеми участниками на верху таблицы, и никто так больше не делал. Все писали четыре задачи, и только имея их начинали ломать. Этому, видимо, есть какое-то разумное объяснение, которого я не вижу :о)

Вот поэтому и встал вопрос - а по какой стратегии играете вы, и, главное, почему?

Read more »

 
 
 
 
  • Vote: I like it
  • +21
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Еще довольно давно, примерно на первых курсах ВУЗа, я играл с другом по сети в игру SpellForce, и обратил внимание, что когда мой герой бежал по дороге вдоль забора, на повороте он оббежал забор по дуге.
Как раз незадолго до этого мы с друзьями работали над поиском пути для другого проекта, и в нашей реализации персонажи поворачивали резко. Я начал думать, смогу ли я адаптировать свою реализацию так, чтобы персонаж поворачивал по дуге. И я понял, что ничего из этого не выйдет.
Тогда я решил проверить как персонажи поворачивают в эталонной RTS игре, так как раньше внимания на это не обращал. Как и ожидалось, в StarCraft персонажи поворачивают резко.

С тех пор прошло много времени, и недавно, работая над уже совсем другим проектом, я опять задался этим вопросом.

Постановка задачи: имеется персонаж, представленный окружностью радиуса R, посланный из одной точки до другой на местности с препятствиями, представленными выпуклыми многоугольниками. Требуется найти кратчайший путь для персонажа. Очевидно, кратчайший путь будет всегда поворачивать вдоль дуги окружности радиуса R.
Демка почти рабочего решения -- в редких случаях найденный путь не является кратчайшим (левый клик в любой точке пошлет персонажа к этой точке):






Ну и это, в свою очередь, ничто иное, как задача D с чемпионата России по программированию 2006 года:
http://neerc.ifmo.ru/past/2006/problems/problems.pdf
За той лишь разницей, что там многоугольники могли быть не произвольными, а только прямоугольники со сторонами, параллельными осям координат. Что в сущности никак не влияет задачу - общее решение не сложнее частного.
Идея решения достаточно проста. Превращаем окружность в точку, расширив все прямоугольники на ее радиус во всех направлениях, превратив их тем самым в прямоугольники со скругленными углами, и дальше строим граф, где вешнины - это некоторые контрольные точки, а ребра между парой вершин есть тогда и только тогда, когда путь по прямой между этими вершинами не пересекает ни одного многоугольника. Даже при ограничениях, данных в задаче (30 прямоугольников) лучшее такое решение, которое я смог написать, работало 20 секунд на худшем тесте.
Но в нашей задаче есть несколько важных отличий, которые помогут сделать гораздо более быстрое решение:
1. На адекватной карте многоугольники распределены по поверхности карты, не создавая "крайних случаев". Проверяя для данного отрезка пути пересекает ли он какие-то ребра или скругленные углы многоугольников, мы можем использовать какие-то оптимизации, которые могут не улучшать худший случай, но улучшать средний, чтобы сразу отсечь кандидатов, которые даже близко не лежат на пути.
2. Нам не нужен идеальный маршрут. Игрок, скорее всего, не сможет отличить кратчайший маршрут от не самого короткого, а даже если и сможет, едва ли воспримет это как критичное упущение. Поэтому сделать ряд эвристик при проверке отрезка на пересечения.
3. Конечно, надо использовать A* а не Дийкстру.
Определим очертания алгоритма:
1. На вход подается набор многоугольников, координаты начала S, координаты конца E, радиус персонажа R.
2. Для каждого многоугольника отодвигаем каждое ребро от центра многоугольника на R. Для того, чтобы понять, в какую из двух сторон двигать ребро, надо понять, задан он по часовой стрелке или против часовой. Для этого можно, например, посчитать сумму всех векторных произведений соседних сторон. Абсолютная величина этого значения будет удвоенной площадью многоугольника, а знак будет говорить о том, направлены ребра по часовой стрелке или против часовой. В разорванные углы многоугольника добавляем дуги с радиусом R.
3. Забываем про многоугольники, оставляя только набор отрезков и дуг.
4. Строим граф. Для этого поймем, как будет выглядеть кратчайший путь. Если внимательно проанализировать тип карты, становится понятно, что каждый фрагмент пути будет либо пролегать вдоль одной из дуг, либо идти по общей касательной двух дуг (либо идти от стартовой/к конечной точке по касательной одной из дуг).
5. Строим путь. При поиске пути на каждой итерации мы будем находиться в какой-то точке какой-то дуги - вершине графа. Мы будем перебирать все остальные дуги, и идти к ним кратчайшим путем, который, очевидно, будет состоять из пути по дуге до точки касания общей касательной, а затем пути вдоль этой самой общей касательной.

Далее опишем сам алгоритм, и будем достаривать его до рабочего варианта.
1. Если конечная точка достижима из начальной, возвращаем один отрезок
Зависимости: Для проверки нам понадобится функция, которая проверяет, пересекает ли заданный отрезок что-либо на карте. Это, в свою очередь, потребует написать функции пересечения отрезка и отрезка, и пересечения отрезка и дуги (можно заметить, что для данной конкретной задачи хватило бы пересечения отрезка и окружности).
2. Добавим в очередь вершины, достижимые из начальной точки.Вершину будем задавать как дугу, на которой она лежит, ее координаты относительно центра окружности, которой принадлежит эта дуга, и направление, по которому персонаж продолжит движение (по часовой стрелке или против).
{
Point center;
Vector relativePosition;
Bool isClockWise;
}
Для нахождения всех достижимых из начальной точки вершин, построим касательную из этой точке к каждой дуге, и проверим, что отрезок от начальной точки до точки касания не пересекает ничего на карте.
Зависимости: Функция, которая проверяет, пересекает ли заданный отрезок что-либо на карте, у нас уже есть с прошлого шага. К этому добавляется функция поиска касательной к окружности из заданной точки, и проверка, принадлежит ли точка касания заданной дуге.
Нам также понадобится приоритетная очередь. Ключом для элемента приоритетной очереди будем считать уже известное нам расстояние от начальной точки до заданной вершины плюс эвклидово расстояние от заданной вершины до конечной точки (это эвклидово расстояние в нашем случае будет единственным отличием A* от Дийкстры).
3. Аналогично, найдем все вершины, из которых достижима конечная точка.
4. Пока приоритетная очередь не пуста, и пока не найден путь, достаем из приоритетной очереди вершину с минимальным ключом. Помним, что любая вершина -- это точка на дуге.
Обработаем два типа переходов:
а) Проверим, нет ли на текущей дуге вершины (пусть А), из которой достижима конечная точка. Если она есть -- проверим, можем ли мы дойти по дуге от текущей вершины до вершины А. Если можем, добавим в приоритетную очередь конечную точку.
б) Для каждой дуги на карте, отличной от текущей, построим все общие касательные для окружностей, содержащих текущую дугу и закрепленную дугу. Из не более чем четырех касательных оставим не более чем две: мы помним, в каком направлении (по часовой стрелке или против часовой стрелки) двигается персонаж -- оставим те две касательные, по которым можно начать движение двигаясь в том направлении, в котором двигается персонаж. Для каждой из не более чем двух оставшихся касательных проверим, пересекает ли путь по дуге от текущей вершины до точки касания на текущей дуге, а затем вдоль касательной до точки касания на закрепленной дуге, что-либо на карте. Если не пересекает, добавляем точку касания на закрепленной дуге в приоритетную очередь.
Если на очередной итерации с вершины приоритетной очереди достали конечную точку, восстанавливаем путь и возвращаем его.
Зависимости: нам понадобится функция, которая проверяет, пересекает ли заданная дуга что-либо на карте. Для этого надо написать две функции: пересечение дуги и дуги и пересечение дуги и отрезка. Вторая функция у нас осталась с первого шага.
Нам также понадобится функция, проверяющая пересекает ли заданный отрезок что-либо на карте. Она также осталась с первого шага.
Наконец, нам понадобится функция, находящая все общие касательные двух окружностей.

В принципе это весь алгоритм.
Код на ActionScript, и парный ему на JavaScript, доступен здесь:
http://skidanovalex.ru/files/astar.zip
Код на яваскрипте включает несколько тестов к геометрическим функциям (кроме пересечения отрезка и дуги).



Read more »

 
 
 
 
  • Vote: I like it
  • +38
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,

Я уверен, что многие из вас, кто сейчас занимается олимпиадным программированием, попутно занимаются или пытаются заниматься разработкой игр. Я могу с ходу вспомнить упоминания как минимум двух человек об этом хобби, один из которых красный и медалист (если не дважды) ICPC.
Я давно хотел тут написать об одной игре - мы занимались ей с другом, запустили, и она существовала на протяжении двух лет. До этого я так и не написал о ней, потому что не хотел чтобы это сочли как её рекламу, но теперь, когда мы полностью прекратили её поддержку, я думаю я абсолютно чист в желании рассказать о ней.

Я сначала расскажу немного предыстории, затем как мы его разрабатывали, со всеми препятствиями, как мы его запустили, как он развивался, и почему мы его закрыли.

Игра - обычная браузерная ММОРПГ. Посмотреть на нее можно здесь: alideria.ru.

Сначала предыстория. Я раньше играл в игру, назовем ее ИКНН (игра-которую-нельзя-называть), которая собственно послужила прототипом Алидерии. Игра тогда была очень сырая, и я, за компенсацию игровыми ценностями, помогал администраторам переписывать какие-то фрагменты с чистого PHP на PHP+JavaScript, чтобы перенести часть каких-то вещей на клиент, и добавить асинхронности. Я сам тогда был не очень крут как в PHP, так и в JavaScript, и эта работа на самом деле принесла невероятное количество опыта.
В какой-то момент времени оказалось, что я приложил руку почти к каждому аспекту игры на тот момент, и это дало мне понять, что, вероятно, я смогу написать такую игру и сам. Я начал ее писать, и благополучно забил, написав какие-то основы типа регистрации, брождения, боя, инвентаря и магазинов. Это даже было немного играбельно.

Спустя некоторое время мне постучал другой человек, Дима, который тоже помогал разработчикам ИКНН. Только он занимался ей со стороны рисования картинок. Он предложил мне написать вместе игру, а также познакомил с еще одним человеком, тоже Димой, который тоже помогал разработчикам ИКНН, но он, в свою очередь, писал квесты. Я до сих пор его считаю самым талантливым человеком в этой области из всех кого я знаю :о)

Я сразу отрыл исходники игры, которой я занимался, и это послужило как отправная точка. Дима, который рисовал, успел только сделать дизайн (который до сих пор стоит в игре), и ушел из проекта, оставив нас в двоем с Димой, который делает квесты. Он, в свою очередь, согласился проинвестировать часть своих денег в игру (я тогда жил на стипендию и такой возможости не имел), оплатив виртуальный хостинг, и начав заказывать картинки вещей на сайте free-lance.ru. Работа у нас шла очень медленно, в основном потому что я готовился к соревнованиям. Через полтора года у нас был уже рабочий прототип, но все еще не готовый к запуску. В это время у меня начался год, который был посвящен ICPC целиком, а за ним стажировка в Microsoft. Таким образом игра оттянулась еще примерно на год. После стажировки за пять месяцев мы дописали все, что недоставало для запуска, вставили заглушки вместо картинок, которых не хватало, и 16-ого февраля 2009 года мы ее открыли. В качестве первой попытки привлечь аудиторию мы просто кинули ссылку в ИКНН, в игру вошло 20 человек, и виртуальный хостинг накрылся попой. Заказ выделенного сервера пришелся аккурат на праздники в честь 23-его февраля, и поэтому на протяжении первых 10 дней жизни игры она существовала между полностью убитым состоянием, и едва живым :о)
Затем выделенный сервер у нас появился.

Первые проблемы, которые встали после этого:
1. Многие участки кода были очень сырыми. В первые дни работа шла в режиме 10 часов в день, с непрерывным исправлением ошибок, о которых писали в чат. Там же произошла первая отправка запроса вида delete from player_items с забытым where... На протяжении жизни проекта запросов в забытым where, и многочасовых разгребаний их последствий, будет штук 40 :о)
2. Чат, написанный на PHP, нагружает сервер очень сильно. Я не верю вообще в возможность написать на PHP чат, который будет делать адекватную нагрузку. Поэтому сразу пришлось писать новый чат на C++. Это было достаточно сложно, учитывая, что в работе с сетью и потоками под линукс на С++ я был полнейшим нубом. Потом-таки пришлось переписать на Java.

Затем время текло, игроки требовали вещей, которые мы не успели сделать до старта игры. Например - кланов. ММОРПГ без кланов - это не ММОРПГ :о) Систему кланов мы сделали очень крутую, с огромной системой прав доступа, удобным управлением клановыми вещами, и необходимостью всем кланом строить постройки, чтобы получать бонусы. Запускали все это добро в апреле, прямо в мой день рождения. Нет ничего приятнее, чем подарить себе на день рождения релиз клевой штуки. И полный день у компьютера с наблюдением, что все работает. Конечно, в первую секунду упало все, что могло упасть...

Как мы ее раскручивали. Я к моменту запуска уже работал в ИКНН почти официально, и получал кучу бабла - 1000 долларов в месяц за достаточно не большое количество часов. Поэтому деньги на рекламу были. Мы покупали рекламу в Яндексе, Гугле и на ВКонтакте. В тот момент при равных вложениях третья обходила первые две на голову. Потому что тогда контекстная реклама на ВКонтакте вроде как только появилась, и тысяч крутых игр, которые бы ей пользовались, там не было. Сегодня на наш тогдашний бюджет с ВКонтакте наверное даже одного посетителя не получить :о)
Такая реклама позволила медленными темпами развить игру до 200 человек онлайн. И эта цифра никогда не была побита по большому счету. Потому что реклама становилась дороже, а наш бюджет больше не становился. В какой-то момент мы рекламу попросту отключили.

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

В какой-то момент времени мы стали думать о введении платных сервисов. Проект с самого начала разрабатывался как что-то, что со временем должно приносить прибыль. Легче всего было подключить мерчант веб-мани. У Димы был персональный аттестат, и имея его подключить мерчант - это пять кликов на сайте. Но вы можете догадываться, что WebMoney есть у очень малого процента посетителей игры. По этому, помимо мерчанта сразу же начали сотрудничество с компанией, управляющей коротким номером для СМС-сообщений. Запуск СМС-ок и WebMoney для покупки внутренней валюты, и нескольких премиум-сервисов за эту внутреннюю валюту (вида "в течение месяца вы будете получать x1.5 боевого опыта" за 300 рублей) начал приносить какую-то небольшую прибыль. К этому мы добавили позже 2pay, основная крутость которого - это терминалы (ну и яндекс.деньги), и этих трех способов нам хватало по сей день. За все время жалобы от игроков о невозможности пополнить баланс мы слышали лишь несколько раз, всегда от игроков из ближнего зарубежья, и чаще всего выяснялось, что у нашего СМС-оператора есть короткий номер в этой стране, который мы просто добавляли.

В будущем из платных сервисов мы добавили только возможность поменять аватар на форуме, и возможность докупить дополнительные смайлики в игре. Будучи "хорошими админами" мы так и не ввели платные вещи и платные заклинания, сохранив в игре баланс донаторов и не донаторов. Теперь вот я лично жалею о недополученной прибыли :о)

Чтобы вы понимали, чего ждать от такого подхода: при 200 игроках онлайн в середине дня, платных сервисах, ограничивающихся премиум-аккаунтами по 150-300 рублей (в среднем игрок, вкладывающий деньги, активировал три разных премиум-аккаунта на месяц), игра приносит порядка 30 тысяч рублей в месяц (до вычета расходов на сервер, новые картинки, рекламу итд).

Для сравнения, в ИКНН, где онлайн 800 человек, и где можно покупать уникальные вещи за реальные деньги, есть по меньшей мере пять человек, чей комплект вещей стоит более 15ти тысяч долларов. Это мне подсказывает, что их прибыль значительно больее чем в четыре раза превышает нашу.

Другие проблемы, с которыми мы сталкивались:
1. Всегда есть бараны, которые взламывают игру. Иногда приходится тратить очень много времени, чтобы разгрести последствия действий этих баранов.
2. Если администрация ведет себя открыто с игроками (не прячется за абстрактным ником Администратор), общается с ними, то игроки ведут себя значительно требовательней, и относятся к администрации как к обязанной немедленно выполнять их требования. Это заметно раздражает :о
3. Игроки ждут апдейтов очень часто. Выпускать их часто очень сложно. В итоге, опять же, недовольства игроков.
4. Вообще, игроки недовольны всегда. Бывали случаи, когда игрок просил какое-то изменение, а когда оно вводилось, в первых рядах кричал, что это изменение погубит игру.
5. Очень сложно сбалансировать игру. В нашем случае никого баланса между стихиями так и не было достигнуто.
6. Фрилансеры имеют свойство пропадать. Очень неприятно, когда очередной комплект вещей ждешь два месяца...
7. Сделать качественную модерацию в игре очень сложно. Все люди в какой-то мере неадекватны, и если их сделать модераторами, это быстро проявляется.

Еще очень важно потратить время на создание админки. Для сравнения - в ИКНН все квесты целиком пишутся кодом. У нас все разговоры, фразы, переходы, требования, пункты в дневнике, и базовые действия вроде "добавить игроку вещей" или "установить игроку триггер 121" делались через интерфейс админки. По большому счету к коду прибегали только когда в квесте надо было либо сделать нестандартную логику (НПЦ появляется только с 2 до 6 дня допустим), либо когда надо было вставить в квест миниигру.
При этом я делал в ИКНН квест, на который я потратил почти неделю чистого времени, и который в Алидерии я бы почти целиком просто вбил в админке.
Аналогично, по ходу управления игрой постойнно приходится добавлять или забирать у игроков вещи, деньги, заклинания, выкидывать их из клана (глава пропал допустим), расформировывать кланы, выкидывать игроков из зависших боев, перекидывать игроков из локации в локацию. Хорошее правило, которому я следовал - если какое-то действие пришлось сделать трижды, надо его добавить в админку.

Игра наша просуществовала на протяжении двух лет. Кода за это время было написано тонна, картинок куплено еще больше. Мы выбрали вариант развития в ширину, а не в глубину, вводя новые квесты, локации, возможности. Тем самым постоянно портя еще сильнее и без того отсутствующий баланс.

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

Я упоминал выше про взломы игры. Конечно, любой взлом игры происходит из-за ошибки программиста. Из самых тупых взломов я помню следующий:
Когда игрок авторизуется в игре, мы ему присваиваем номер сессии, который в сущности просто является случайным числом, возвращенным функцией mt_rand(). Очевидно, код авторизации был написан одним из первых, то есть за три года до открытия игры, даже раньше, и в нем как-то получилась в то время очень странная конструкция
mt_srand(time());
session_id = mt_rand();
Теперь, мы видим, что перед генерацией сессии инициализируется seed, и инициализируется он на основе текущего времени с точностью до секунды. Добавим к этому, что в Алидерии в информации любого игрока можно увидеть как он давно онлайн с точностью до минуты, а в углу главного экрана игры есть часы с текущим временем на сервере. Хакеру было достаточно перебрать всего 120 значений зерна, чтобы подобрать id сессии нужного ему игрока. В роли нужного ему игрока выступил я, с доступом к админке :о)
Важный урок, который я после этого вынес - не надо размещать ссылку на админку прямо в игре :о Так бы может, взломав меня, он бы хотя бы не нашел как до неё добраться. В админке после этого он сделал только одно действие - поставил админские права своему персонажу. И всплыло это только через две недели.

На последок скажу несколько советов из полученного опыта тем, кто сейчас думает в эту сторону.
1. Когда вы начинаете проект, есть большой шанс, что через месяц он вам будет не интересен, и вы будете хотеть написать уже совсем другой проект, а код текущего будете считать грязным и ужасным (хотя навреное у крутанов нет такой проблемы). Разумно, однако, продолжать работать над текущим проектом.
2. Имеет смысл перед началом работы над сложным проектом написать сначала что-то простое на той технологии, которую вы планируете использовать (например, напишите Марблс). Это откроет вам глаза на многие проблемы, о которых вы не догадываетесь.
3. Игроки не любят сложную игру. Если вы сделаете Magic The Gathering Online, и игру, в которой есть только кнопка "Получить +10 опыта", вторая будет популярнее, и принесет больше прибыли. Ботва - хорошее тому доказательство :о)
4. И, конечно, запуск игры стоит денег. Как минимум на содержание сервера и покупку рекламы. Это с предположением, что у вас есть команда, покрывающая все необходимое в игре. Иначе надо еще рассчитывать бюджет на покупку недостающего контента. Прежде чем тратить значительные усилия на разработку, убедитесь, что ваше финансовое положение позволит потом проект запустить.

 

Read more »

 
 
 
 
  • Vote: I like it
  • +74
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,

Внимание! Шестиминутный лимит был убран - у вас есть время до трех ночи по МСК чтобы послать ваши решения, если вы не успели послать сразу, допустили ошибку, или скачали тест, не зная, что о существовании шестиминутного лимита.

1. Что мне делать, когда я открыл dashboard?
Нажать на название задачи слева, и затем НЕ НАЖИМАТЬ на кнопку Download Input. Можно прочитать все задачи, прежде, чем начинать их писать.

2. Я  прочитал вторую задачу и не понял ее, это нормально?
Это нормально. Ненормально наоборот.

3. Откуда мне читать данные и куда мне их писать?
Как и на GCJ, вы отправляете только ваш аутпут. Откуда вы читаете данные и куда пишете - не важно, до тех пор пока вы можете передать выкаченный из интернета файл вашей программе, и загрузить полученный вывод обратно в интернет.

4. Я дописал решение, и я уверен, что оно верное (= я не пытаюсь просто отсортировать строки в третьей задаче). Что дальше?
Дальше надо нажать Download Input. Ваш браузер куда-то скачает файл. Кнопка сделана убого, поэтому лучший вариант нажать по ней правой кнопкой и выбрать Save Target As (Save Link As или как это может еще называться я вашем браузере). С этого момента у вас начнутся шесть минут, причем вероятность, что вы сможете увидеть таймер, очень низка - шесть минут надо держать в голове. Запустите ваш код. Как только ваш аутпут готов, скопируйте его в буфер обмена, вернитесь в окно с HackerCup, и нажмите Submit Answer внизу. Вставьте output, нажмите ОК.
Вы не получите подтверждения о том, получил ли сервер вашу посылку.

5. Я сделал все, как описано выше, но когда таймер закончился, я увидел фразу Time Expired. Это нормально?
Это нормально. Ваше решение учтено.

6. Меня нет в таблице результатов, что мне делать?
Эту проблему сообщают еще N-10 человек. Facebook разбирается.

7. В FAQ сказано, что надо отправлять Source Code. Куда его вставлять?
В этом раунде не надо отправлять Source Code.

8. Если я нажму Download Input в течение шести минут повторно, скачается другой тест?
Нет, ваш тест не меняется между нажатиями Download Input.


Очевидные вещи:
У вас есть ОДНА попытка сдать задачу. Протестируйте ваше решение очень хорошо. Напишите альтернативное решение, чтобы при скачивании инпута проверить на нем мелкие тесты, и убедиться, что они сходятся с вашим основным решением. Шесть минут может оказаться достаточным, чтобы найти и исправить ошибку.

 

Read more »

 
 
 
 
  • Vote: I like it
  • +82
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Их есть у нас!
Если вы знаете (PHP или NodeJS) и ActionScript, и хотите применить эти знания на деле, и получить за это денежное вознаграждение, немедленно напишите мне на почту skidanovs@gmail.com :о)

Если вы не знаете ActionScript - это не беда, пишите, научим.
Если вы не знаете NodeJS, и хотите его выучить - тем более пишите, тем более научим.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Вышел новый эпизод айтишников (IT Crowd) - первая серия четвертого сезона. Там обоссаться можно от некоторых моментов :о)

http://vkontakte.ru/video19091867_146612299

П.С. Если вы еще не смотрели айтишников, то вы вообще зря жизнь прожили, и это надо исправлять :о Серии про скринсейвер, интернет и ограбление (особенно про то, как парни будут прятаться от ментов) вам вообще снесут мозг :о)

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Че-то я почитал решения на 1000 на TopCoder Open Online Round 1 и заметил, что оказывается, многие не умеют писать "не обязательно максимальный поток минимальной стоимости", как в транспортной задаче - то есть когда первичный критерий - минимальной стоимости, а не максимальность потока. Я увидел много решений, где люди перебирали размер потока и запускали несколько mincost maxflow - это же не надо так делать :о

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

Read more »

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,

Вступление

ICFPC – это контест, на котором команды в течение трех суток пытаются решить какую-то одну забавную задачу по программированию. Язык программирования, который использует победившая команда, признается лучшим языком программирования года до следующего контеста. Я о соревновании узнал впервые в начале этого года, случайно увидев ссылку на него на википедии со статьи про TopCoder, и очень захотел попытаться в нем принять участие. В тот момент информации о контесте 2010 еще не было, а потом я че-то зафтыкал и забыл. Так бы я его в общем-то и пропустил, если бы мой бывший одногруппник Кирилл не написал мне на Вконтакте, что он собирает команду для участия в нем, и приглашает меня принять участие.

 Я относился к этому скептически, потому что собственно я хотел писать на C#, а ребята собравшиеся в той команде – линуксоины.  Моно все еще нормально .NET 4.0 не поддерживает. Или, по крайней мере, найти такое Моно, не очень легко. Но вариант писать с командой победил просто потому что это казалось более интересным. Про язык пока думать не хотелось. В команде два человека писало на Ruby, и один на С++.

Готовясь к контесту мы завели, как видимо и почти все команды, хранилище кода н github, завели дашборд на EtherPad, настроили Jabber-конференцию (Все-таки в конце концов мне пришлось его завести. Оказалось безболезненно – в миранде он как выяснилось есть по дефолту, без необходимости ставить плагины :о))

Контест по моему времени начинался в пять утра в пятницу. Я встал где-то около семи...

День первый, Пятница

Согласно описаниям прошлогодних контестов в блогах, обычо условие задачи занимает 20 страниц. В этот раз, когда я открыл его, и увидел, что скроллбар сравнительно большой (= документ маленький), я был приятно удивлен. Ну это было преждевременно.

Итак, чтоже от нас хотят. Ссылка: (http://icfpcontest.org/2010/task/) У нас есть машины и топливо. Машина состоит из чемберов, чемберы состоят из двух пайплайнов – верхнего и нижнего. Пайплайн по существу – лист чисел от 0 до 5. Так же каждый чембер является либо основным, либо нет.

Топливо – это от одной до шести квадратных матриц произвольного размера.

Грубо говоря, числа в пайплайне – это номер матрицы. Топливо подходит машине, если для любого чембера умножение любого вектора А на произведение матриц в верхней пайпе всегда вернет вектор, где каждый элемент не меньше, чем в векторе, полученном при умножении вектора А на произведение матриц в нижней пайпе. При этом, если чембер является основным, то первый элемент результирующего вектора для верхней пайпы должен быть строго больше, чем первый элемент для нижней не зависимо от входного вектора. Подразумевается, что все элементы А не отрицательны, а первый элемент положителен. Более того, требуется, чтобы в процессе умножения входного вектора на каждую матрицу слева на право первый элемент никогда не становился нулем.

После прочтения этого это можно сразу забыть на пару дней :о) Потому что дальше начинается самая жопа. И машины и топливо задаются в тернарном формате. Про него известно то, что он тернарный, описывает числа, листы и туплы, и что он может описывать бесконечно большие числа и бесконечно длинные листы. И все :о Ну и еще у вас есть пример машинки, описанной в тернарном формате, но не более того. В этом и есть весь шарм ICFPC и его отличие от соревнований типа SRM или Marathon – вы даже не знаете, ЧТО вам надо решать :о)

Далее, на этом организаторы тоже решили не останавливаться. Чтобы делать топливо, нужно строить фабрики. Фабрика – это граф, где у каждой вершины (гейта) есть два входящих ребра, и два исходящих (порядок ребер важен – то есть если поменять два входящих ребра местами, получится другая фабрика). Порядок вершин тоже важен: если ребро идет из вершины с меньшим номером в вершину с большим, то результат передастся моментально, иначе только на следующий такт.

Ну и фабрику надо выводить в специальном формате, который тоже не описан, но дан пример фабрики, описанной в нем. Также дана последовательность. Скармливание этой последовательности на данную фабрику даст нам некоторую ключевую последовательность. Любое топливо должно начинаться с ключевой последовательности.

Важно также, что на сервере фабрики запускаются поверх другой входной последовательности.

Многое не понятно? Не беда, мы чуствовали тоже самое :о)

Задача контеста – засылать топливо для существующих машин. Точнее, засылать фабрики, которые его производят. Чем меньше команд кроме вас поставляют топливо для заданной машины, тем больше профита вы будете получать за нее каждые 15 минут. Чем короче фабрика (чем меньше у нее вершин), тем больше вы будете получать профита с нее.

Окей. Задачу прочитали, надо думать :о) Все что у нас есть в начале – это возможность засылать фабрики на сервер и смотреть, какой тернарный аутпут она дает, если на вход ей подана секретная входная последовательность, лежащая на сервере.

Собрав несколько фабрик руками, мы поняли, что без визуального редактора нам не жить. Как написать визуальный редактор, чтобы он запускался и у меня на винде, и у ребят на линухе? Qt мы допустим не знаем. Ок, на ум пришло JavaScript + HTML5 Canvas Firefox-то есть у всех.

Начинаю писать. Время где-то 9:15 утра. В 10:00 утра на работе митинг. Пытаюсь успеть, но необходимость позавтракать, умыться, и, собственно, дойти до работы, сыграли свою роль.  Я успел буквально только набрать в Bing html5 canvas tutorial” и по уроку сделать, что клики по канве рисуют гейты, складывая их в массив.

Дальше я бегу на работу, митинг проходит не очень продуктивно, так как я, под видом записей заметок, обсуждаю с ребятами фабрики в джаббере :о)

После митинга я за час заканчиваю редактор фабрик (да, это оказалось не так просто :о)), и мы начинаем тестировать. Не очень быстро, но становится понятно, что гейт – это функция тернарная функция f(x,y)=>(x,y), и мы постепенно начинаем восстанавливать  эту функцию засылая разные фабрики. Когда функция восстановлена, я прикручиваю к нашему редактору на JavaScript эвалуейтор фабрик, который по последовательности на входе и фабрике генерит ее выход. Получаем “key sequence” – тернарку, которая должна идти в начале любого топлива. Вот это уже было тупо. Редактор на JavaScript было премлемо, но любой код, который может пригодиться потом – это было тупо. В это же время примерно один из участников команды – Бегемот, расшифровывает входную последовательность на сервере, но у него отпадает интернет, и он не успевает ее послать. Я расшифровываю ее тоже мелкой кодякой на С++, и успеваю как раз к моменту, когда он входит в интернет, и мы одновременно почти отправляем ее в Jabber :о)

Теперь задача найти фабрику, которая будет генерить эту последовательность. Вот тут настал тупняк. Ребята ушли уже спать, а я начал думать. Брутфорс писать было лень (и слава богу, потому что в этот момент я не знал, что потом надо будет делать фабрики для производства топлива длиной под тысячу символов, которые бы не брутились). Начал выводить фабрики, которые не зависимо от входа будут делать нужный выход. Научился делать два блока – один возвращает ноль, а затем поданную на вход последовательность, другой – получает на вход последовательность и возвращает ее, увеличенную на один. Первый из шести гейтов, второй – из десяти. Их комбинации, очевидно, могут создать фабрику для любой последовательности. Тока фабрика будет иметь длину, в 20 раз большую длины входной последовательности :о)

Пишу на JavaScript конвертер выходной последовательности в фабрику (ну опять, почему JavaScript???), и засылаю ее на первую машинку. Команда получает 0.014 баллов :о) Я писаюсь кипятком – у нас не ноль :о)

На другие машинки не засылается. Теперь надо думать над тернаркой. Сразу бросается в глаза, что часто встречаются две подряд идущие двойки. Кроме того, почти все машинки начинаются с двух двоек и заканчиваются 10. Казалось бы, 22 – начало листа, 10 – конец. Но не работает. Да и есть машинка, заканчивающася не на 10, а самые простые машинки начинаются не на 22, а на 1.

Проблема еще в том, что префикс, который должен быть в начале каждого топлива, вообще не похож на описание машинок, а ведь по логике он должен быть в том же формате.

До ночи ничего не придумываю, ухожу спать с надеждой, что ребята расшифруют.

День второй, Суббота

Утром тернарный формат еще не был разгадан. И никаких зацепок не было.

В девять утра был первый отборочный на топкодер, и я решил поискать подсказок в чате. Один чувак отозвался на фразу IFCPC, и в диалоге с ним я прозрел. Префикс у топлива не является вообще валидной тернарной строкой, и описание топлива идет после префикса, а не начиная с него! Это даже прямым текстом указано в условии, но че-то я затупил. С этой информацией Бегемот засылает наконец-то топливо на хоть какую-то машину, кроме пустой, просто перебирая текст после конца префикса. Кирилл пишет на Ruby бота, который рассылает это топливо на все тачки, и он подходит на неслабое их количество. Баллы начинают течь рекой! Конечно, не сравнимо с другими командами, которые так долго не тупили.

Следующее прозрение происходит, когда мы понимаем, что если подать валидное топливо (а у нас теперь есть хотя бы одно такое), то можно изучать ошибки парсера машинки. Ошибки были четырех типов: «ожидается 0, 1 или 2, а обнаружен конец», «ожидается 2, а обнаружен конец» и «ожидается 0, 1 или 2, или число здесь должно быть 0 или 1, а обнаружен конец». Третья ошибка выносит мозг. Ожидается 0, 1, 2, 0 или 1? Что это значит? Иногда пишет, что машинка валидна, но что-то с ней не так: нет ни одного мейн чамбера, или топливные баки не соединины (там есть определенное правило по соединению топливных баков). Долго, очень долго, мы втупляем, каждый сам по себе, иногда кидая мысли в джаббер. Копим разные последоавтельности с ошибками, составляем полный список. Спустя пол дня, где-то после обеда уже, я нахожу машинку, которая пишет «не соединен 0 бак сам с собой». Замена на конце нуля на 10 меняет ошибку на «не соединет нулевой с первым». Начинаю перебирать и умудряюсь восстановить формат представления чисел. Awesome. Перебираю еще пол часика и понимаю весь формат. Я не мог поверить своему счастью. Конечно, когда он уже расшифрован, он кажется очень простым :о) И он реально крут. Мы готовы приступить к непосредственно задаче. Прошло всего полтора суток из трех :о)

Сразу пишется на JavaScript (ну твою ж за ногу) парсер машинок из тернарки в JSON и парсер топлива из JSON в тернарку и сразу в фабрику.

Кирилл улучшает скрипт, чтобы тот рассылал больше типов топлива, и уходит спать. Скрипт убивается через 10 минут после этого, когда сервер вернул 503. Не очень Robust :о)

Сначала я решаю руками некоторые простые машинки, где матрица имеет размер 1 на 1 (открыть машинку, подать ее на парсер, подумать, написать JSON топлива, закодить в фабрику, заслать – автоматизацией не пахнет :о)), пока не нахожу машинку 13252. Смотря на нее я понимаю, что некоторые числа в описании топлива в решении могут быть очень большими, знаков по 100. И мое решение на яваскрипте явно не способно их обрабатывать. Приходится переписывать половину кода на Java – потеря времени -  с BigInteger, с осознанием того, насколько изначально было тупо писать все на JavaScript. Теперь весь код, уже готовый, невозможно использовать, потому что JavaScript даже не научишь писать в файл/читать из файла. При этом конвертор в фабрики я не переношу, и автоматизация все еще хромает, так как надо сконвертить машинку в JSON на стринчке, запустить ява-приложение, и опять на страничке сконверить аутпут в фабрику.

После этого я решаю все машинки вида 13252, и на этом получаю сильный старт – такие машинки к тому времени решены 6-7 командами, а значит баллов за них дают неплохо. Обгоняю постепенно в таблице результатов соседние команды, спустя какое-то время мне уже не надо проматывать странцу чтобы найти нас :о)

Далее вырисовывается несколько путей развития:

1.      Улучшить наши фабрики – сделать их покороче, чтобы баллов за них капало побольше

2.      Написать решалки каких-то базовых машинок

3.      Или сделать свои машинки

Я выбрал третий путь, и начал делать машинки, выбирая несколько больших степеней двойки, и рисуя семь чемберов, которые, видимо, можно будет решить только подобрав эти степени двойки. Засылаю одну такую машинку, и ее почти сразу решает пять команд...

Это не беда, увеличиваю ограничение, засылаю снова. В этот раз почти успех, только через пару минут решила одна команда, и еще попозже вторая. Затем много минут новых решений не поступает, и я убеждаю уже проснувшихся ребят заслать такие машинки под лимит, и сосредоточиться на решении чужих до конца соренования. Сам засылаю машинок 30, и ухожу спать, время уже за полночь. Перед сном успеваю пронаблюдать, как наша команда начинает взлетать в таблице результатов, обходя тонну соперников. Кирилл в этом время добавляет в бота две новых фабрики, которые решают еще больше нубских машинок.

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

День третий, Воскресенье

С утра мы уже на 14-ом месте с 300К очков, наши машинки уже решило по 5-6 команд не считая нас, и к списку решенных нами машинок добавилось порядка 60 нубских. Мы все еще растем неплохими темпами (не смотря на то, что наши машинки научились решать).

Я ухожу смотреть матч Бразилия – Ивори Коаст, а ребята продолжают улучшать бота и думать. Просмотр матча в баре без выпивки не удался, и вернулся я в состоянии, не пригодном для решения задачки. Однако новости хорошие – Бегемот придумал новый способ генерить фабрики, который позволит делать фабрики в 10 раз короче!

Сервер соревнования лежит. Администраторы, видя это, дают несколько вспомогательных ссылок, среди них полный список машинок с длинами всех решений, где мы видим, что наши решения самые длинные (и, как следствие, приносят меньше всего очков). 

В это время я начинаю писать брут для топлива на C# (как хорошо, что в .NET 4.0 есть BigInteger), который перебирает одноингридиентные топлива с кажным элементом от 1 до 10. Парсер написался легко, но попытки найти машинку, которую бы он решал, заканчиваются буквально нахождением двух трех.

При этом копировать аутпут брута на JavaScript страничку, чтобы сконвертировать топливо в фабрику, очень неудобно, и встает необходимость перенести конвертор топливных фабрик на C#. Раз уж надо переносить генератор, решаю сразу писать идею Бегемота. Это занимает ужасное количство времени (вероятно не последнюю роль в этом сыграл побочный эффект матча Бразилия – Ивори Коаст), но в конечном итоге новый конвертор топлива в фабрики, готов.

Затем запрос “C# WebRequest” в Bing и 30 минут учат софтинку грузить список машинок с сервера, грузить машинки, брутить их, конвертить и засылать, и за несколько минут количество решенных нами машинок увеличивается в 1.5 раза! :о)

При этом софтинка перепосылает все уже решенные нами машинки с более короткими фабриками.

Теперь внимание вопрос. Почему я написал брут форс, а не линейное программирование, если даже ребенку очевидно, что это – задача на линейное программирование? Большинство конкуретнов, которые нас потом обошли не очень сильно, разумеется написали ЛП.

Вечером, когда ребята проснулись, возникает печаль. Mono с .NET 4.0 не так-то легко найти. Они оба не могут запустить мою софтинку. Я генерирую у себя на машине все простые топлива, чтобы Кирилл добавил их в свой скрипт. Теперь на новые машины сразу засылается новое топливо. К сожалению, мой C# кодяк в отличие от бота Кирилла, не запоминает решенные машинки, и каждый раз идет по всему списку. Чтобы он как-то все-таки решал свежие машинки, я запускаю его восемь раз с разным стартовым отступом. Оборачиваю пол кода в try-catch, чтобы не повторить подвиг Кирилла с падением через 10 минут. Ухожу спать в полночь, до конца контеста пять часов.

Ночью происходит забавный момент. Во-первых, уже с вечера многие команда, похоже, написали ЛП-солвер, и начали очень быстро расти. И конкуренция в последние часы просто дикая. Нас рвет SnakeTeam, которую Бегемоту было принципиально порвать, и дерет нас за счет... своих машинок! Потому что 1000 решенных простых машин дает порядка 10 баллов за прирост, в то время как 72 своих (72 - лимит), которые решит одна команда кроме вас, дает 30 баллов за прирост! Прогадал я, однако, с засылкой машинок под лимит раньше времени.

Так вот, забавный момент. Была под нами команда SzM – стыдно за МГУ. Бегемот открыл ихнюю машинку, прочитал, и понял, что он знает как ее решать, в тоже время, наши боты пока ее не умеют делать. Он решает ее, и решает все машинки SzM. В итогде, в конце контеста SzM за нами с минимальным отставанием :о) Получается ихние же машинки не дали им нас обойти :о)

В итоге мы на 19-ом месте. Вокруг невероятная концентрация российских команд: над нами TBD, повыше SnakeTeam, под нами Стыдно за МГУ, jabber-ru.

Вот в общем такая история. Основные уроки, которые были вынесены:

1.      Подумай 10 раз на каком языке пишешь.

2.      Не пиши на JavaScript :о)

3.      Внутри команды используйте один язык программирования :о)

 В следующем году обязательно буду писать снова :о Никакие из соревнований, где я участвовал прежде (кроме конечно ICPC 2008 - с этим ничто не сравнится :О)) по накалу страстей даже рядом, по-моему, не стояли :о)

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
http://icfpcontest.org/2010/

Ежегодный контест, очень клевый. Я участвую впервые в этом году, и за те несколько часов что он идет я убедился что это просто охренеть :о)
Длится трое суток, так что никогда не поздно присоединиться :о)

Контест закончился, таблица результатов начиная с шестого места:
http://icfpcontest.org/icfp10/score/teamAll

Read more »

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Мужики, я по-моему нашел статую снарка :о


Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
На топкодере на форуме мне понравился состав сборной Канады на IOI в этом году

Canada's official team:
hpmv (Robin Cheng)
bbi5291 (Brian Bi)
SourSpinach (Jacob Plachta)
Zhiqiang (John) Liu

Unofficial team:
cyril (Cyril Zhang)
aurickQ (Aurick Qiao)
Tyson Andre
Jonathan Zung

Интересно, Jacob и Tyson не чуствуют себя здесь не к месту? :о

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Раз уж эта тема просочилась сюда, то непременно надо опубликовать наш ответ на операционную систему BolgenOS.
http://www.youtube.com/watch?v=64GjZiNHl4w

Read more »

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Анонс: 24.05.2010 (пн), 20:00 на сервере личных соревнований SnarkNews пройдёт экспериментальный индивидуальный турнир. Турнир будет проведён по системе TCM, которая будет использоваться на "Яндекс Open 2010". Продолжительность турнира - 1 час 20 минут.

(с) SnarkNews

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

Мне одному кажется, что в этом соревновании будет просто невероятно заруливать удача? По-моему совершенно любой человек может накосячить на любой задаче с каким-то шансом. Очевидно, что по простой задаче никто никогда в такой системе не отправит в светлую - это тупо. Значит все почти участники поощрительные задачи будут сабмитить в темную.
У трети из них она не пройдет, и это сразу совершенно случайным образом даст кому-то фору в 1.5 поинта :о Если простых задач парочка, то это еще круче раскидает людей.
Было бы еще разумно, если бы у задач были какие-то назначенные им поинты, и падение простой задачи не равнялось бы по поинтам падению гроба, а в таком виде это будет полюбому лотерея.

Вообще возникает устойчивое ощущение, что снарк не любит штрафы. Те, кто писал в его системе АСМ+ думаю помнят, что там штраф полностью лишает вас возможности бороться за призовые места с теми, кто штраф не сделал :о

А еще интересно, что же вообще значит TCM. Это типа TC и ACM вместе? От TC получается взяли только проверку в конце? Или это как-то по умному еще расшифровывается?

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
Разберу некоторые задачи.

Простые я многие не решал, так как во время тура не мог писать нормально, а на дорешивании это не очень интересно, но общая идея такая:
C кажется просто надо сделать что написано
F видимо дийкстра
G это поощрительная задача
и J - есть острое сомнение, что на Java и BigDecimal сдается моментально.

Задача B.
Решать будем для каждой отдельной компоненты связности.
Сначала избавимся от очень дурацкой вещи - вершин со степенью один. Легко доказать, что если степерь вершины равна единице, то и степень смежной ей вершины тоже единица. Отлично :о) Это мы покрасить можем.
Теперь полагаем, что степень всех вершин не единица.
Возьмем произвольную вершину, и покрасим ее в первый цвет. Возьмем любую смежную с ней вершину, и покрасим во второй. Теперь будем до победного делать очевидную вещь - если у вершины есть смежные ей двух разных цветов, красить ее в третий.
Теперь легко доказать, что это покрасит всю компоненту связности. Пусть это не так. То есть в какой-то момент времени мы остановились, и осталась хотя бы одна вершина, не покрашенная. Очевидно, что тогда есть ребро, связывающее покрашенную и не покрашенную вершину. Пусть покрашенная вершина - А, а непокрашенная - Б. Так как А покрашена, у нее есть две смежных вершины ей двух других цветов (иначе почему бы мы покрасили А?), возьмем только одну из них, другая нас не интересует. Пусть эта вершина - В. То есть мы имеем вершину А одного цвета, смежную ей вершину В другого цвета и смежную вершине А вершину Б не покрашенную. В и Б не обязательно смежны, но! между В и Б есть путь, пролегающий через вершины, смежные А (по условию того, что все вершины, смежные с А, образуют связный граф). Пусть эта цепочка В-Х1-Х2-Х3-Б. Обратите внимание, что мы можем ее покрасить. Х1 смежна с В и А, которые разных цветов, и потом красится в оставишйся, аналогично красится Х2, далее Х3, и наконец, Б. То есть Б не могла остаться не покрашенной.
В общем задача требует от нас покраски в лоб по большому счету.

Задача D
Первое наблюдение - оба дуэлянта никогда не зайдут в одну боковую аллею, так как это pointless. Если дуэлянт входит в аллею, где сейчас другой дуэлянт, это странно - они тогда точно столкнуться, в тоже время не войдя в нее мы гарантированно избежим столкновения.
Если дуэлянт входит в аллею, где был другой дуэлянт прежде, то значит они уже разошлись - это вообще не имеет смысла рассматривать :о)
То есть до момента, когда дуэлянты столкнутся или разойдутся, каждая боковая аллея будет посещена максимум одним из них. А значит решать можно так:
1. Закрепим за 2^20 в какие из боковых аллей хотя бы один дуэлянт войдет
2. Создадим четыре типа событий (первый дуэлянт вошел в аллею, второй дуэлянт вошел в аллею, первый вышел ,второй вышел) и пойдем по событиям, пока либо второй не окажется выше первого без столкновения, либо пока они не столкнутся.

Задача E.
Для каждого отрезка АВ построим прямую, перпендикулярную ему и проходящую через точку А, и другой, проходящий через точку В. Для каждой такой прямой будем хранить два списка перпендикулярных ей отрезков - те, у которых левый конец лежит на этой прямой, и те, у которых правый конец лежит на этой прямой. Для вертикальных отрезков, у которых нет левых и правых концов, соответственно будем брать нижний и верхний.
Для каждой прямой оба списка должны быть отсортированы по удалению лежащего на этой прямой конца отрезка до какой-то очень далекой точки на этой прямой.
Теперь рассматриваем каждый отрезок СД. Для скольких букв Ш, у которых торчалки идут вправо (или если лежачая палочка строго горизонтальная, то идущих вверх) она будет лежачей палочкой? Очевидно, чтобы посчитать это, надо понять
а) У скольких отрезков левый конец лежит на этой прямой, в точности в точке С
б) У скольких отрезков левый конец лежит на этой прямой в точности в точке Д
в) У скольких отрезков левый конец лежит на этой прямой между точками С и Д.
И перемножить эти три числа.
Так как мы знаем все отрезки, у которых левый конец лежит на прямой, содержащей СД, и они у нас отсортированы, ответить на все три вопроса кажется не очень сложным.
Аналогично считаем, сколько букв Ш идут в обратную сторону от закрпленного отрезка. Рассматриваем так каждый отрезок в роли лежачей палочки, суммируем ответ. Получается что-то вроде N log N.

Задача I (разбор предоставлен Сергеем Штейнером)
Нам нужно вычислить сумму весов остовных деревьев, делённую на их количество. Вычислим для каждого ребра, какой вклад оно даст туда. Понятно, что i-е ребро появится в сумме N - N_i раз, где N - количество остовных деревьев вообще, а N_i - количество остовных деревьев, не содержащих i-е ребро, то есть количество остовных деревьев в графе с удалённым i-м ребром. Заметим, что для всех рёбер, инцидентных одной и той же паре вершин N - N_i одно и то же. Итак, осталось научиться вычислять количество остовных деревьев в мультиграфе. Тут нам на помощь приходит матричная теорема Кирхгофа:
http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%8...
Теперь мы перебираем все пары вершин и за O(n^3) считаем ответ для каждого ребра. Итоговая сложность O(n^5).

Задача К.
Нам нужна структура данных, позволяющая удалять один элемент, и говорить в какой позиции находится K-ый максимальны, и выполнять оба действия быстро.
Чтобы сделать это можно поддерживать два дерева, которые говорят, в каких позициях в оригинальном массиве нет уже элементов, и в каких позициях в отсортированном массиве нет элементов. Первое дерево позволяет по сдвинутой позиции получить оригинальную позицию (это надо для удаления, чтобы понять какой же элемент удалить), второе - ответить на вопрос, какое же сейчас число I-ое по величине.
Оба действия получаются log n


Задачу А более менее кажется понятным как решать - в каждый момент времени возможные позиции наших войск - это многоугольник с вырезанными дырами. С ходом времени все вершины внешнего многоугольника двигаются по диагонали в сторону расширения, а всех дыр - по диагонали в сторону уменьшения дыры. Когда происходит взрыв, надо улучшить многоугольник, вырезав из него квадрат, который взорвали, и так дальше продолжать. Это видимо самая сложная чась.
Или я не прав?

Задача H мне очень интересна after all :о)

Read more »

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

By ItsNear, 9 years ago, In Russian,
I just want to remind everybody, that registration for GCJ 2010 ends in less than a day, and the first qualification round is already being run.

Don't miss it. You can find additional information here:
http://code.google.com/codejam

Read more »

Tags gcj
 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it