Время: 14 дней (1 марта — 14 марта (утро) 2011 г.)
Конкурс завершён.
Посмотреть итоги.

Посмотреть рейтинг

Предлагаю принять участие в очередном любительском конкурсе по спортивному программированию. В очередной раз приза не будет — участие предполагается только для своего удовольствия, и если у Вас есть свободное время и желание посоревноваться. Как обычно, я провожу конкурсы по трудным задачам, то есть таким задачам, которые с наскока не берутся. По крайней мере, в своё время я их решил не сразу. Поэтому и время проведения предполагается 10 дней или больше, если этого не хватит.

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

Задачи

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

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

Требуется придумать такую сеть, на которой алгоритм Эдмондса-Карпа выполняет как можно больше итераций увеличения потока вдоль дополняющего пути. Для определённости, такой тест нужно подогнать именно под мою реализацию (специально написанную для конкурса). В моей реализации дополняющий путь ищется поиском в ширину, но каждый раз ищется лексикографически минимальный путь из всех путей с минимальной длиной (если считать, что путь — это последовательность вершин). Вот моя реализация (там же EXE файл, если кто-то не сможет скомпилировать, и один тест, чтобы был понятным формат ввода данных). Программа считывает из файла «file.in» сеть, ищет максимальный поток (из источника s в сток t) и выводит его значение в файл «file.out», в этот же файл выводится число итераций, которое пришлось сделать для нахождения максимального потока. Примечание: моя программа написана специально для конкурса и написана максимально понятно, в ущерб оптимальности. Сеть хранится в матрице. Поэтому не рекомендую использовать данный код для каких-то своих целей, он просто очень неоптимальный.

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

Описание параметров сети и формата её записи в файле

Все вершины сети пронумерованы числами от 1 до n. Во входном файле «file.in» в первой строке записывается 4 числа (n, m, источник s и сток t), а в последующих m строках записаны тройки чисел a, b и c, которые означают, что в сети есть ребро, идущее из вершины a в вершину b и имеющее пропускную способность c. Не должно быть мультирёбер (из одной вершины в другую может быть только одно ребро, при этом если есть ребро (a,b), то НЕ запрещается делать ребро (b,a), даже с другой пропускной способностью). Максимальное число вершин в сети не должно быть больше n=256 (можно меньше). Число рёбер m — не меньше нуля : ). Максимальная пропускная способность рёбер пусть будет 5 000 000 (чтобы значение максимального потока точно влезло в 32 бита со знаком). Источник и сток не должны совпадать. Петли (рёбра вида (a,a)) в сети не допускаются.

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

Пример

Пример прилагается в файле с программой. Там записана такая сеть:
6 7 1 6
1 4 2
1 2 2
2 3 1
4 3 2
2 5 2
3 6 2
5 6 2
Это означает, что в сети 6 вершин, 7 рёбер, источник имеет номер 1, сток — номер 6. Сама сеть выглядит вот так:

Здесь будет 4 дополняющих пути, все с пропускной способностью 1:
[1,2,3,6]
[1,2,5,6]
[1,4,3,6]
[1,4,3,2,5,6]

Конечно, никто не спорит, что здесь максимальный поток можно найти, сделав лишь 2 итерации, но программа-то ищет всегда лексикографически минимальный путь — именно так само и получается, если написать BFS естественным образом. И разумеется, что сам по себе алгоритм Эдмондса-Карпа не самый лучший, но давайте другие алгоритмы пока трогать не будем.

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

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

Задано натуральное n. Имеется шахматная доска размером 2n×2n. Сколькими способами можно расположить на ней n2 шахматных королей так, чтобы они не били друг друга? Например, для n=1 ответ 4 (один король может занять любую из 4 позиций доски 2×2). Для n=2 ответ 79. Более того, ответы для некоторых других значений n можно найти в сети очень быстро. Например, в энциклопедии под номером 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)
(n≥3),

а вот сама последовательность: [1,0,4,6,36,100,430,1470,5796,21336].

Порядок соотношения — это «глубина», то есть количество членов последовательности необходимое для получения её следующего члена. Степень соотношения — максимальная степень полинома, входящего в него. В последнем примере порядок равен трём, а степень — двум. Ответы для k=3 и k=4 тоже известны, они есть в энциклопедии: A117813 и A181072 соответственно.

