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

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

Нужно задать скорость подачи топлива на ближайшие 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) сделать в принципе нельзя, но в зависимости от ухищрений константа может быть очень разная.

Four months ago I asked about existence of algorithmic solution for "Color Cubes" game.

Now I created the challenge based on this game — the goal is to gain maximum points:

Color Cubes challenge

Rules of the game are described in this exercise and here is also small playable demo to get better idea.

Here are current stats — you see that during last three days only three participants submitted successful solutions. Perhaps you will decide to join? Be sure, it requires only 10-15 minutes to write the simple code producing answer good enough to be submitted!

Challenge is not limited by any dead-line and no solution is going to be posted officially (though no one is restricted from discussing approaches)

Есть длинная (до 10^5 символов) строка W в которой мы ищем кусочки текста. Каждый запрос представляет собой строчку Si длиной Li (10-20 символов) и нас интересует наибольший префикс этой строки содержащийся в W. После выполнения каждого запроса строчка Si конкатенируется в конец W а из начала W отбрасывается такое же число символов Li (так что размер W остаётся постоянным). Наверное без ущерба можно считать что добавляются просто случайные символы, не обязательно сама Si.

Количество запросов на порядок (порядки) больше размера W.

А есть ли какая-нибудь "классическая/популярная" структура позволяющая эффективно осуществлять такой поиск? В рамках реализации LZ77 из которого эта задача украдена она наверняка решалась различными способами (на ум лезут сразу сложно-придуманные деревья и хэш-таблицы с возможностью выкусывания "отслуживших" частей — но именно что как-то сложно). Но есть ли что-то такое что must know (а я дурак не знаю)?

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

Дано: Xi, Yi, Ti — координаты и время регистрации взрыва каждым из датчиков (i = 1..4 больше всё равно не нужно, вроде).

Найти: X0, Y0, T0 — координаты и время самого взрыва.

Предполагаем что полигон плоский и скорость распространения волны постоянна и одинакова во всех направлениях (но неизвестна).

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

А вот как её решить изящно / красиво / аккуратно?

В 2009-м кажется году я её и решил, и сдал заказчику и контора вроде даже какие-то денежки получила. Но я совершенно не помню решения, а найти пояснительную записку которую тогда составлял не могу (да и я с тех пор пяток контор уж сменил).

Мне упорно кажется что у меня чуть ли не к линейной системе свелось всё и оказалось можно скорость исключить. Но когда я беру в руки карандаш и бумагу — мне перестаёт казаться что это возможно.

Сами мы не местные! Помогите старому склерознику! А то коллеги кому я эту задачку задал интересуются — а я запоздало обнаружил что сам не помню как решал :)

Update

PLEASE NOTE this post have become slightly outdated. Nowadays we have more automated process. So I have just remove outdated technical details and added more contemporary links.

Uptodate info:

Here is the E-maxx site in English: https://e-maxx-eng.appspot.com

And still here is github project with article sources: https://github.com/e-maxx-eng/e-maxx-eng

To contribute one just needs to create PR in github, so generally one even may work in github web-interface for the whole process. Detailed instructions are here https://e-maxx-eng.appspot.com/contrib.html

Older text follows below

Preface

Non-zero amount of users have suggested translating E-Maxx Algo to English. As far as I know some people even started translating in their blogs, though I'm not aware of any attempt seeing great advance and evolution.

This comment suggested to attempt to do this in collaborative manner using github.

I've created a project and pushed few files here. My idea is that we can write or improve articles in Markdown format (you know it since it is used in posts/comments on CF) using pull-requests here (at least at beginning).

The results are converted HTML pages and hosted at the google appengine website.

Remaining is removed to decrease bewilderment

I was somewhat surprised to learn that besides Pi Day celebrated on the 14-th of March we have Pi Approximation Day celebrated today, on the 22-th of July.

Don't be surprised, both link lead to the same page.

