Hi Friends! Small game for coders have been added at my site: Space Invaders Automation

If you have, perhaps, 30 minutes to spare, I invite you to have fun with it! It is to be coded in Lua, but don't hesitate — language is simple (similar to Python) and we have small introduction, so you'll be an expert in 15 minutes — and can write reasonably good code in another 15, moreover there are a couple examples :)

The goal is to defend against aliens at least for 60 seconds. Current "standings" are (only 3 participants yet):

tzyLee         417 seconds
gardengnome    162 seconds
TestUser (me)   63 seconds

Many thanks to gardengnome for proof-solving it — actually it was he who suggested converting it to "challenge" format — so now you can compete, whose program stand longer!

Perhaps there are a few people who haven't yet learned about Cartesian Tree — this curious data structure allows many interesting uses and actually is very simple! Years ago I read about it here at CodeForces, but felt slightly confused/horrified and put it aside. Very silly :)

Returning to it years ago I created small exercise which could be solved, perhaps, in 15 minute — to help learning the idea, so to say, "practically". Here it is: Cartesian Tree Visualization — feel free to skip the intro about Descartes (kinda local joke).

Regard a simple problem of adding elements to a "list", every time into random place, e.g. in Python:

arr = []
for i in range(1000000):
    pos = random.randint(0, len(arr))
    value = random.randint(1000000, 9999999)
    arr.insert(pos, value)

With what data structure it can be effective? Linked list will allow O(1) insertion, but to find a place where to insert, we need to run O(n) from start. Some variants of trees may allow O(log(N)) insertion but it seems finding the proper index is equally difficult.

Wikipedia suggest Skip List with "minor modification" is what we want. Are there another structures (e.g. perhaps some modifications to some type of tree, perhaps, cartesian) useful for this task?

Hi Friends! Here is the problem created by one of the user's at my site. I don't ask for solution (at least yet, ha-ha, going to try thinking a bit more) — but invite you to check your skills, presumably, at DP.

It has somewhat lengthy description, but boils down to counting number of differing subsequences in 01-string with required balance of zeroes and ones. I quickly started scratching typical DP-like double loop, but soon found it doesn't account for possible duplicates: i.e. in the sequence 1010 we can pick 10 subsequence in two ways but they are not considered different. Results seemingly can grow somewhere to 10^18 so naively keeping all sequences in hashtable doesn't look like a viable approach. Sorry for my naive thoughts, I'm obviously lame at this and perhaps there is a known solution. However if you, like me, don't know it, you can spend some time on it...

Hi Friends!

I know you all are probably busy solving some ongoing contest or preparing to some upcoming. But in case you have half an hour to spend on funny problem without clear solution, I invite you to try Jewels at my site.

You may know this game as "Match-3" or "Bejeweled". Now the question is to write small function to "auto-play" it - i.e. to suggest some good move. Code is accepted in Python or Lua (supposedly many of us know Python anyway — and who don't, I recommend investing 15 minutes in learning Lua — there is "intro" link included).

Writing naive implementation of about dozen lines which iterates over the board and tries to find any valid move probably won't take more than another 15 minutes from you. However running time is limited to 1 second so that it probably is not possible to carefully and slowly examine all possible moves at each step. This means you can try some fancy ideas of "inexact" solution.

We know the problem of "maximal pair matching" (or "maximal matching in bipartite graph) — one of solutions for it is via "maximum flow" algorithms.

But how to solve certain extension of the problem?

Statement

There is a set of 3*N persons, gender-agnostic. We want to split them into N groups of 3.

For every two of them we know the value of mutual happiness of being together in the same group (e.g. we have a diagonally symmetric table 3N by 3N of happiness).

Now, how to maximize happiness? Assuming happiness of a group is sum of 3 pair's happiness in it — and total happiness is the sum over group's happiness.

Any ideas? Iterative random swaps may help in improving happiness but is there precise solution (without brute-force iterating over all possible group arrangements as their number increases pretty fast).

Thanks in advance!

Hi Gurus and Colleagues!

Sorry for distracting you from coding — but e-maxx-eng project needs your advice — as you probably remember, it is a collection of articles on algorithms seen as important for mastering competitive programming :)

Since the past November project have got real boost — especially due to dedicated efforts of Jakube, adamant and other wise people. So its statistics grew several times, its content too... Over 100 articles and crawling to 1000 daily pageviews... And probably it is now a time to improve its appearance on the web by choosing a dedicated domain name.

Currently it resides on default appengine's e-maxx-eng.appspot.com. It's all right, but probably not extremely clear for people not aware of who is e-maxx, it is 3-rd level — and also clashes with Traxxas E-Maxx toy %)

