### SkidanovAlex's blog

By SkidanovAlex4 months ago, ,

Hello everyone!

The second round of MemSQL start[c]up will take place on August, 3rd, 10:00am PDT. There will be two contests running simultaneously, one for people who participate onsite, and one for everybody else who advanced to the round two. Both rounds share the problemset and are rated based on the combined scoreboard.

Onsite participants will have special prizes for first three places. All onsite participants as well as the top 100 in the online contest will receive a start[c]up t-shirt.

People who have not advanced to the round two can participate in the round unofficially. Unofficial participation will be rated.

The contest will be 3 hours long, and will feature 6 problems. The score distribution is 500-1000-1000-2000-2500-3000.

The problem set has been developed by MemSQL engineers pieguy, nika, exod40, SkidanovAlex and dolphinigle.

Good luck and happy coding!

UPDATE: Editorial is up!

Announcement of MemSQL start[c]up Round 2

•
• +138
•

By SkidanovAlex5 months ago, ,

Square and Rectangles

Author: SkidanovAlex

What happens if the rectangles form an N × N square? Then these two conditions are necessary.

1) The area must be exactly N × N.

2) The length of its sides must be N. That means, the difference between the right side of the rightmost rectangle — the left side of the leftmost rectangle is N. Same for topmost and bottommost rectangles.

We claim that, since the rectangles do not intersect, those two conditions are also sufficient.

This is since if there are only N × N space inside the box bounded by the leftmost, rightmost, topmost, and bottommost rectangles.

Thus if the sum of the area is exactly N × N, all space must be filled -- which forms a square.

Author: nika

Suppose the "divide-by-two" stage happens exactly D times, and the round robin happens with M people.

Then, the number of games held is:

We would like that

This is an equation with two variables -- to solve it, we can enumerate the value of one of the variables and calculate the value of the other one. We cannot enumerate the possible values of M, since M can vary from 1 to 10^9. However, we can enumerate D, since the number scales exponentially with D -- that is, we should only enumerate 0 ≤ D ≤ 62.

Thus, the equation is reduced to

Since this function is increasing, this can be solved via binary search on M.

Monsters and Diamonds

Author: SkidanovAlex

First part of the problem is to find minimum number of diamonds one can achieve by starting with a given monster. To do so, we will be using Dijkstra algorithm. Originally we don't know the minimum for any monster. For every rule we will maintain how many monsters with unknown minimums it has (let's call it ki for the i-th rule). Let's take every rule that has only diamonds in it (i.e. which has ki = 0), and assign number of diamonds in that rule as a tentative minimum for the monster (if a monster has several diamonds-only rules, take the smallest one). Then take the monster, that has the smallest tentative minimum currently assigned. For that monster the tentative value is the actual minimum due to the same reasoning we use when we prove correctness of Dijkstra algorithm. Now, since we know the minimum for that monster, for every rule i that has that monster in its result subtract 1 from ki for every occurrence of the monster in the result of that rule. If for any rule the value of ki becomes zero, update the tentative minimum for the monster that rule belongs to with the sum of minimum values for each monster that rule generates plus the number of diamonds that rule generates. Then from all the monsters for which we don't known the minimum yet, but for which we know the tentative minimum, pick the one with the smallest tentative minimum, and continue on.

At the end we will end up in a state, when each monster either has an actual minimum value assigned, or has no tentative value assigned. The latter monsters will have  - 1 - 1 as their answer. For the former monsters we know the minimum, but don't know the maximum yet.

The second part of the problem is to find all the rules, after applying which we are guaranteed to never get rid of all the monsters. We will call such a rule bad. It is easy to show, that the rule bad if and only if it generates at least one monster with minimum value of -1. Remove all the bad rules from the set of rules.

When bad rules are removed, finding maximums is trivial. Starting from every node for which maximum is not assigned yet, we traverse all the monsters in a DFS order. For a given monster, we consider every rule. For a given rule, for each monster it generates, we call DFS to find its maximum value, and then sum them up, add number of diamonds for the rule, and check if this rule gives bigger max value than the one currently known for the monster. If we ever call DFS for a monster, for which we already have a DFS call on the stack, that means that that monster has some way of producing itself (directly or indirectly) and some non-zero number of diamonds (this is why problem statement has a constraint that every rule generates at least one diamond), so the answer for the monster is -2. If, processing any rule, we encounter a monster with max value -2, we immediately assign -2 as a max value for the monster the rule belongs to and return from the DFS.

As an exercise, think of a solution for the same problem, if rules are not guarantee to have at least one diamond in them.

Reclamation

Author: dolphinigle

Assume there's an extra sea cells on a row above the topmost row, and a row below the bottom most row. Hence, we can assume that the top and bottom row consists entirely of sea.

We claim that: There does not exist a sea route if and only if there exists a sequence of land cells that circumfere the planet (2 cells are adjacent if they share at least one point).