I'm curious, whether it is possible to invent the day for another well-known approximation 355 / 113? Well... It could be the 113-th minute of the 355-th day of the year — something closer to astronomic time notation...

Около месяца назад я постил вопросы о поступлении / обучении в магистратуре СПб Академического Университета.

Вчера посетил собеседование — попробую теперь что-то добавить к ответам на мои вопросы.

Человек который меня встретил и проводил на собеседование подозрительно похож на Dumpty (с точностью до фио).

Сначала тестовые задачи, как предупреждали в этом комментарии. Впрочем задачи оказались значительно проще чем я ожидал.

Не в том смысле что я всё решил и притом легко :) но для студента 1-2 курса произвольного технического ВУЗа они наверняка привычны — сходимость последовательностей / рядов (незамысловатых), задачка на программирование на уровне Div2 B может (когда мне подсказали что можно обойтись без доп.памяти, я потупив даже оптимальное решение сообразил), три из задач касались основ линейной алгебры (тут уж я тупил по-чёрному — единственный курс по ней я проходил в 2000-м году — например, меня спросили по-вашему, в определителе матрицы 3x3 всего 3 слагаемых, гы).

На собеседовании просматривали мои ответы на тестовые задачи, что-то уточнили, что-то подсказали. Предложили вспомнить быстродействие алгоритма Дейкстры (я сам его упомянул) — мучительно вспомнил что в нём можно использовать priority queue и со второй попытки ответил правильно.

Основной вопрос касался предполагаемой нагрузки — утверждают что уделять работе даже 20 часов в неделю — весьма сложно. Учитывая мой общий низкий уровень я склонен поверить.

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

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

Прокомментирую пару высказываний из упомянутого комментария:

Итак, процедура поступления непрозрачная. Ощущение, что берут по принципу понравился — не понравился.

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

Зачем-то заставили оставить под замком телефон с сумочкой, как-будто кто-то собирается обманывать или списывать.

Имхо ничего странного или страшного тут нет — сейчас и на ЕГЭ небось примерно так же — не сидеть же над душой у человека... :)

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

Напротив, мне собеседование понравилось. Люди вежливые, внимательные, приятные. Вопросы разноплановые, да, но не тупые и не заоблачные. Никто не запрещает сказать "не знаю". Возглавлял в моём случае, по-видимому Д.М. Ицыксон.

Заключение

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

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

В общем, хоть сам я погрузился в мучительные раздумия, но в целом мне понравилось и если кому магистратуру будет сложно выбирать — осмелюсь порекомендовать пособеседоваться здесь!

Как генерировать сочетания K элементов из N при условии что среди исходного множества некоторые элементы одинаковы? Например:

[1, 1, 2, 3, 3, 3]
по 3
[1, 1, 2]
[1, 1, 3]
[1, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]

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

В общем, буду рад ссылкам / намёкам.

Probably many of you already have heard of it — currently (8 a.m. June 16 2014 GMT) the site looks like this:

If no — you may want to take care of your credentials. Most people at forums are now discussing who used which passwords :)

I'm however mostly curious about other question: how may this happen, technically and to what extent which data are "compromised". As I remembered, Project Euler offered very little interaction with user:

• submitting answers;
• watching "friends";
• changing passwords and e-mails.

so probably it was hacked (if was) through other means — broken ssh, stolen admin passwords etc. — do not know. (though some people may hypothetize on recent heartbleed bug — I do not remember the site ever used https)

But if anyone have more knowledge of "how the ProjectEuler works" and what had happened and when it is going to return to life — please, share your info!

Итак в ходе дискуссий у некоторых коллег (и у меня) появилось желание порасспросить авторов раундов о том, как происходит подготовка раунда.

Официальная документация на CF даёт на этот вопрос скудный комментарий "Обратитесь к Геральду". По-видимому понятно что с этого процесс начинается — или, более детально, как подсказал dalex стоит подготовить задачи (в Полигоне или прям совсем "на словах"?) и показать их Геральду чтобы выяснить годятся ли они...

