Седьмой любительский конкурс по программированию

[Zealint]

Модераторам: форум dxdy прорекламирован в видеопрезентации конкурса.

Предлагаю принять участие в седьмом любительском конкурсе по программированию.

Задача. Задан неориентированный граф $G=(V,E)$ без петель и кратных рёбер. Требуется посчитать в нём количество циклов длиной 3, 4, ..., n. (n - число вершин). Это называется статистика распределения циклов по длинам. Ограничение на число вершин $n\leq 21$ (для быстрых алгоритмов) и $n\leq 14$ для алгоритмов полного перебора.

Конкурс не совсем обычный, так как можно задействовать видеокарту GeForce 250 GTS и оба ядра процессора Core 2 Duo E8400.

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

[Circiter]

Zealint писал(а):

Требуется посчитать в нём количество циклов

Имеются ввиду простые циклы?

Может быть кому-нибудь будут полезны эти статейки:
N.Alon, R.Yuster, U.Zwick, Color-coding;
___, Finding and Counting Given Length Cycles.
В последней упомянутой работе, в частности даются "явные" формулы для $n\leqslant 7$.

[Zealint]

Цитата:

Имеются ввиду простые циклы?

Да, разумеется. Об этом сказано в презентации.

Цитата:

N.Alon, R.Yuster, U.Zwick, Color-coding;
___, Finding and Counting Given Length Cycles.
В последней упомянутой работе, в частности даются "явные" формулы для $n\leqslant 7$

Там нет формулы для k=7. Там есть только намёк на то, как она выводится. Саму эту формулу (как и остальные формулы до k=13) впервые получил мой коллега, на которого я ссылаюсь в видео.

[Zealint]

Конкурс завершился. Можно посмотреть итоги. Видео смотреть не обязательно, там только описание алгоритма имеет смысл, если кто-то его не изучал.

[cepesh]

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