The "sufficient" part of the proof is easy -- since there exists such a sequence, it separates the sea into the northern and southern hemisphere and this forms a barrier disallowing passage between the two.

The "necessary" part. Suppose there does not exist such route. Then, if you perform a flood fill from any of the sea cell in the top row, you obtain a set of sea cells.

Trace the southern boundary of these set of cells, and you obtain the sequence of land circumfering the planet.

Thus, the algorithm works by simulating the reclamations one by one. Each time a land is going to be reclamated, we check if it would create a circumefering sequence. We will show that there's a way to do this check very quickly -- thus the algorithm should work within the time limit.

Stick two copies of the grid together side-by-side, forming a Rx(2*C) grid. The leftmost and rightmost cells of any row in this new grid are also adjacent, similar to the given grid.

Each time we're going to reclamate a land in row r and column c, we check if by doing so we would create a path going from (r, c) to (r, c + C). If it would, then we cancel the reclamation. Otherwise, we perform it, and add a land in cell (r, c) and (r, c+C).

This "is there a path from node X to node Y" queries can be answered very very quickly using union find -- we check whether is it possible to go from one of the 8 neighbors of (r, c) to one of the 8 neighbors of (r, c+C).

Correctness follows from the following: There exists a circumefering sequence IFF there exists a path from (r, c) to (r, c+C). Sufficient is easy. Suppose there exist a path from (r, c) to (r, c+C). We can form our circumfering sequence by overlapping the path from (r, c) to (r, c+C) with the same path, but going from (r, c+C) to (r, c) (we can do this since the grid is a two copies of the same grid sticked together).

Necessary. Suppose there exists a circumfering sequence. We claim that there must exist a path to go from (r, c) to (r, c+C). Consider the concatenation of an infinite number of our initial grid, forming an Rx(infinite * C) grid. If there exists a circumfering sequence, we claim that within this grid, there exists a path from (r, c) to (r, c+C).

Suppose there does not exist such a path. Since there exists a circumfering sequence, it must be possible to go from (r, c) to (r, c+ t * C), where t is an integer >= 2. Now, you should overlap all the paths taken to go from (r, c) to (r, c+t*C) in the grid (r', c' + C) (the grid immediately to the right of the grid where (r, c) is located). There must be a path from (r, c) to (r, c+C) in this new overlapped path.

Proofing the final part is difficult without interactive illustration -- basically since t >= 2, there exists a path that goes from the left side to the right side of the grid (r', c' + C). This path must intersect with one of the overlapping paths, and that path must be connected to (r, c+C). The details are left as... exercise :p.

The Red Button

Author: nika

In this part of editorial, all numbers we speak are in modulo N. So, if I say 10, it actually means 10 modulo N.

First, observe that this problem asks us to find a cycle that visits each node exactly once, i.e., a hamiltonian cycle. Thus, for each node X, there exists one other node that we used to go to node X, and one node that we visit after node X. We call them bef(X) and aft(X) (shorthand for before and after).

First we will show that if N is odd, then the answer is  - 1.

Proof...? Consider node 0. What nodes points to node 0? Such node H must satisfy either of the following conditions:

2H = 0

2H + 1 = 0

The first condition is satisfied only by H = 0. The second condition is satisfied only by one value of H: floor(N / 2).

So, since we need a hamiltonian cycle, pre[0] must be floor(N/2), and aft[floor(N/2)] = 0

Now, consider node N - 1. What nodes points to node N - 1?

2H = N - 1

2H + 1 = N - 1

The second condition is satisfied only by H = N - 1. The first condition is satisfied only by H = floor(N / 2)

But we need a hamiltonian cycle, so aft[floor(N/2)] must be N - 1. This is a contradiction with that aft[floor(N/2)] must be 0.

Now, N is even. This case is much more interesting.

Consider a node X. It is connected to 2X and 2X + 1. Consider the node X + N / 2. It is connected to 2X + N and 2X + 1 + N, which reduces to 2X and 2X + 1.

So, apparently node X and node X + N / 2 are connected to the same set of values.

Now, notice that each node X will have exactly two nodes pointing to it. This is since such node H must satisfy

2H = X

2H + 1 = X

modulo N, each of those two equations have exactly one solution.

So, this combined with that node X and X + N / 2 have the same set of connected nodes means that the only way to go to node 2X or 2X + 1 is from nodes X and X + N / 2.

Thus, if you choose to go from node X to node 2X, you HAVE to go from node X + N / 2 to node 2X + 1 (or vice versa).

Now, try to follow the rule above and generate any such configuration. This configuration will consists of cycles, possibly more than 1. Can we join them into a single large cycle, visiting all nodes?

Yes we can, since those cycles are special.

Weird theorem: If there are 2 +  cycles, then there must exist X and such node X and node X + N / 2 are in different cycles.