А остальное? Итак, попробую сформулировать несколько вопросов:

1. Сколько времени у вас уходит на то чтобы подготовить, выбрать, вспомнить или подыскать сами идеи задач — происходит ли это в течение дня-двух, или они постепенно рождаются недельку-месяц а потом вы начинаете думать "не применить ли их в контесте?"

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

3. Сколько сил (в человеко-часах) у вас лично отнимает подготовка раунда?

4. Как вы общаетесь с администрацией CF — сообщениями на сайте, почтой, скайпом или ещё что? Насколько этот процесс быстрый или медленный особенно если разные временные зоны?

5. Сколько итераций у вас могут пройти задачи прежде чем вы по их идеям достигнете согласия с администрацией и приступите непосредственно к подготовке раунда? Или задачи всегда "нравятся" с первой попытки?

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

7. Как выбираются тестеры для задач, как они участвуют в подготовке — например, советуют ли снять задачу, изменить количество баллов по ней и т.п.?

8. Требуется ли непосредственное участие автора во время проведения контеста? Поддерживается ли с ним постоянная связь скайпом и т.п.?

Если кто-то ещё вопросы подскажет, будет здорово.

А если кто-то из авторов решится таки написать пост, хотя бы небольшой — этакое сочинение "как я готовил раунд" — наверное его прочтут с большим интересом!

Я джва года хотел саит! (с) классик

http://www.codeabbey.com — а вот и он, встречайте! Ультрасовременный дизайн апеллирующий к временам когда вебсайты рисовали каменными топорами на шкурах! Множество сложнейших задач типа A+B, и A+B+C и даже A+B+C+D!

...

Русская версия этого поста немного отличается от английской.

Года три назад я был одержим наивной идеей написать Online Judge на манер TopCoder, потом я хотел сделать соревнования ботов для внутрикорпоративного использования, потом ещё что-то... Все эти идеи быстро приходили в упадок :)

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

Однако в самом начале выяснилось что сервера для тестирования решений и нужной инфраструктуры "пока" не будет, поэтому идея поменялась и функционал сайта стал похож на ProjectEuler или Rosalind — т.е. критерием решения задачи является отправленный ответ.

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

Недавно появился функционал для добавления задач за которые можно получать произвольное количество очков — т.е. ответ на которые может быть более или менее оптимальным.

...

Основной проблемой (ну, кроме дизайна, низкой посещаемости, ошибок в SEO) как обнаружилось является мой недостаточный опыт в решении и изобретении задач. Как результат — большинство задач очень простые, многие на тупую реализацию алгоритма по написанному. (т.е. это сайт не для СП-энтузиастов, а именно для начинающих, школьников изучающих языки и .п.) Вот пример "очень сложной" задачи (по позитивным отзывам пользователей) — сводящейся к простому ДП.

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

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

Сайт совсем-совсем бесплатный (хотя некоторые функции доступны лишь с определённого уровня). Я сначала хотел было монетизировать его с помощью небольших рекламных баннеров, но понял что миллионов я таким образом не заработаю и убрал чтоб не раздражать пользователей. :D

Неторопливо подумываю пойти в магистратуру.

Есть такое учебное заведение — Академический Университет — помню здесь были либо студенты, либо сотрудники оттуда — в связи с чем надеюсь на подсказки которых не могу найти на сайте.

Интересует магистратура CS или возможно SE — вот их краткие анонсы.

1. Есть ли очная или очно-заочная форма? Дело в том что работу бросать ради учёбы пока тоже сложно... Насколько сложно совмещать обучение с работой, если у кого есть опыт?

2. Будет ли легче учиться на SE чем на CS при наличии небольшого (лет 5) "industrial experience" в разработке ПО.

