Конкурс про баян завершён и я, как обычно, позволю себе высказать собственные соображения о том, что происходило. Для начала хочу прояснить один момент: в некоторых местах я пишу, что задачи сложные (и что их с наскока не решить), а в других местах я много раз указывал, что задачи 1 и 3 являются халявой, при этом сложной я называл только задачу 2. Казалось бы, что я сам себе противоречу. А на самом деле имеется в виду следующее (на примере задачи 3): решить задачу 3 сложно в том смысле, что для неё сложно отыскать решение для достаточно большого входного параметра k. А простая она в том смысле, что для многих начальных значений k=5,6,7 (с которых предлагалось начать) и даже, наверное, k=8 эта задача решается тривиально. То есть принять участие в конкурсе мог любой человек, кто понял смысл прошлого конкурса — про решение целочисленных систем линейных уравнений. Теперь давайте по порядку.

Итоги

Задача 1. Про максимальный поток

Победителем объявляется участник зщл.

  1. зщл :: 137 214 доп. путей.

Задача 2. Про королевский баян

Победителем снова объявляется участник зщл. К сожалению, я пока не успел проверить его ответ для n=20, но он, скорее всего, правильный. Обязательно проверю в течение пары-тройки дней, будьте уверены. [Дополнение: ответ проверен]

  1. зщл :: n=20 :: 20 ядер (3 GHz) :: 18 ч.
  2. Костя Лопухин :: n=19 :: 8 ядер (2.5 GHz) :: 2 ч. 50 м.
  3. alexBlack :: n=16 :: 1 ядро (2.9 GHz) :: 18 ч.

Задача 3. Про блуждания на прямой

Участников нет. Поэтому победила сама задача : )

А что надо было делать?

Задача 1

Для алгоритма Эдмондса — Карпа известны тесты, на которых он выполняет O(n3) итераций поиска дополняющего пути НЕ ЗАВИСИМО от того, в каком порядке будут перебираться вершины при поиске самого короткого пути. Один из таких тестов я представил в своей статье (см. там Figure 1) на TopCoder.com 4 года назад, там у меня был отдельный ник для написания статей, я под ним мало выступал. Тест придумал не я, идея была позаимствована из статьи

Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.

Я просто изменил граф так, чтобы сеть была «плохой» не зависимо от способа поиска кратчайшего пути (саму сеть я нарисовал так, чтобы она была похожа на «гриб». Я её тогда называл «грибок»). Эта статья была написана ради получения $400 для того, чтобы сделать подсказку участникам на одних сборах по программированию, где я предлагал свой контест из 10 задач. Там была и похожая на эту задача, но её не решил никто. Хотя мне было известно, что 90% участников сборов выступают на соревнованиях TopCoder — и саму статью все они могли видеть, при этом они знали меня заранее и могли сопоставить рожу на фотографии (сделанной через старый мобильник в 2007-м) с моим настоящим лицом.

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

Задача 2

Здесь решение участников, занимающих 1-е и 2-е место явно быстрее, чем моё. Особенно быстрое решение у Кости. У меня есть давно написанный алгоритм решения «всех таких задач». Он универсальный для всех задач, решаемых методом матрицы переноса, нужно только указать способ кодирования состояний и правила перехода. Поэтому мой алгоритм (в силу универсальности) работает медленно. Но n=20, конечно, может посчитать. Поэтому о том, как написать быструю программу, вам лучше пусть расскажут сами участники, если захотят. Если они захотят поделиться своей идеей, я могу опубликовать её тут или отдельным постом. А может им хватит места в комментариях.

[ Дополнение: Костя предлагает свою реализацию. ]

Моя идея стара, как одна статья Герберта Уилфа (Herbert S. Wilf) 1994 года, в которой предлагалось считать расстановки «по слоям» шахматной доски, кодируя каждый слой парой чисел (K,x), где K означает номер клетки того короля, который самым первым стоит в правой половине своего 2×2 участка, а x — это битовое представление того, какие короли занимают верхнюю, а какие — нижнюю часть своего 2×2 участка (см. статью, там есть этот способ кодирования состояний). Далее в ход идут оптимизации: учёт симметрии, модулярная арифметика, можно также использовать meet-in-middle оптимизацию, плюс трюки с битовыми масками. Последнее я не делал, но если вы захотите посчитать ответ для n=24, без этого вряд ли получится.

В общем так, моё решение не самое лучшее. Участники здесь меня обошли, и это очень хорошо. Пусть делятся опытом с другими участниками : )

Задача 3