Proof: Suppose not. We show that there must exist one cycle in that case. Since node X and X + N / 2 are in the same cycle, they must also be in the same cycle as node 2X and 2X + 1. In particular, node X and 2X and 2X + 1 are all in the same cycle. It is possible to go from any node X to any node Y by following this pattern (left as exercise). Now, consider the X such that node X and node X + N / 2 are in different cycles. Suppose we go from node X to node 2X + A, and from X + N / 2 to 2X + B (such that A + B = 1). Switch the route -- we go from node X to 2X + B and X + N / 2 to 2X + A instead. This will merge the two cycles -- very similar to how we merge two cycles when finding an eulerian path. Thus, we can keep doing this to obtain our cycle!

...It's not entirely obvious to do that in O(N) time. An example solution: use DFS. DFS from node 0. For each node X:

• if it has been visited, return

• if X + N / 2 has been visited, go to either 2X or 2X + 1 and recurse, depending on which route used by node X + N / 2

• otherwise, we go to node 2X and recurse. Then, check if X + N / 2 was visited in the recursion. If it was not, then the two of them forms two different cycles. We merge them by switching our route to 2X + 1 instead, and recurse again.

•
• +61
•

By SkidanovAlex5 months ago, ,

Hello everyone!

The first round of start[c]up is upon us. It is open to all participants. Registration works as a normal CodeForces round, and will close five minutes before the start of the contest.

The contest uses normal Codeforces rules, and will be rated. The score distribution is 500-1000-2000-2000-2500.

The problem set has been developed by MemSQL engineers pieguy, nika, exod40, SkidanovAlex and dolphinigle.

Top 500 competitors will advance to the second round, with the top 25 Silicon Valley residents invited to participate on-site, where there will be special prizes.

Good luck and happy coding!

UPDATE: Please note that the score distribution has changed.

UPDATE: Editorial is up now!

Announcement of MemSQL start[c]up Round 1

•
• +165
•

By SkidanovAlex6 months ago, ,

MemSQL is happy to announce start[c]up -- a programming competition, hosted by Codeforces and MemSQL HQ located in San Francisco, California. start[c]up consists of two rounds.

All rounds will be prepared by MemSQL engineers: pieguy, nika, exod40, SkidanovAlex and dolphinigle.

Round 1 is online and takes place on July 13. Round 1 follows regular Codeforces rules and consists of 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. There are no eligibility restrictions to participate in the round.

Round 2 takes place on August 3, consists of 5 problems, and uses regular Codeforces rules. The complexity of the problems is higher than a regular Codeforces round. Only people who finished in the top 500 in Round 1 can participate. The top 100 in round 2 will receive a start[c]up T-shirt.

For the Silicon Valley residents, MemSQL will be hosting up to 25 people on-site during the second round. The winner of the on-site round will be awarded a special prize.

MemSQL is building an in-memory database that powers many well-known companies, such as Morgan Stanley and Zynga. Nearly half of our engineers are TopCoder Open Algorithm finalists in recent years, and we have more IOI and ICPC medals than we have engineers.

The reason for such a skew towards topcoders is that only very good engineers can build a database. Even though topcoders might not have skills necessary to build a database, they are known to be very smart. We’ve seen that smart coders can quickly acquire necessary skills, but average coders, regardless of experience, cannot learn to be smart.

We have lots of exciting problems for topcoders. For example SQL Query optimizer, cluster management for the distributed system, lockfree storage engine were all written by topcoders in here. If you are looking for an internship or for a full-time position and want to work on exciting stuff with people who are as smart as yourself, send your resume to topcoder@memsql.com.

•
• +304
•

By SkidanovAlex17 months ago, ,

Сегодня я хочу рассказать про Хакатоны – интересный вид соревнований по программированию, который заметно отличается от всего, к чему привыкли люди, которые занимаются спортивным программированием. Хакатоны весьма популярны во всем мире, они проходят с какой-то периодичностью и в России, и на Украине, а в кремниевой долине их особенно много. За последние полтора месяца я поучаствовал в четырех хакатонах, и остался невероятно впечатлен.

