2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Максимальный поток, баян и блуждания на прямой – конкурс
Сообщение01.03.2011, 08:40 


26/01/10
959
Модераторам: ссылка на форум dxdy.ru, как на информационного спонсора, указана на странице конкурса.

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

На этот раз три задачи. Здесь приводятся краткие описания задач, а на странице конкурса (ссылка ниже) - полные описания.

Задача 1. Плохая сеть для поиска максимального потока.
Здесь предлагается отыскать сеть, в которой алгоритм Эдмондса-Карпа для поиска максимального потока выполняет как можно больше итераций поиска дополняющего пути. Данный алгоритм ищет минимальный по длине дополняющий путь, а в естественной реализации из всех минимальных выбирает лексикографически минимальный. Максимальное возможное число вершин - 256. Напомню, что теоретически алгоритм Эдмондса-Карпа выполняет $O(nm)$ поисков дополняющего пути, а на каждый поиск уходит $O(m)$ элементарных операций ($n$ - число вершин, а $m$ - число рёбер). И также напомню, что эта асимптотика является точной. Однако в конкурсе нужно придумать сеть, в которой число вершин ограничено, а количество операций поиска - максимально возможное для этого ограничения. У кого в сети будет больше итераций, тот и победил.

Задача 2. Королевский баян
Имеется шахматная доска размером $2n\times 2n$ ($n\in \mathbb N$). Сколькими способами можно расположить на ней $n^2$ королей так, чтобы они не били друг друга? Конкурс начинается от $n=12$, так как до 11 ответы известны уже более 10 лет [A018807].

Задача 3. Блуждания на прямой
Существует классическая задача о блуждании на прямой. Точка находится в начале координатной прямой и за один шаг обязана прыгнуть на $1, 2, \ldots, k$ делений вперёд или назад. Сколькими способами она может оказаться в начале координат ровно через $n$ шагов?
Для $k=1$ и $n=0,1,\ldots,10$ мы получим последовательность [1,0,2,0,6,0,20,0,70,0,252] (не надо обращать внимание на то, что здесь видны центральные биномиальные коэффициенты, это не важно). Последовательность удовлетворяет линейному однородному рекуррентному соотношению с полиномиальными коэффициентами:

$$
n\cdot a_n = 4\cdot (n-1)\cdot a_{n-2}, \qquad n\geq 2
$$

Ответы для $k=2,3,4$ тоже известны. Требуется вывести рекуррентные соотношения для $k=5,6,\ldots$. Кто дальше - тот и победил.

Несмотря на кажущуюся сложность, задача хоть и трудная (нет эффективного алгоритма для любого $k$), но не сложная для многих фиксированных $k$.

Если задачи Вас заинтересовали, прошу на страницу конкурса.

 Профиль  
                  
 
 
Сообщение14.03.2011, 19:55 


26/01/10
959
Конкурс завершился. Предлагаю ознакомиться с его итогами.

Вторую задачу удалось пробить до $n=20$, что весьма неплохо. Последнюю никто не пытался решать.

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:55 
Основатель
Аватара пользователя


11/05/05
4312
 i  Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group