Это, товарищи, халява для некоторых начальных значений k. Для всех k сразу задача не решена вообще, и даже не ясно, можно ли её решить. Но принцип решения очень прост: вам даже можно было не писать программу, а запустить Maple, в котором есть функция listtorec из пакета gfun. По начальному отрезку последовательности эта функция даёт рекуррентное соотношение. Ну, допустим, вы этого не знали. Тогда вы можете решить задачу методом неопределённых коэффициентов. Например, пусть k=1. Вот сама последовательность

[1,0,2,0,6,0,20,0,70,0,252,...].

Предположим, что мы знаем порядок соотношения (он равен 2) и степень (она равна 1), тогда соотношение имеет вид:

(A*n+B)*a(n)=(C*n+D)*a(n-1)+(E*n+F)*a(n-2).

Здесь 6 неизвестных. Значит нужно взять 6 членов последовательности (со 2-го по 7-й) и подставить их в данное уравнение, чтобы получить 6 линейных уравнений. Почему со 2-го? У вас порядок равен 2, значит 0-й и 1-й члены будут как бы начальными. В левую часть вы можете подставить члены, начиная только со 2-го.

Теперь эту систему нужно решить 2 раза. Слева у вас либо A, либо B могут оказаться равными нулю (но не оба сразу). Сначала решаете в предположении, что B=1, переносите A*n*a(n) вправо и решаете. Если не получилось (соотношение оказалось неправильным), то полагаете A=1, переносите B*a(n) вправо и решаете. На какой-то из попыток решение будет найдено. Вы получите его в виде дробей, которые нужно умножить на общий знаменатель, чтобы решение стало целым. Зачем предполагать, что один из коэффициентов равен 1? Дело в том, что коэффициенты определяются с точностью до константы, поэтому нужна нормировка.

После подстановки и решения мы получим A=1, B=C=D=0, E=−F=4. Тут все сразу получилось в целых числах, поэтому умножать на общий знаменатель не требуется.

Вам даже не нужно вспоминать метод Дискона для решения СЛАУ, тут обычный Гаусс все решает — вы же не на скорость соревнуетесь, а на вывод ответа. И вообще, вам даже реализовывать ничего не нужно — любая нормальная система компьютерной алгебры умеет решать систему уравнений в целых числах.

Теперь по поводу минимальной степени: по исходным данным, которые я дал, можно догадаться, что минимальная степень соотношения будет равна k (это можно доказать строго, но не нужно). А вот порядок неизвестен. Ну тогда просто перебираем все порядки подряд, пока полученное вами соотношение не окажется правильным, скажем, для первой тысячи членов. Если подошло, значит оно, скорее всего, правильное. Для k=5 порядок должен быть 13, для k=6 — 15, потом 19, 21, 25 и дальше сами…

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

Так почему же эту задачу никто даже не пытался делать? Может быть её условие оказалось настолько непонятным или необычным для участников, что они даже не стали в ней разбираться? А между тем я в своё время любил так прикалываться: даёшь на олимпиаде задачу, в которой ответ всегда «Да», мутишь условие, вводишь десяток специальных терминов и наблюдаешь, как по окончанию олимпиады её никто даже не пытался сдать. Все вместо этого решали гробы, которые написаны более понятно. Ну ладно, пусть это будет тоже приколом, хотя если честно, задумка была не в том, чтобы пошутить, а в том, чтобы в этом конкурсе было что-то действительно простое и понятное. Среди всех таких комбинаторных задач, где получается семейство линейных рекуррентных соотношений с полиномами, эта — самая простая.

Выводы

Ну что я могу сказать по поводу конкурса? Опять было скучно. Участники накинулись на баян, а самые интересные задачи остались как бы за кадром. Первую задачу пытался решать лишь один человек, а третью — ни одного. Вторую же задачу решали многие, но в таблицу попали только трое. Мне действительно начало казаться, что делать три задачи на конкурсе неправильно. Нужно давать одну задачу, чтобы её действительно решали, и чтобы можно было сосредоточиться на чём-то одном и не отвлекаться лишний раз.

Ещё я заметил, что всё больше участников говорят какие-то слова про CUDA. Очень много домыслов по поводу этой чудной архитектуры. Наверно, имеет смысл устроить конкурс по решению задач на видеокарте. У меня есть GeForce 250 GTX и 1Gb памяти на ней. Может замутим что-нибудь? Только нужно взять трудную задачу, типа тех же королей, и такую, чтобы распараллеливание было нетривиальным. Распараллелить банальный цикл или перемножение матриц каждый сможет, а вот бывают такие задачи, где параллельность не очевидна… Кажется, у меня появилась одна идея, но осуществить я её смогу не раньше начала апреля, так как в конце марта мне надо ехать в командировку.

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

Обсуждение конкурса на форуме в этой теме.