Хакатон в Nokia
Самый первый хакатон, в котором мне довелось поучаствовать, проводился компанией Nokia, и целью хакатона, как можно догадаться, было разработать приложение для Windows Phone 7. Длительность “coding phase” была восемь часов, и разрешалось приходить с готовыми наработками. У нас готовых наработок не было, так что вся подготовка заключалась в том, чтобы найти два ноутбука с Windows, и поставить на них Windows Phone 7 SDK. Так как это был наш первый хакатон, мы не знали, чего ожидать. Мы приготовили идею – мы хотели написать приложение, связывающее два телефона, и дающее им канву, на которой они оба могут рисовать. Идея не очень сложная, и не очень новая – она, например, реализована в Pair. На хакатон я пришел с супругой, которая у меня тоже программист. Ни я ни она из-за рода работы не работали на Windows к тому дню уже порядка года, поэтому рабочая станция была немного непривычной. Для начала мы открыли документацию “пишем Hello World для WP7”, которая описывала, как создать простейшее приложение для WP7. Так как технологии развиваются с невероятной скоростью, простейшее приложение – это не приложение с текстом Hello World посередине, а web-браузер. Пройдя каждый пункт документации у нас получилось приложение с компонентой WebBrowser на весь экран. Это подтолкнуло нас к идее, что все приложение можно написать на HTML5 Canvas, и затем просто воткнуть его в эту самую компоненту. Мы в конечном итоге так и сделали. Через четыре часа приложение было уже написано, и мы рисовали на общей канве с двух компьютеров. Сервер мы быстренько подняли на EC2, и написали на PHP – буквально два 10-строчных скрипта. Порадовавшись тому, что за четыре часа до конца у нас все работает, мы решили проверить все на эмуляторе телефона. Указали WebBrowser компненте загружать страницу на EC2, запустили приложение, начали рисовать пальцем, и… а тут все стало не совсем радужно. Когда на WP7 нажимаешь пальцем и начинаешь его двигать, он прокручивает страницу, и ни Mouse Down, ни Mouse Move события на странице не вызываются вообще. Существующие специально для этой цели Touch Start и Touch Move события на WP7 не поддерживаются тоже. Я нашел вопрос на Stack Overflow, где спрашивали, можно ли отключить прокрутку страницы в WP7, с ответом “мой знакомый работает в WP7, и ответ – нет”. Тут-то мы и поняли, что четыре часа стараний ушли в унитаз, потому что запустить наш HTML5 код на WP7 попросту нельзя. Но, конечно, мы были далеко не первыми людьми, столкнувшимися с этой проблемой, и в мире есть много энтузиастов, которые так просто не сдаются. Порыскав поглубже в интернете я нашел двух ребят, которые через Reflection смогли найти во внутренностях WebBrowser часть, отвечающую за прокрутку, и собрали пример того, как ее оттуда можно выпилить. Я вошлебной силой копипаста реализовал такую же функцинальность у себя, перезапустил проект, повел пальцем, и никакой прокрутки не произошло. Это уже половина победы. К сожалению, как и ожидалось, отключение прокрутки не повлекло за собой срабатывание MouseMove или MouseDown – их, похоже, в WP7 в браузере нет как таковых. Но это решалось уже совсем просто – мы просто поставили обработчики на OnMouseMove и OnMouseDown в C# прямо на сам компонент WebBrowser, и в этих обработчиках вызывали события на HTML странице. Приложение заработало, мы его отполировали, и были готовы к презентации. На презентации мы сделали самое главное открытие о хакатонах, которое затем закрепили на каждом последующем из них: 95% всех презентаций – это шлак. Люди пишут календари, приложения для заметок, аггрегаторы социальных сетей и прочие двухколесные транспортные средства, и в среднем, не зависимо от количества команд, только 3-6 презентаций действительно интересны. На первом хакатоне мы не попали в топ3, но так как не ужасных приложений было всего 6, Nokia вручила 6 телефонов, так что мы с Машей унесли свеженький не залоченный Lumia 900 – очень недурной девайс.

AT&T Mobile hackathon -- Education

Через две недели после хакатона от Nokia мы пошли на значительно более масштабный хакатон от AT&T, посвященный проблемам образования. На нем мы узнали вторую интересную особенность хакатонов – люди относятся к ним очень серьезно. На вступительном слове организаторы сказали, что поводом для этого хакатона стало то, что в Америке 40% студентов не заканчивают университет. Затем люди представляли свои идеи, чтобы собрать команды. На этом хакатоне готовый код приносить было нельзя, и собрать команду было важно. Почти каждый второй человек рассказывал, как его беспокоит такая большая цифра, как 40%, и как его приложение поможет ее уменьшить. Правда, в основном это звучало как: “проблема заключается в том, что у студентов нет удобного календаря в телефоне”, или “у студентов нет удобных средств для заметок”. В общем теория о 95% проявила себя еще на стадии озвучивания идей. Было и несколько хороших серьезных идей – в основном высказанных учителями, а не программистами. Забегая в перед следует отметить, что выигравшая команда была как раз одной из тех, которые собрала учительница, а не программист. Еще до Хакатона решив, что писать надо для таблеток, мы одолжили у Ники c работы его iPad, который после прошлогоднего Russian Code Cup есть у каждого уважающего себя программиста (у меня нету). Наша идея была написать онлайн игру с математическими головоломками. Я ее озвучил, и к нам присоединились двое ребят из Cisco, которым она понравилась. Coding Phase был опять 8 часов. Пока ребята писали паззлы, я писал красивые эффекты на HTML5 Canvas и CSS3, чтобы игра выглядела презентабельно. Как раз когда я собрал небольшую демку с эффектами, к нам подошел парнишка из BlackBerry, и спросил над чем мы работаем. Я показал ему демку, и он предложил нам презентовать это дело не на iPad, а на PlayBook. Он дал нам PlayBook для презентации, и пообещал, что если мы что-то выиграем, он подарит каждому члену команды по Playbook. Поддержка HTML5 и CSS3 на Playbook была более чем достаточная, и моя демка отлично запустилась на нем. К тому времени ребята уже подготовили паззлы, и мы начали собирать все это дело в игру. Сервер опять развернули на AWS, с двумя 10-ти строчными PHP скриптами. За пол часа до конца Coding Phase мы смогли запустить первую рабочую версию игры, и поиграть с двух таблетов друг против друга. На PlayBook анимация немного тормозила, на iPad летала, поэтому мы решили для презенации только упомянуть, что второй игрок играет с PlayBook, но под камеру поставить все-таки iPad. Презентация прошла красиво. Перед награждением к нам подошел один из судей, и сказал, что хотя наше приложение и было технически заметно лучше многих других, в топ3 оно не может попасть, потому что оно не помогает решить проблему с 40% студентов, выпаюащих из колледжа. А так как правило 95% никто не отменял, на третьем месте оказалось приложение, которое просто показывает демотивирующие картинки, которые описывают судьбу человека без высшего образования. Мы же получили первый приз от AWS, так как Amazon спонсировал соревнование, в размере \$1500 на AWS аккаунте, и, как следствие, по PlayBook на человека. Нам с Машей два PlayBook были ни к чему, так что она вместо своего взяла себе BlackBerry Bold 9900.