So it is now tricky situation. It seems to be easy to order a dedicated domain name and bind it to the site. But we can't easily choose one. There were a few suggestions — but probably you'll be able to advice something better suitable — or vote for one of these variants:

• competitive-programming.com — bit too wide, site is not everything about CP
• cp-algorithms.com — looks good for me, though CP is used for other abbreviations...
• competitive-programming-algorithms.com — not sure anyone will type it in
• cs-algorithms.com — similar to cp-algorithms, but more known abbreviation... regretfully more wide too
• e-maxx-eng.com — not clear whether retaining E-Maxx name is a good move or bad
• hard-algorithms.com — not very clever (and like tough-algorithms, tricky-algorithms)
• algorithms-wiki.com, algorithms-hub, algo-hub — however "algohub" is already taken in several variants

So feel free to participate, to suggest, to cast your vote! Also you may express what suffix you feel suits better. Though .com seems to be ok — I personally feel .net or .org may highlight it is not commercial enterprise. Also there is .info — probably it may be more descriptive to the nature of the site.

Few Points: name should not resemble some existing domain too closely (e.g. differ in suffix and spare dash), not should be already taken of course, probably should express some relation to its content :)

Thanks in advance!

I was informed by some bot of removal of wikipedia page about Codeforces.

It was created some years ago when someone asked why there still is no such page. Then some material was added to it by few people, but it seems that either notability criteria were not reached or some other factors were involved (Russian hackers hysteria, maybe).

It is somewhat strange for me, since Codeforces is steaming extremely well, seemingly surpassing Topcoder by popularity and many other sites moreover.

Perhaps some people will decide to invest time and recreate/improve such a page. For now let there be the link to one of the latest snapshots of the page from wayback machine:

https://web.archive.org/web/20160114012719/https://en.wikipedia.org/wiki/Codeforces

Внезапно получил несколько вопросов о Hacktoberfest 2017 и e-maxx-eng — в общем, в этот раз все как и год назад, так что вкратце повторюсь.

1. О да, digitalocean объявил новый Hacktoberfest: https://blog.digitalocean.com/hacktoberfest-2017/

2. О да, вполне возможно (и несложно) получить футболку — создайте 4 осмысленных пулл-реквеста на гитхабе (для этого не требуется знать гит) и пошлите заявку на футболку (нужно будет ввести свой ник на их сайте, и если ПРов хватает — размер футболки и адрес).

3. О да, мы уже попробовали это в 2016-м по подсказке Марии (aka Nickolas) — и да, футболки пришли. Мне пришла где-то через месяц (хотя дизайн показался немного тускловат в смысле красок — см фото внизу).

4. О да, проект e-maxx-eng подходит для участия в хактоберфесте как и любой другой — присылайте переводы статей оригинального сайта, или свои собственные (авторство сохранится). Пожалуйста, обратите внимание на инструкцию и пост 2016 года.

Мы постараемся помочь с ПРами по мере возможности и ответить на вопросы. Также Большое Спасибо Марии (aka Nickolas) что двигала процесс в течение всего этого года, так что у сайта теперь даже ненулевая стабильная посещаемость образовалась :)

P.S. Касательно вопроса "что за футболки были в 2016" — я нашел демонстративное фото в посте из блога Anna Dodson:

Hi Friends!

Briefly: E-Maxx in English project is now semi-automated so it would be far easier (I hope) to contribute.

Updated web-site is http://e-maxx-eng.appspot.com. It grabs source texts from github and converts them from markdown. So now if you want to add an article, you can do this just in your browser, in github's interface. No more need to kick with local PHP installation etc.

You can read details in Contributors Manual or watch this demo video.

In details:

I've started E-Maxx-Eng project two years ago, as described in this post.

• the first part of idea was that people would be able to add or update texts via GitHub fork / pull-request functionality;
• the second part was to convert markdown article sources into html with PHP script on local computer and then upload result to github pages.

The second part was total crap, as it appeared. I myself felt it is difficult to update the site in such manner so the site soon become forsaken as I got more involved in my personal projects. I'm sorry for this.

