В моей прошлой теме администратор дал добро на размещение подобного рода объявлений.

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

Кого интересует, добро пожаловать на страницу конкурса.

Конкурс любительский - just for fun, как говорится. Без призов. По случаю первого дня весны.

С некоторой оговоркой: "думаю, пока люди проявляют интерес и обсуждают задачи, нет ничего плохого".

А для этого было бы неплохо процитировать условия задач здесь...

Хорошо. Можно процитировать условия. Но не всё подряд, а самые важные моменты. Все подробности и нужные ссылки лучше пусть останутся на странице конкурса.

Задача 1. Плохая сеть для задачи о максимальном потоке.

Для решения задачи о максимальном потоке существует большое количество алгоритмов и методов. Пожалуй, наиболее известный из них – это метод Форда-Фалкерсона и модификация Эдмондса-Карпа для него (когда дополняющий путь выбирается с наименьшей возможной длиной). Пусть n – число вершин в сети, а m – число рёбер. Известно, что алгоритм Эдмондса-Карпа работает за время O(nm^2) (можно доказать, что дополняющий путь потребуется искать не более O(nm) раз и время поиска такого пути не больше O(m)). В реальных задачах эта оценка не достигается, хотя существует специальный извращённый тест, подтверждающий асимптотику. Поскольку это конкурс по спортивному программированию, то предполагается, что участники знакомы с этим классическим алгоритмом.

Требуется придумать такую сеть, на которой алгоритм Эдмондса-Карпа выполняет как можно больше итераций увеличения потока вдоль дополняющего пути. Для определённости, такой тест нужно подогнать именно под мою реализацию (специально написанную для конкурса). В моей реализации дополняющий путь ищется поиском в ширину, но каждый раз ищется лексикографически минимальный путь из всех путей с минимальной длиной (если считать, что путь – это последовательность вершин). На странице конкурса предлагается скачать мою реализацию этого алгоритма, с помощью которой участники смогут тестировать свои сети. Там же приводится пример простой сети с картинкой. Участникам предлагается ограничиться сетью из 256 вершин без петель и кратных дуг.

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

Баяном задача названа по причине своей чрезвычайной заезженности. Однако так далеко, как я предлагаю, её ещё никто не решал.

Задано натуральное n. Имеется шахматная доска размером 2n×2n. Сколькими способами можно расположить на ней n^2 шахматных королей так, чтобы они не били друг друга? Например, для n=1 ответ 4 (один король может занять любую из 4 позиций доски 2×2). Для n=2 ответ 79. Более того, ответы для некоторых других значений n можно найти в сети очень быстро. Например, в энциклопедии oeis.org под номером A018807 (эти значения были посчитаны ещё до 2000 года). Поскольку ответы до n=11 уже известны (на самом деле известны и дальше, но искать сложнее), будем начинать конкурс от n=12. Как обычно, у кого больше n, тот и победил. Ответы для достаточно больших n у меня есть, будем надеяться, что этого хватит для проверки ответов участников.

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

Есть числовая прямая. Точка находится в позиции 0 на этой прямой. Точка за один шаг может (и обязана) переместиться на 1, 2, …, k единиц вперед или назад. Сколькими способами можно, выполнив ровно n шагов, вернуться в начало координат? Например, если k=1, то для n=0,1,2,…,10 ответы будут, соответственно 1,0,2,0,6,0,20,0,70,0,252. Данная последовательность (обозначим её через а(n)) удовлетворяет линейному рекуррентному соотношению с полиномиальными коэффициентами: 

n*a(n) = 4*(n-1)*a(n-2) (n≥2).

То есть, например, при n=2 имеем 2*2=4*(2-1)*1 или при n=10 имеем 10*252=4*(10-1)*70.

Ответ для k=2 имеет вид

-2*n*(2*n-1)*a(n) = (17*n^2-77*n+60)*a(n-1)+(-78*n^2+222*n-180)*a(n-2)+(-216*n^2+972*n-1080)*a(n-3),
а сама последовательность [1,0,4,6,36,100,430,1470,5796,21336,...]

На странице конкурса также даны ссылки на известные решения для k=3,4 и предлагается решить задачу для k=5,6,... и так далее, кто дальше.

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