AngelHack

Парнишка из PlayBook оказался Larry McDonough, и предложил нам на следующем Хакатоне выступать от BlackBerry. За один только факт выступления BB платит по \$500 на участника, и дает кофточки, кепочки и сумочки. За победу на хакатоне там цифры повыше, но победы не произошло, так что они не важны :о) Следующим Хакатоном, через две недели после AT&T, был AngelHack. Это огромный хакатон, с невероятным количеством участников. Coding Phase длится 24 часа, по итогам которых команда должна засабмитить 90 секундное видео с презентацией своего продукта. Из них выбирается 30 лучших, и они выступают с презентациями перед инвесторами, которые готовы вложить \$25000 сразу на месте – это первый приз на соревновании. На этом Хакатоне мы выступали вдвоем c Машей, и писали игру, позволяющую выбрать друга на Facebook и намылить ему морду в игре, похожей на Mortal Combat. В этот раз мы хостились на Windows Azure, потому что они спонсировали соревнование, и я не могу не отметить, что Azure неплохо подрос со своим недавним релизом – если вам нужен PHP + MySQL (Python, Java, NodeJS) сайт, вы просто вводите название домена, и получаете доступы к MySQL и Git репозиторий. Все, что вы пушите в этот репозиторий, автоматически появляется на сайте. Во время работы с Azure было сложно поверить, что это сделал Microsoft. Кто бы мог подумать год назад, что делая git push со своей убунты я смогу обновлять сайт в Майкрософтовском облаке. В общем, в топ30 мы не попали, потому что на этом хакатоне ценились приложения с хорошими бизнес-перспективами, а мы просто написали забавную игру. Вот видео, которое мы в конечном итоге засабмитили:

По итогам этого хакатона мы не получили никаких призов, но унесли 1000 долларов за то, что представляли BlackBerry.