I_love_Hoang_Yen provided much help with reviewing and merging recent pull-requests, however I'm afraid it seemed far from comfortable for him either. Thanks a lot to him!

Recently Nickolas wrote to me with the question whether anything could be improved. As I admire and love her greatly, I felt quite ashamed that the project is neglected. So big thanks too! And thanks to everyone who tried to contribute, to help or simply wrote some kind words.

So I composed my brain and tried to make appengine project which can:

• automatically grab new pages from github project as they are merged;
• provide live preview for the text you are going to add;
• and render all these page, so becoming a new e-maxx-eng site.

It seems to work now. Though perhaps you will be able to point some bugs or suggest improvements. Please sorry again for it take that long, but honestly speaking 2 years ago I have no clear idea of how this could be done. We all learn new things by and by.

P.S. I hope we'll be able to add few more "admins" to the github e-maxx-eng organization by and by who have the power to accept pull-requests and also to provide technical advice to contributors (e.g. with github, markdown etc).

Dear Admins and Developers of the CF! Thanks a lot for all your efforts in maintaining and extending the functionality of this wonderful site.

If possible, please change the "Recent Actions" box on the right to be loaded via AJAX. There are two reasons:

• Google crawler is fooled with the topic names from there so when I search in Google for some phrase (trying to find some CF blog post), Google usually includes into results several unrelated pages which by coincidence contained the "recent" link with the phrase during the time the page was indexed — but surely do not contain it now (it is even more important as the site currently have no full-text search of its own);
• less important, but this will allow you easily make this box periodically updating — say, once per minute — just repeating the initial ajax call by the timer.

Thanks in advance!

P.S. Simple example on the first reason: open google.com and search for cool new feature site:codeforces.com — or just click this link — besides the first result (leading to the proper page) there are many others which lead to pages containing no words "cool" or "feature" at all! E.g. Gassa profile etc :)

Hi Friends! Sorry if this was already mentioned. You perhaps know that ProjectEuler was hacked again recently and was shut down for almost a week (since 2 to 7 of August 2015).

It is now back, but Mr. Euler stated they failed to determine how the site was hacked and ask for people skilled in vulnerability hunting to help.

Here is his post in the news: https://projecteuler.net/news

And here are few details about the recent troubles: http://forum.projecteuler.net/viewtopic.php?f=5&t=3937

Hi Colleagues! I need to have about 20 programming exercises (i.e. their statements) translated from English to Chinese, German, French. (this is for CodeAbbey site)

They are on average 100-250 words each (somewhat similar). I can offer small reward — about $25 per 10 translations — about 2 hours work for native speaker. Texts are in Markdown format. Few more technical details could be found here along with texts translated so far (but in different languages). Feel free to contact me with any questions / suggestions.

Поздравьте меня — на моём сайте CodeAbbey обнаружен первый крупный читер. Блин! Чел не поленился скопировать и слегка отрефакторить 125 задач (видимо, у коллеги) — чтобы попросить сертификат. Зачем — ума не приложу. Это же не сертификат оракла или микрософта. Но потратил в сумме недели три. Выглядит это так:

оригинальный код

код последователя

(А может мне только кажется что они похожи?)

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

Пока обмозговываю — можно по коду считать какие-то метрики / хэши и записывать вместе с решением. Ну скажем, количество знаков препинания, символьных операторов. Потом для проверяемого пользователя найти еще одного с близкими показателями метрик. В общем что-то вроде Locality-Sensitive-Hashing получается. Однако прежде чем врукопашную и наобум экспериментировать — решил спросить — вдруг уже более-менее проторенные дорожки есть? Быть может кто-то уже сталкивался (а то и собаку съел) с похожими задачами — и подскажет направление?

Догадываюсь что администрация CF имеет свои способы наверняка — но как подсказывает мудрый коллега, наверняка они достаточно засекречены во избежание сами понимаете чего :o

Пытаюсь сдать FLOW на SPOJ.

Вошёл на сайт, запастил код, выбрал язык "Java (JavaSE 8)", нажал Send.

Попал на страницу http://www.spoj.com/A12/submit/complete/

С надписью:

This contest page does not exist or you are not authorised to view it. Perhaps you may wish to reauthenticate or create a new account.

Допускаю что я у нас сегодня дурачок и плохо знаю нюансы спожа (до сих пор сдавал там несколько задач но такого не видал). Не мог бы кто из сведущих подсказать что я делаю не так? :-o