Ваша задача состоит в том, чтобы вывести рекуррентные соотношения с минимальной степенью для k = 5, 6 и т. д. Кто больше — тот победил. Гарантируется, что ответ в таком виде существует для любого натурального k.

Формат представления и ограничения

Соотношение требуется представить в правильном формате (в котором оно у меня проверяется). Слева от знака «=» должно стоять выражение, включающее a(n), а справа — слагаемые, включающие a(n-1), … a(n-m) (если считать, что порядок равен m). Сами слагаемые могут идти в любом удобном для Вас порядке, а полиномы перед ними могут быть записаны любым удобным для Вас способом. Коэффициенты полиномов должны быть целыми. Знак умножения записывается как «*» и его нельзя опускать. А знак возведения в степень — «^». Например, соотношение для k=1 может быть записано любым из следующих способов:

n*a(n) = 4*(n-1)*a(n-2),
n*a(n) = (4*n-4)*a(n-2),
n*a(n) = (-4+4*n)*a(n-2),
n*a(n) = a(n-2)*(4*n-4),
n*a(n) = 4*n*a(n-2)-4*a(n-2),
n*a(n) = 4*n*a(n-2)+(-4)*a(n-2),
(n-1)*a(n) + a(n) = -a(n-2)-a(n-2)+4*n*a(n-2)-a(n-2)-a(n-2).

Дело в том, что я все равно приведу подобные слагаемые и сгруппирую все как нужно.

Если вы возводите в многозначную степень, то скобки не обязательны. То есть оба варианта n^10 и n^(10) — правильны, но первый лучше читается.

Главное: Соотношение должно быть линейным, а его коэффициенты должны быть полиномами, причём максимальная степень полинома должна быть минимально возможной. Файл, с ответом, который вы присылаете для участия в конкурсе не должен превышать 10 Mб.

Положения

Общие правила и ограничения

Решайте задачу как угодно, считайте на чём угодно. Побеждает тот, кто предоставит лучший ответ (что значит «лучший» — зависит от задачи). Задачи являются независимыми, поэтому у каждой будет свой победитель. В целях борьбы с беспределом кое-какие ограничения все же будут.

  1. Предоставляя ответ для некоторого n (в задаче 2) или k (в задаче 3), участник обязан сказать ответ также для всех меньших значений, но при условии, что они ещё не были получены остальными участниками. Например, если лидер сказал ответ для n=14 (в задаче 2), а Вы посчитали до n=16, то ответ засчитывается только если Вы также называет ответ для n=15.
  2. Конкурс завершается ровно через 10 дней (10 марта вечером, в 21:00 по московскому времени). Если понадобится, можно будет продлить. Хотя практика (см. предыдущие конкурсы) показывает, что все подобные задачи решаются в пределах 3-4 дней до своего предела (когда никто не может продвинуться дальше). [ Дополнение 10.03.2011: конкурс продлевается до 13.03.2011, 14-го числа будет подведение итогов. ]
  3. Я НЕ принимаю участия в конкурсе и НЕ вмешиваюсь в рассуждения участников и их решения от начала конкурса и до его завершения. Никому ничего не советую и не помогаю найти / понять / написать / скачать и т. д. Буду ограничиваться лишь общими комментариями по мере необходимости.
  4. Я оставляю за собой право менять правила проведения конкурса, если в них обнаружатся неточности.