Наконец, в эти выходные, спустя всего неделю после AngelHack, мы пошли на хакатон, который нам наконец-то удалось выиграть. Хакатон был привязан к Google IO, и проводился компанией Mashery, с 36-часовой Coding Phase. Уставшие после AngelHack и тяжелой рабочей недели, мы не хотели писать ничего сложного, а просто хотели пообщаться с людьми, и выучить что-то новое, посвятить больше времени изучению того, что предлагают спонсоры на этом соревновании. Среди интересных спонсоров были AllJoyn, с API, которое позволяет легко общаться между телефонами/таблетами/компьютерами на небольшом расстоянии по Bluetooth или через общую точку доступа к WiFi, и Sphero Ball – шарик, которым можно управлять с Андройда, и который можно программировать. Сначала мы очень хотели написать что-то для Sphero, но первую половину дня шариков ни у кого не было – спонсор забыл прийти на событие. Но это было не важно, потому что первая половина дня все равно благополучно ушла на то, чтобы поставить Android SDK и разобраться как им пользоваться. Телефонов на Андройде в нашей команде ни у кого не было (у меня WP7, у Маши BB, у двух других ребят iPhone), так что телефон мы одолжили опять заранее, у Дэвида с работы, который купил его всего пару дней назад и еще не успел заполнить его личной информацией. Во второй половине первого дня шарик-таки нашелся, но после непродолжительной игры с ним мы поняли что он является абсолютно бесполезным девайсом. Точность выполнения команд, равно как и точность всех сенсоров в нем настолько ужасная, что написать хоть что-то рабочее для него не представляется возможным. Поэтому мы решили сконцентрироваться на AllJoyn. Настройка его, и долгие попытки связать два телефона заняли ненулевое время, как моего, так и представлителя AllJoyn на хакатоне, но в конце концов мы смогли заставить один телефон получить данные с акселорометра другого. Выступали мы вчетвером, с Марко с работы и молодым человеком по имени Харшит из Cisco, c которым мы выступали на AT&T хакатоне. Марко в первый день нашел Open Souce версию бомбермена на Java, в которую мы попытались сыграть вчетвером. Это было очень легко раньше, во времена, когда существовали цифровые клавиатуры, и стрелки были далеко от букв. Разместить четыре человека на клавиатуре сегодня, когда люди используют в основном лэптопы, дело не простое, и весь второй день мы неспеша хакали эту игру, чтобы сделать возможным управлять человечками с телефонов. Часа четыре с утра я с парнишкой из AllJoyn пытался разобраться, почему код, почти идентичный семплам, разрывает соединение ровно через 20 секунд после установки. Парнишке пришлось поднять половину команды, разрабатывающей AllJoyn, посреди воскресенья, чтобы разобраться в проблеме. В конце концов оказалось, что я создавал ссылку на объект, отвечающий за соединение, в области видимости метода, этот объект создающего, а не класса, содержащего этот метод, и Java любезно через 20 секунд после завершения метода тот объект собирала мусоросборщиком. Откуда берется волшебное значение в 20 секунд я могу только догадываться. В любом случае, задолго до конца Coding Phase все было готово, и мы нарезали в бомбермена с телефонов. Акселорометр управлял человечком, а нажатие в любом месте экрана ставило бомбу. Управление оказалось на удивление недурным, и презентации еще не начались, когда уже почти каждый участник хакатона зарубил в эту игру с нами. Единственные несколько человек на хакатоне, кто все еще не видел это произведение искусства из Open Source игры, едва измененного семпла AllJoyn и нескольких строк кода, все это связывающих, были судьи. Правило 95% в очередной раз проявило себя, и хороших презентаций было от силы 5. Плюс была одна презентация, почти ничего из себя не представляющая, но сделанная двумя 16-ти летними девочками. Они, собственно, собрали почти все вторичные призы – потому что 16-ти летние девочки, по мнению судей, на хакатоне являются более важным качеством команды, чем техническая сложность исполнения. В любом случае, AllJoyn использовало только четыре команды, и мы среди них волшебным образом заняли только второе место, уступив ребятам, которые сделали приложение, позволяющее быстро собрать контакты всех ребят, присутствющих на событии (вместо постоянного обмена визитками). Но в общем зачете мы разовали всех, и заняли первое место, внеся в свою копилку первую победу на хакатоне. В итоге мы ушли домой с \$1300, которые, правда, пришлось делить на четверых. Так что для нас с Машей AngelHack, на котором мы заняли ничего, оказался прибыльнее, чем IOhack, который мы выиграли. А сразу после хакатона мы побежали на концерт Dream Threater, который в этот день выступал буквально в квартале от того места, где проходил хакатон, и в трех кварталах от нашего дома.

В итоге за четыре события мы обогатились на три новых девайса и чуть больше чем \$3000, выучили много новых для себя технологий (разработка для WP7 и Android, Azure, Facebook API, AllJoyn API, Sphero), познакомились с огромным количеством очень интересных людей. Единственный большой минус хакатонов – они ужасно изматывают, и забирают единственные два дня на неделе, когда можно отдохнуть.

Вместо P.S. не могу не напомнить, что через две недели будет ICFPC – одно из самых крутых соревнований в году, тоже очень сильно отличающееся от спортивного программирования.

•
• +208
•

By SkidanovAlex22 months ago, ,

Давече на ВКонтакте Николай Дуров в одном из обсуждений посоветовал книжку Inside C++ Object Model.

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

Вот сегодня я показал такой пример:

``````#include <stdio.h>

class Point
{
public:
int a;
Point() : a(5) { };
virtual ~Point() { printf("%d\n", a); }
};

class Point3D : public Point
{
public:
int b;
Point3D() : b(7) { };
virtual ~Point3D() { printf("M\n"); }
};

int main()
{
Point* p = new Point3D[5];
delete [] p;
return 0;
}
``````

И спросил их, что они ожидают увидеть.

Потратьте 5 минут чтобы предложить свой вариант ответа.

На самом деле для меня (и для тех кому я задал вопрос) кажется очевидным, что 5 раз выведется M5 (сначала вызовется виртуальный деструктор Point3D, затем виртуальный деструктор Point).