3. По SE: на 5 курсе работа заключается в выполнении выбранного студентом проекта — насколько возможно протолкнуть что-нить из собственных проектов, на что уже были потрачены силы и время год-два назад, чтобы сэкономить их теперь? Или всё определяется непреклонной волей преподавателя?

4. Ещё по SE: На шестом курсе из студентов формируются коллективы из 3-4 человек, работающие под руководством преподавателя — правильно понимаю что альтернативы развивать в одно жало проект с 5 курса при этом не предоставляется?

5. По CS: Насколько самонадеяно пытаться поступать на это направление если бакалавра получал в несколько другой области (автоматизация, промышленные контроллеры, электропривод) — или окажется что подготовка по математике и дискретной математике недостаточна и повесть будет печальной и мучительной?

Спасибо за подсказки/советы если таковые последуют!

A * B + C - D
(C + A * B) - D
C + (-D + B * A)

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

Ещё можно потестить на случайных наборах чисел — присваивать произвольные значения, считать результат и проверять что он совпадает. Этот вариант мне не нравится — тут и вопросы точности и т.п. :)

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

Всё действительно так сложно, или я не вижу какого-то более разумного пути?

P.S. Набор действий ограничим четырьмя (+ - * /).

P.P.S. М.б. в ОПН сравнивать выражения легче технически, но мне не кажется что суть это упростит.

А есть ли где-нибудь задача о счастливых билетах (тех у которых равны суммы цифр в половинках) со сравнительно большими ограничениями (больше тех которые на первом курсе в каждом втором вузе предлагают)? Ну в духе сколько есть счастливых билетов с 30-значным номером в 16-ричной системе счисления?

Гугл выдал пару ссылок на Тимус: 1044 из них простая, а 1036 вроде бы близко к тому что я ищу, но там предлагается считать билеты с заданной суммой и я, кажется, не пойму, насколько от этого становится проще / сложнее...

Если соединять вершины пятиугольника отрезками через одну, получается звездочка с 5 пересечениями между этими отрезками, как в детстве рисовали.

Если взять семиугольник, то вершины можно соединять через одну или через две. Получатся разные звёздочки с 7 или 14 пересечениями, если я не ошибаюсь. Ну и так далее.

А правда ли что для любых построенных таким образом звёздочек (ну по крайней мере если число вершин и шаг соединения вершин — который 1 для N-угольника и 2 для пятиконечной звезды — взаимнопросты) никакие три отрезка не будут пересекаться в одной точке?

UPD: спасибо Sammarize за уточнение — речь о правильных многоугольниках и звёздах, конечно.

Уважаемые коллеги и гуры :)

Есть всяческие задачки которые можно обобщить так:

• есть N лампочек;
• есть M выключателей;
• каждый из выключателей переключает (!) состояние некоторых (известно каких) лампочек.

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

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

Вообще это выглядит как система линейных уравнений на GF(2), но я пока не понял, приближает ли меня это к решению.

Уважаемые гуру, привет!

Есть популярная игрушка, для которой "популярного" названия я не знаю — видел её как "Color Cubes", "Brick Breaker", "Cube Crasher". Вот онлайновый пример.

Судь такая — прямоугольное поле, скажем, 20*30 заполняется квадратами 4 или 5 цветов. За каждый ход можно снимать группы квадратов одного цвета. Группой считаются соседствующие (по стороне) квадраты, т.е.:

1 2 1 1 1
2 2 1 3 3
3 2 2 1 1

Здесь есть одна группа цвета 2 из 5 квадратов и 3 группы цвета 1, из 4, 2 и 1 квадрата.

За снятые группы начисляются очки — причём обычно гораздо выгоднее снимать большие группы — впрочем прогрессия варьируется обычно вместе с правилами, например она может расти как N^2 или 2^N-1.

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

Заинтересовал вопрос — есть ли алгоритмическое решение которое позволяет для заданной начальной ситуации определить последовательность ходов, ведущей к максимально возможному результату (или сам максимальный результат)?

Или же с ростом размеров поля только эвристические решения возможны, неоптимальные?