P.S. альтернативно поможет ссылка на аналогичную простую задачу на реализацию макс.потока на кодефорсез или тимус (чтоб далеко не ходить). Мне просто протестить код.

About half a year ago I posted there announcement of my site CodeAbbey. Since then the site have been evolving by and by (many thanks to all people who provided invaluable hints and suggestions!) — and few of them looks funny enough to me so that I'm eager to tell a bit about two of them.

Certificates

They [are awarded] for certain achievements (currently for 125 problems) — and are shown in profile — though you can also print it and hang above your desk. Of course they are still useless papers, but they are somewhat funny I think:

Certificates bear unique number on them so that their authenticity could be verified on site. You may read more here about them.

Interactive problems

They were introduced recently — to solve the problem user is to play a kind of game against a server. HTTP Post requests are used for interchange (sample code fragments in Python are provided).

Currently there are only four such problems:

• Say 100 — simple test that you can work with HTTP;
• Nim Game — also simple but allowing several moves;
• Maze of the Wumpus — by the motives of old game — requiring a bit of heuristic I suppose;
• Connect Four — once popular tic-tac-toe-like game allowing to practice minimax algorithm.

Though of course I hope to add more in future — and to improve clumsy infrastructure of these games also, he-he :)

Concluding I'd say it appeared to be a funny matter to try building my own site, though small and puny. Besides other things it made me acquainted with several interesting people all around the world — I hope I'll be able to write about some of them later in separate posts.

Придумал как понизить вклад — нужно поругать Google

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

Чем больше я знакомлюсь с многочисленными сервисами гугла, тем больше я порой удивляюсь. Попробовал вспомнить самые загадочные для меня моменты:

1. Гугл активно борется с сексом и насилием в Google Play (geektimes). Жертвами борьбы падают мелкие разработчики-одиночки, апелляции которых гугл игнорирует — при этом просто достаточно чтоб на тебя пожаловались, даже если у тебя нет подобного контента (гугл после "тщательной проверки" банит твои приложения) — крупные же дилеры софта явно имеют некие коррупционные договорённости с гуглом, которые позволяют им выкладывать что угодно.

2. Аналогично гугл борется за права правообладателей. Реагирует на любые жалобы крупных партнёров вроде "Blue Planet Software", банит без предупреждений, не вникая в детали и не вдаваясь в объяснения — апелляции предлагает направлять к этим же партнёрам. Будьте осторожны со словом "tetris"! :)

3. Гугл тихонько сливает инфу. Если вы добавляете на сайт хоть баннер Google AdSense, то рейтинг вашего сайта в Alexa ощутимо изменится (обычно в лучшую сторону) — т.е. инфа о количестве загрузок ваших страниц сливается в Амазон владеющий Алексой (так же как если вы рекламу от амазона добавите). В этом почти ничего плохого (особенно если рейтинг в алексе растёт а не падает) — но вы не найдёте чтобы гугл об этом писал. Это в частности одна из причин почему некоторые заказчики даже аналитику просят использовать собственную а не гугловую.

4. Несмотря на обещания показывать только качественную рекламу, гугл, особенно на мобильных платформах, отображает и баннеры волшебных программ "для ускорения всего", и "супер-антивирусы", и даже рекламирует конкурирующие магазины приложений (что сам запрещает), и сайты которые сам считает небезопасными (см. подробнее). Как результат в какой-то момент пользователи начинают жаловаться что им ваш сайт показывает какую-то хрень, а вы даже не можете разобраться что это за хрень была (т.к. для этого надо от пользователя добиться ряда хитроумных действий, чуть ли не перехода на вредоносный сайт).

5. Установите Поиск Гугл для Сайтов чтобы увидеть насколько он убогий — он не находит на вашем сайте даже той инфы которая явно проиндексирована в обычном поиске гугл — зато вываливает тонну нерелевантной рекламы типа "купить travelling salesman". К счастью я обнаружил что Поиск от Яндекса лишён обеих этих проблем (подробнее описал здесь). По интернетам я позже нашёл что это известная проблема (например).

6. Вообще сервисы гугла безобразно плохо интегрированы. Платёжная система Google Wallet не может быть использована для оплаты Google AdWords или для вывода Google AdSense. Для каждого из этих сервисов нужно регаться в какой-нить посторонней системе (вроде ООО Рога и Копыта). Я понимаю что амазон не принимает платежи через PayPal, т.к. это конкуренты. Но в случае с гуглом другого объяснения как затмение в умах на высшем уровне трудно найти.