Согласно книге это не так. delete[] ничего не знает о полиморфизме, и вызовет деструктор Point. Более того, delete[] ничего не знает о том, что реальный размер объектов в массиве больше размера Point, а потому удалив первый элемент он сдвинется только на размер Point, а не на размер Point3D, тем самым вызвав второй декструктор на совершенно неверном участке памяти. Ребята мне не поверили О.О

Мы запустили код, и он вывел M5 пять раз.

Как же так, книга врет? И в тоже время -- я могу поверить, что компилятор догадался взять деструктор из виртуальной таблицы, но откуда он узнал реальный размер объекта?

Не веря в происходящее, я установил Clang, и собрал этот код clang'ом. Код вывел пять пятерок. Кажется, что в этом коде вывести пять пятерок просто невозможно -- это значит, что компилятор не догадался вызывать деструктор из виртуальной таблицы, но догадался сдвигаться на правильный размер?

Я думаю, что все опытные С++ гуру уже поняли что здесь происходит.

Проблема в том, что код запускался на 64-ех битной машине, и компилятор догадался поместить a и b в один восьмибайтный блок, таким образом размер класса Point и Point3D был одинаковый (16 байт -- еще 8 на указатель на виртуальную таблицу).

Теперь давайте поменяем int в определении обоих классов на long long. Каково будет поведение? Опять же, потратьте пять минут, чтобы придумать свой ответ, прежде чем читать дальше.

Чуда не происходит. Коду неоткуда узнать реальный размер объектов. Оба компилятора продолжают вести себя так же как и раньше (g++ вызывает виртуальный деструктор, а clang вызывает деструктор у Point), но только теперь размер Point не равен размеру Point3D. Таким образом clang выводит мусор в виде пятерок, семерок, и численного представления указателя на виртуальную таблицу, а g++ просто сразу падает по Segmentation Fault, не успев вывести ничего. Это странно, потому что виртуальная таблица лежит в самом начале класса, и не понятно, что именно не позволяет вызвать виртуальный декструктор хотя бы для первого элемента.

В любом случае, мораль простая -- массивы не работают с полиморфизмом, и, видимо, приведенный код -- это undefined behavior. Интересно, как этот же код поведет себя в Visual Studio и MigGW?

Вот код для запуска с отладочным выводом:

``````#include <stdio.h>

class Point
{
public:
long long a;
Point() : a(5) { };
virtual ~Point() { printf("%lld\n", a); }
};

class Point3D : public Point
{
public:
long long b;
Point3D() : b(7) { };
virtual ~Point3D() { printf("M\n"); }
};

int main()
{
printf("%d\n", (int)sizeof(Point));
printf("%d\n", (int)sizeof(Point3D));
// это поможет понять где лежит указатель на виртуальную таблицу
printf("%llu\n", &Point::a);
printf("%llu\n", &Point3D::a);
printf("%llu\n", &Point3D::b);

Point* p = new Point3D[5];
delete [] p;
return 0;
}
``````

Вывод для G++:

``````16
24
8
8
16
Segmentation fault
``````

Вывод для clang:

``````16
24
8
8
16
4197968
5
7
4197968
5
``````

•
• +74
•

By SkidanovAlex23 months ago, ,

Facebook анонсировал очередной HackerCup. Регистрация уже началась, квалификационный раунд начнется 20 января в 4 вечера по времени в Фейсбуке (21-ого в четыре утра по Москве).

Первый раунд состоятся 28-ого января, второй и третий -- 4-ого и 10-ого февряля (5-ого и 11-ого ночью по Московскому времени соответственно)

•
• +80
•

By SkidanovAlex2 years ago, ,

TCO2011 закончился. Из семи номинаций в шести победили азиаты, и в одной победил поляк. Это печально :о)
Несколько слов о том, что вообще такое TCO2011 для тех, кто не знает. Это соревнование, проводимое компанией TopCoder в нескольких номинациях, включая проектирование и разработку ПО, дизайн, и, самое важное и интересное, спортивное программирование.
До этого года ТСО четыре года подряд проходил в Вегасе, в этом году его провели в городе Голливуд на берегу Атлантического Океана, в 20 минутых езды на машине от Маями. Организаторы объяснили это тем, что очень сложно говорить серьезно и приглашать компании к сотрудничеству, когда событие проходит в Лас Вегасе.
Несколько фотографий отеля и видов из окна

Наша компания спонсировала соревнование, и я присутствовал на соревновании как спонсор. Я уже публиковал фотографии нашего столика в комнате, где проводилось соревнование, и говорил, что у Интела там целый угол. Вот так этот угол выглядел.

Люди иногда подходили и играли в Wii, но в целом казалось, что усилия Интела не оправдали себя.

Фейсбук на этом соревновании не раздавал никаких дорогих подарков, только кубики рубика, Интел разыграл нетбук от Леново, мы разыграли MacBook Air. Кажется, что большие компании очень жадные :о Разыгрвали мы его в турнире по покеру, который проходил на пуфиках рядом с ballroom-ом