Допускаю что это может зависеть от варианта правил, в частности от прогрессии очков.

В общем, подскажите если кто-то встречался, пожалуйста!

Извиняюсь если об этом уже писали — но есть подозрение что не все заинтересованные лица всегда вовремя узнают об этих событиях:

Google Code Jam 2014 — квалификация 11 апреля, продолжается 27 часов (вроде).

TopCoder Open 2014 / Algorithm — первые раунды 5, 12 и 26 апреля.

TopCoder Open 2014 / Marathon — первый раунд начинается 9 апреля.

Поздравляю всех коллег — любителей java!

Пример кода:

List<Widget> widgets = ... ;
int sum = widgets.stream()
    .filter(MyClass::isRed)
    .mapToInt(w -> w.getWeight())
    .sum();

public static boolean isRed(Widget w) {
    return w.getColor() == RED;
}

То о чём так долго говорили большевики — свершилось!

Лямбды и ссылки на методы, а главное туча непонятных вещей требующих изучения — в классах типа Stream, Collector, Consumer, BiConsumer и т.п. :)

На сайте Яндекс.Contest последняя новость о Яндекс.Алгоритм 2013... На странице соревнований единственная дата с 2014 годом у события test_test_1. Вроде бы даже зарегистрироваться можно и м.б. даже сабмитнуть. Но в целом выглядит так будто все ушли на фронт в подполье.

Я почему заинтересовался — думал, Интернет-Математика в 2013 году туда переехала (т.к. её кажется давно не было) — но вроде бы это не так.

В общем если не тайна, и если кто знает, поделитесь, есть ли какие новости после вот этой.

Как начали обсуждать, на подходе закон предусматривающий:

• регистрацию сайтов владельцами в Роскомнадзоре;
• предоставление данных о действиях пользователя "уполномоченным государственным органам".

Вот ещё раз ссылка (другого первоисточника я не видел) на статью.

Сам факт, как уже отметили, обсуждать смысла нет. Кому-то это не нравится — хотя в то же время сейчас владелец сайта:

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

Однако есть и насущные вопросы. Например, если закон такой появится то администрация Codeforces должна будет по необходимости предоставлять "органам" например переписку пользователей, как подсказал AndreySiunov.

Внимание, вопрос:

Быть может кому-то из пользователей страшно важно чтобы его переписка осталась его тайной и стоит до введения закона попросить администрацию удалить её? Чтобы и коллектив Codeforces не ставить в неудобное положение?

сразу оговорюсь, содержимого мой собственной переписки мне не жалко, я ещё и "корзину" могу за деньги продать — зато браузеры привык использовать в режиме incognito, почему-то

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

ПРОФЕССИЯ: ПРОГРАММИСТ

Введение:
Одна из самых важных задач в жизни — найти своё призвание... Если ваш ребёнок ещё не решил... можете рассказать о самых интересных профессиях, например о профессии ПРОГРАММИСТА.

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

Из окончания:
Будущему программисту надо развивать логику, память и сообразительность. В этом помогают логические тесты, задачи на IQ, игры "Что? Где? Когда?". Азы программирования открывает программа Logo, которую можно скачать в интернете. С ней разберутся даже детишки 3-го класса. Для школьников постарше увлекательный мир профессии открывает среда для программирования AgentSheets, которая позволяет сделать первые шаги в создании игр и моделировании разных явлений. Более серьёзную подготовку учащиеся могут получить в кружках или на занятиях с репетитором.

Журнал "Самая — женские советы", №2 Февраль 2014

А вы, коварные адепты святой науки — знакомы ли вы с программой (т.е. языком) Logo? Слыхали ли про AgentSheets? Мучали вас родители тестами на IQ? А может вы работаете прикладными программистами, т.е. пишете программы для компьютеров? Интересно в какой раздел попадают разработчики софта для бизнеса, языков программирования, баз данных и т.п. %)