7. Гугл проводит политику монополизации андроидного мира и старательно выжимает конкурентов, в частности требуя разработчиков девайсов предустанавливать свои приложения (ссылка) — в противном случае лишая доступа к своим сервисам.

8. Гугл предпочитает секретить разработки таких технологий которые Yahoo и Facebook контрибутят в opensource. Типичным примером являются технологии BigData — почти все решения гугла в этой области закрыты (ну как GFS и BigTable), так что мы пользуемся их опенсорсными аналогами (вроде HDFS и HBase) лишь благодаря вышеупомянутым конкурентам гугла.

9. Похоже Гугл не стремился поддержать Google AI Challenge, так что в последний раз они вроде бы прошли уже без названия гугла... И с тех пор по-моему их не видели. Ну да, это общая проблема подобных соревнований — их польза для больших компаний слишком неочевидна. Но всё же энтузиасты находятся даже среди куда меньших компаний.

Резюмируя что я хочу сказать. Гугл зайка — но он не годится на пост:

• всемирного борца за права и свободы (если их нельзя трактовать и использовать в целях увеличения прибыли гугла);
• великого радетеля о светлом технологичеком будущем человечества;
• примера компании которая всё делает идеально.

P.S. Извините что недостаточно много пруфлинков собрал.

Currently Top Contributors List is the same for English (international) and Russian version of the site.

As sweiss pointed out (here), this means that English-speaking users may see here users without slightest idea what is contributed by them. Especially if most of user's contributions consist of good old Russian Humor instead of programming-related stuff :)

Suggestion:

This should not be hard to build separate contributors list filtered by only English posts and comments and show it on the English version of the site.

This should be more "foreigner-friendly", I think, since this will give some English-speaking contributors a chance to get to this top...

Тут обсуждали форум, который, возможно, никогда не будет сделан потому что для этого надо чтобы кто-то из состава администраторов-разработчиков CF этим занялся.

И я подумал:

У CF есть теперь крутое API. Если бы ещё можно было с его помощью логиниться через Codeforces, то создание подобных форумов и прочих забавных сайтов, доп-ресурсов и т.п. — им могли бы заниматься все желающие.

С такого ресурса нужно было бы только жать ссылку "войти через CF", после чего он получал бы данные о пользователе (ссылку на профиль например) для сессии — и ура.

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

Кажется крутых возможностей по расширению функционала CodeForces сочувствующими бы значительно прибавилось!

Кстати это на порядок легче реализовать ведь чем форум! :)

В недавнем топике про поиск работы для "красного" и притом "интересной" — возник вопрос от Konstantin.Zakharov по поводу того, не возникает ли привыкание (адаптация) к "обычной", т.е. неинтересной программистской работе. Данный пост — содержит мои краткие наблюдения по этому поводу (в коммент не влезло).

Целиком вопрос выглядел так:

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

Я хочу сказать что люди разные! По-моему можно выделить две категории разработчиков в индустрии:

1. Те кто что-то пишет даже дома, в свободное время;
2. И те кто дома не пишет.

Я не имею в виду что это "хорошие" и "плохие" программисты :)
Но сам я об этом разделении узнал довольно поздно. Рассказывал коллеге о задачке попавшейся на ProjectEuler — и тут он спрашивает, не то со смехом, не то с возмущением:

Ты чо, и дома что ли кодишь?

Я удивлённо говорю "А ты нет???" — он ответил "Нет конечно, я телик смотрю". А у меня и телевизера нет (я его вынес на лестницу и какие-то добрые люди забрали).

Как эти две категории программистов относятся к карьере

Пару лет назад я работал в одной аутсорсерской конторе (большой). Там я познакомился с классными ребятами с соседнего проекта. Назовём их Ева, Петр, Хайрем и Саймон (все четверо были старшими разработчиками и пилили национальный поисковый портал для одной европейской страны).

В течение года Хайрем и Саймон уволились. С тех пор они кажется меняли работу ещё. Помимо того они постоянно творят какие-то посторонние (потусторонние) проекты.

