Алгоритм решения задачи Google Code Jam, учебник C

Question

Я хотел бы понять алгоритм, который решает Google Code Jam, Учебное пособие, Проблема C . До сих пор я написал мою собственную базовую реализацию , которая решает небольшую проблему. Я считаю, что он не может справиться с большой проблемой (сложность O (min (n, 2 * k)! Что составляет 30! В большем наборе данных).

Я нашел эту страницу решения , но решения, конечно, не документированы (контекст ограничен во времени). Я видел, что по крайней мере одно из решений использовало структуру данных Union Find , но я не понимаю, как это применяется здесь.

Кто-нибудь знает страницу с алгоритмами, решающими эти проблемы, а не просто код?

Answer 1

Не уверен, есть ли лучший способ справиться с этим почти дубликатом GCJ - Гамильтоновы циклы , но вот мой ответ оттуда:

Решение на основе O (2 ^k ) использует принцип включения-исключения . Учитывая, что существует k запрещенных ребер, существует 2 ^k подмножеств этих ребер, включая набор сам и пустой набор. Например, если бы было 3 запрещенных ребра: {A, B, C}, было бы 2 ³ = 8 подмножеств: {}, {A}, {B}, {C}, {A , B}, {A, C}, {B, C}, {A, B, C}.

Для каждого подмножества вы рассчитываете количество циклов, которые включают в себя по крайней мере все ребра в этом подмножестве. Если число циклов, содержащих ребра с , равно f (s) и S - это множество всех запрещенных ребер, тогда по принципу включения-исключения число циклов без каких-либо запрещенных ребер равно:

 sum, for each subset s of S: f(s) * (-1)^|s|

где | с | количество элементов в с . Другими словами, сумма количества циклов с любыми ребрами минус количество циклов с хотя бы одним запрещенным ребром плюс число с хотя бы двумя запрещенными ребрами, ...

Расчет f (s) не тривиален - по крайней мере, я не нашел простой способ сделать это. Вы можете остановиться и подумать, прежде чем читать дальше.

Чтобы вычислить f (s) , начните с числа перестановок узлов, не связанных ни с одним s узлами. Если существует m таких узлов, существует m ! Перестановки, как вы знаете. Позвоните на номер перестановок c .

Теперь рассмотрим края в с для цепей. Если есть какие-либо невозможные комбинации, такие как узел с 3 ребрами или подцикл в пределах s , тогда f (s) это 0.

В противном случае для каждого приращения цепи м на 1 и умножить c на 2m . (Есть m мест для размещения цепочки в существующих перестановках, и коэффициент 2 объясняется тем, что цепочка может быть вперед или назад.) Наконец, f (s) - c / ( 2 м ). Последнее деление преобразует перестановки в циклы.

Answer 2

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

Это задачи NP Complete, которые простыми словами означают быстрое решение которых не известно .

Для решения вопросов по Google Code Jam вы должны знать Algorimths Analysis and Design, хотя они могут быть решены в геометрической прогрессии, и не волнуйтесь, Google знает это очень хорошо. ;)

Для начала вам будет достаточно следующих источников:

1. Видео лекции MIT: «Введение в алгоритмы»

2. Учебные пособия по TopCoder

3. http://dustycodes.wordpress.com

4. Книга: Введение в алгоритмы [Cormen, Leiserson, Rivest & Stein]

5. Руководство по разработке алгоритма [Стивен С. Шиена]

Answer 3

Важным ограничением, накладываемым на входные данные, является то, что количество запрещенных ребер k <= 15.</p>

Вы можете продолжить путем включения и исключения:

• вычислить количество всех циклов ((n-1)!),
• для каждого запрещенного ребра e,вычтите количество циклов, которое его содержит ((n-2)! / 2, если n не очень мало),
• для каждой пары запрещенных ребер e, f, добавьте число циклов, содержащих обаих (это будет зависеть от того, касаются ли e и f),
• для каждой тройки ..., субстрата ...,
• и т. д.

Поскольку существует только 2 ^ k <= 32768 подмножеств F (множество всех запрещенных ребер), вы получите разумную оценку времени выполнения. </p>

The анализ проблемы с застреванием кода Google Endless Knight использует аналогичную идею.