Порядок проведения конкурса

  1. Во время проведения конкурса участники посылают на электронный адрес «zealint.comp@gmail.com» письмо с темой типа «Конкурс». В письме необходимо указать номер задачи (1, 2 или 3) и свой ник. Для первой задачи нужно прислать file.in с сетью. Для второй — значение n, для которого был посчитан ответ и сам ответ. Также требуется указать, на чём выполнялось вычисление (сколько ядер) и сколько минут (или часов (или дней)) заняли расчёты для указанного n. Желательно указать сам процессор. Будет вестись рейтинговая таблица, в которой указываются все участники и их результаты. Для третьей задачи — точно также, как и для второй — нужно прислать значение k и ответ для данного k. Желательно тоже указать, на чём считали и сколько времени ушло (это лишь для сравнения).
  2. Почта проверяется случайным образом (не меньше 4-5 раз в сутки), поэтому может возникнуть ситуация, когда несколько участников предоставляют один и тот же ответ, но кто-то раньше, а кто-то позже. В этом случае сравнивается дата попадания письма в ящик конкурса.
  3. Поскольку форума у меня нет, можно делиться впечатлениями и задавать вопросы либо в комментариях к этому посту (иногда комментарии попадают в «спам», поэтому нужно подождать, пока я их оттуда не вытащу), либо на форуме dxdy.ru в соответствующей теме, а также на Хабре (если вы перешли на эту страницу оттуда). [ Дополнение 01.03.2011: на Хабре мой пост забанили, хотя раньше этого не делали ].
  4. Прежде чем задать вопрос, участник должен убедиться, что похожего вопроса нет в FAQ (кроме вопросов о деньгах, о которых здесь речь не идёт).
  5. Проверку правильности ответов участников я беру на себя, но могут возникать ситуации, когда я не могу подтвердить какой-либо ответ (то есть я пока не в состоянии решить задачу для тех же входных данных для задач 2 и 3), в этих случаях буду отмечать такие ответы как «непроверенные». Их можно считать правильными, если они будут получены несколькими участниками независимо друг от друга.

Текущий рейтинг

Конкурс завершён.

Таблица участников

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

  1. зщл :: 08.03 :: 137 214 доп. путей.
  2. зщл :: 08.03 :: 48 600 доп. путей.

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

  1. зщл :: 14.03 :: n=20 :: 20 ядер (3 GHz) :: 18 ч.
  2. Костя Лопухин :: 12.03 :: n=19 :: 8 ядер (2.5 GHz) :: 2 ч. 50 м.
  3. Костя Лопухин :: 07.03 :: n=18 :: 1 ядро (2.9 GHz) :: 6 ч.
  4. Костя Лопухин :: 07.03 :: n=17 :: 1 ядро (2.26 GHz) :: 1 ч. 30 м.
  5. alexBlack :: 05.03 :: n=16 :: 1 ядро (2.9 GHz) :: 18 ч.
  6. alexBlack :: 04.03 :: n=15 :: 1 ядро (2.9 GHz) :: 3 ч. 30 м.
  7. alexBlack :: 03.03 :: n=14 :: 1 ядро (2.9 GHz) :: 43 м.
  8. alexBlack :: 03.03 :: n=13 :: 1 ядро (2.9 GHz) :: 1 ч. 50 м.
  9. alexBlack :: 03.03 :: n=12 :: 1 ядро (2.9 GHz) :: 16 м.

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

Пока нет участников.

Таблица значений

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

[ Примечание от 16.06.2011: ответы от n=21 до n=26 были получены после окончания конкурса, что обсуждалось на форуме в этой теме. Ответ для n=26 был получен на 8 ядрах по 2.66 ГГц приблизительно за 10 часов. Автор программы для отыскания последнего числа — участник конкурсов Shamil. ]

  1. 4
  2. 79
  3. 3600
  4. 281571
  5. 32572756
  6. 5109144543
  7. 1027533353168
  8. 254977173389319
  9. 75925129079783308
  10. 26568150968269086211
  11. 10749154284380665611224
  12. 4963704194366362387891227
  13. 2588716234142991968960920692
  14. 1511548995678989691821551648635
  15. 980916600918165029390915601861216
  16. 703066055325632897509116263399480311
  17. 553566164164538758951848363955159341236
  18. 476550132149153136812897667419399098606255
  19. 446700013633250141224116671772082056532427712
  20. 454253561073725156534218620121412788113502357703

  21. 499497358232990868471441676816136418783201589544420
  22. 592164459269741145142867933577242446750593983042233185
  23. 754867224182211583012273355207753302384758857649416296064
  24. 1032210451608310484545146750800038813036897244006452398722183
  25. 1510695366603970074479374959524695944196756884581589510634080548
  26. 2361658429416343345310712093583459956750032068219556304032803845397

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

Ответы очень длинные, поэтому записаны в текстовой файл.
Посмотреть TXT файл.
Сейчас в файле 4 соотношения.

Следите за конкурсами на моём блоге!

Информационные спонсоры

dxdy — Научный форум.

КиберФорум — форум начинающих и профессиональных программистов, системных администраторов, администраторов баз данных. Компьютерный форум.

Клуб ПРОграммистов — Форум программистов.

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