Например Хайрем пробовал забацать некий неуспешный финансово-ориентированный сайтик, а позже — многопользовательскую игрушку под андроид — потом они оба бросили свои работы и месяц пилили некий стартап смысл которого я не понял. Разочаровавшись устроились вместе в одну крупную контору занимающуюся хай-лоадам и работающую для клиентов вроде PayPal. В общем, развлекаются :)

В то же время Ева и Петр продолжают работать в компании где я с ними познакомился (сам я с тех пор тоже пару мест работы сменил).

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

Впрочем, как я подозреваю, Саймон и Хайрем с тех пор ощутимо повысились в зарплате — повышаться вообще легче если меняешь работу (моя собственная, например, выросла раза в полтора). Так что все имеют основания быть довольными, все по-своему счастливы :)

Conclusion

Так что осмелюсь повторить свой ответ — люди разные.

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

P.S. Наверное ещё не учли случая когда junior-разработчик приходит на первую работу и она его восторгает даже если она тупая, т.к. есть эффект новизны. Но со временем новизна ведь уходит и человек тоже попадёт в одну из упомянутых двух категорий.

Есть известная задача для новичков которые только научились алгоритму поиска минимума в массиве: найти M минимальных в массиве из N элементов.

И вот коллега недавно проводил собеседование и троллил соискателя вариацией:

Есть десятки терабайт логов — обозначим их как N записей — каждая запись содержит в частности значение некоторого параметра A. Мы хотим выбрать небольшое количество M (ну скажем, миллион) записей в которых значение параметра минимально. Как это сделать?

Характерные нюансы вариации:

• исходные данные живут во внешней памяти, в оперативку их целиком не прогрузишь;
• очень желательно чтобы алгоритм можно было распараллелить т.к. N определяемое терабайтами близко по порядку к 1e12 и один проход на обычном компьютере будет занимать примерно сутки (исходный массив хранится в распределённой системе так что нет проблем с тем чтобы использовать его пофрагментно).

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

Какие возможны подходы к этой задаче?

У меня родилось немного "детских" версий:

1. Можно идти по нашим данным и пихать их в двоичную кучу с максимальным размером M (т.е. пропускаем элемент если его параметр больше чем максимальный в куче, а если в кучу что-то запихнули и размер стал M+1 то вытряхнем из неё максимальный элемент). Быстродействие здесь будет лучше чем N*log(M) потому что не придётся обычно пихать все элементы — даже вероятно ближе к N + M*log(M). Однако как распараллелить двоичную кучу? Возможно заменить её на ConcurrentSkipListMap...

2. Если само M таково, что не помещается в оперативку (ещё вариация предложенная коллегой), то вместо кучи мы будем складывать элементы в список-копилку и после достижения размера 2M будем её сортировать слияниями и обрезать размер до M. Быстродействие по-видимому N*log(M). Распараллеливать наверное не очень легко но можно.

3. Больше всего мне нравится вариант (против которого коллега протестует) стохастический: пройдём по исходным данным и выберем все записи значение параметра у которых ниже некоего порога k. Как определим этот порог? Тут разные варианты — например сделаем предварительный проход по данным и выберем рандомно столько значений параметра сколько влезает в оперативку, скажем миллиард. Возьмём от них пропорциональное M/N количество наименьших значений и в качестве порога k выберем максимальное из этих значений. Конечно в результате просеивания мы потом можем получить не совсем M записей — но мы можем либо заранее завысить порог, чтобы прицелиться на 2M записей например — и отбросить лишнее. Т.е. этот способ хорош "среднестатистически". Его сложность может быть близка к O(N) и распараллелить его вроде легко.

Но хотелось бы узнать о более остроумных вариантах — если есть какая-то удобная структура со свойствами очереди с приоритетами, которую можно распараллеливать (а то ещё держать во внешней памяти) — то первый вариант можно довести до ума?

Нашёл такую "старинную" игру проглядывая "старинную" книжку. Если я правильно помню, клоны её публиковались в "Технике Молодёжи" для программируемого калькулятора.

Игрок управляет ракетой которая мчится к Луне. Ему показывают текущие высоту и скорость, а также количество остающегося топлива.

Нужно задать скорость подачи топлива на ближайшие 10 секунд (этим определяется скорость торможения) — после которых снова показываются высота и скорость и т.п.

Цель игры аккуратно посадить ракету — т.е. достигнуть высоты 0 со скоростью не больше, скажем, 10 м/с.