С финалом в последний день прошла накладка. Утром Петя должен был общаться с детьми, которых привели на выступление Dean Kamen, а после обеда Миша Кевер писал финал ТСО. После Финала у нас с Эриком уже был самолет. Пришлось проводить финал по покеру прямо во время ланча :о)

Выиграла его девушка по имени Анна из Польши, ее хендл на топкодере 7ania7.

Теперь немного о режиме дня и самих соревнованиях. Завтрак каждый день начинался в 7:30, и длился около часа. Можно было вставать немного позже, но в принципе обычно получалось подобраться на завтрак к началу, и некоторые ребята уже там сидели.

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

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

После system test результаты начинали показывать с последнего места, чтобы держать всех заинтригованными до последнего. Хотя, кажется, что с первого места никто ниразу на системниках не упал.

Мы с Эриком уехали с соревнования за несколько минут до начала церемонии награждения, поэтому не смогли понаблюдать за финальными системными тестами. В самолете, правда, был интернет, и результаты мы узнали достаточно быстро.

Интересно, что почти все русские ребята приехали с iPad'ами. И это не потому, что все так любят продукцию Apple, а потому, что почти все прошли на Russian Code Cup, где выдавали iPad всем участникам. Mail.ru реально расщедрился на своем соревновании. TopCoder Open выдал только футболочки и сувениры :о)

В этом году не осталось больше ни одного онсайта -- TopCoder Open было последним, замыкая цепочку соревнования от Facebook, Яндекса, Google, mail.ru и ABBYY. Хотелось бы верить, что все компании, которые провели в этом году впервые свое онсайт соревнование, проведут его и в следующем, и уже в январе мы будем проходить отборочные на HackerCup :о)

•
• +90
•

By SkidanovAlex2 years ago, translation, ,

Last time I mentioned, that one of the winners of the 'best event for participants' competition was a girl, who offered participants to take pictures based on tasks like "take a picture of yourself and <description of other person> doing <description of setting>". Even though that is a really awesome event, very few people were interested in it, which was very sad.

Every person had a different set of 10 tasks, the winner was the one who had more pictures, and the tiebreaker was an additional picture, having most people in the air jumping on the beach.
At the end I had only 9 pictures + a tiebreaker with 8 people in the air, while MikhaelOK had 10 pics without a tiebreaker. The person for the 10th picture already agreed to help me, but organizers told me that I do not qualify for the prize of 2012 trip (since I am one of the sponsors), and I just gave up.

1. Take a picture with a TopCoder Admin with TCO logo in the background. Everybody had that one, and it was very easy.

•
• +78
•

By SkidanovAlex2 years ago, translation, ,

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.

•
• +91
•

By SkidanovAlex2 years ago, translation, ,

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 :)

•
• +92
•

By SkidanovAlex2 years ago, ,
http://www.diofant.ru/problem/1975/

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

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

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

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

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

•
• +35
•

By SkidanovAlex2 years ago, ,

Как и в прошлом году, в этом году готовиться к 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. В любом случае я бы не полетел в Россию на онсайт :о(

•
• +44
•

By SkidanovAlex3 years ago, ,

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

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

Дан массив длины 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.

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

•
• +65
•

By SkidanovAlex3 years ago, ,

Задача А.
Сначала заменим все числа на 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 ).

•
• +6
•

By SkidanovAlex3 years ago, ,

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

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

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

Задача 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 элементов, и мучительно угадываем закономерность.

•
• +35
•

By SkidanovAlex3 years ago, ,

На сайте 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. Удивительно, что место проведения поменяли в этом году.

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

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

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

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

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

•
• +48
•

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

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

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

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

•
• +21
•

By SkidanovAlex3 years ago, ,
Еще довольно давно, примерно на первых курсах ВУЗа, я играл с другом по сети в игру 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
Код на яваскрипте включает несколько тестов к геометрическим функциям (кроме пересечения отрезка и дуги).

•
• +38
•

By SkidanovAlex3 years ago, ,

Я уверен, что многие из вас, кто сейчас занимается олимпиадным программированием, попутно занимаются или пытаются заниматься разработкой игр. Я могу с ходу вспомнить упоминания как минимум двух человек об этом хобби, один из которых красный и медалист (если не дважды) 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. И, конечно, запуск игры стоит денег. Как минимум на содержание сервера и покупку рекламы. Это с предположением, что у вас есть команда, покрывающая все необходимое в игре. Иначе надо еще рассчитывать бюджет на покупку недостающего контента. Прежде чем тратить значительные усилия на разработку, убедитесь, что ваше финансовое положение позволит потом проект запустить.

•
• +74
•

By SkidanovAlex3 years ago, ,

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

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 в течение шести минут повторно, скачается другой тест?

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

•
• +82
•

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

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

•
• +3
•

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

http://vkontakte.ru/video19091867_146612299

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

•
• +12
•

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

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