Физика игры примерно ясна: высота за каждые 10 сек уменьшается примерно на значение скорость * 10. Скорость сама по себе меняется в зависимости от ускорения силы тяжести (увеличивается) и работы двигателей (уменьшается).

Идея мне понравилась и я её заюзал для простенького упражнения на своём сайте. Кроме того я написал клон игры в качестве демонстрации и прилепил его туда же:

Демонстрашка и чуть больше пояснений здесь

После этого я стал играть сам и обнаружил что посадить ракету вообще не так легко!

Часто оказывалось что я сжёг всё топливо пока находился ещё достаточно высоко, ракета теряла скорость, потом начинала набирать её снова и БАЦ :(

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

Отсюда я заинтересовался вопросом:

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

Есть такая головоломка — я на неё давно в книжке М.Гарднера наткнулся: даны квадраты, разбитые на 4 треугольных сектора каждый — сектора выкрашенны в 3 разных цвета. Всего различных квадратов получается 24 и если покумекать, из них можно сложить прямоугольник 6*4, так что:

• вся граница прямоугольника состоит из треугольных секторов одного цвета;
• внутри квадраты касающиеся сторонами должны иметь на этих сторонах одноцветные треугольники.

Извиняюсь за косноязыкость, вот так выглядит типовое решение, чтоб понятнее было:

Онлайн можно попробовать повертеть головоломку на этой страничке.

Автор видимо Александр МакМагон.

Хотя решение с полпинка найти нелегко, их на самом деле много. Гарднер упоминает что один из его читателей вывел аналитически — а второй с помощью ЭВМ число около 12 тысяч.

И вот стало мне любопытно — как программно это дело посчитать (чтобы понять можно ли из этого какую-то задачу придумать).

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

И вопрос в том — существуют ли какие-то более легкие способы ограничить перебор или что-то в этом духе.

Наверное не только мне на почту упало извещение о Russian AI Cup 2014? А на CF анонса почему-то нет — или мне кажется?

http://russianaicup.ru/

Чемпионат третьего Russian AI Cup называется CodeHockey. Вам предстоит программировать искусственный интеллект для команды хоккеистов.

Правда после фокуса с онсайтом Russian Code Cup 2014 возможно некоторые из нас ожидали и фокуса с AI Cup... (впрочем, всё ещё впереди) :)

Недавно AlexanderBolshakov показал в этом посте — который без сомнения скоро канет в небытие потому что его заминусовали — несколько интересных задач со старинной олимпиады. С Zlobober стали они обсуждать задачу T4:

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

Как возможно быстрее узнать фамилию человека на 1234567 месте? Ограничение по памяти — не более 32 магнитных лент (списков) и не более 64кб памяти с произвольным доступом.

А правда, как это решать?

Мне на ум приходит пока следующее:

Ну сначала препроцессим данные — отсортируем и заменим фамилии на порядковые номера по алфавиту например, после чего исходную ленту перезапишем в виде пары чисел. Это у нас займёт O(N*logN).

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

Допустим если фамилии были однобуквенные и люди стояли так:

A D R O C I T E

То после этого шага (который тоже займёт O(N*logN)) у нас будет две ленты:

AD CI DR IT OC RO TE
OC AD TE CI RO DR IT

Эти пары можно явно слить за один проход в тройки (отбрасывая AD и TE как концевые по тому признаку что для них нет пары):

OCI ADR CIT ROC DRO ITE

Эти тройки я опять могу скопировать и отсортировать по первым и последним буквам, потом слить и получить пятёрки, дальше фрагменты по 9, 17 и т.п. Собственно хранить эти фрагменты целиком необязательно, от каждого нужна первая и последняя буквы.

От каждого шага будем оставлять по одной отсортированной (по первым буквам) ленте — с двойками, тройками, пятёрками, девятками... Так у нас будут ленты с фрагментами длиной до 2^20 и их формирование займёт O(N*logN^2) по-моему.

В принципе после этого я могу любую фамилию на этих лентах отыскать также за O(N*logN).

Но мне сдаётся что у меня получается много лишних действий (хранение ненужных фрагментов в том числе) избавившись от которых можно было бы формирование лент ужать до O(N*logN). Кроме того Я ни на одном шаге не попытался использовать память с произвольным доступом.

Правильны ли мои размышления и что тут можно улучшить?

В то же время я подозреваю что лучше чем O(N*logN) сделать в принципе нельзя, но в зависимости от ухищрений константа может быть очень разная.