Боря программирует

London Underground.

Мой контест, о котором я писал в этом посте, теперь доступен на CodeForces!

Расскажу про мою любимую задачу из контеста. К сожалению, она довольно сложная (ее решило 5 команд), но зато у нее прикольное решение.

Вам дан (прямо файлом, можно скачать) граф реального Лондонского метро. В нем 426 станций и 505 перегонов между ними. Нужно посчитать (по модулю 998244353) количество назависимых подмножеств в этом графе. Т. е. посчитать сколько всего существует способов выбрать какие-то вершины так, чтобы не было двух, которые соединены напрямую перегоном.

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

Как вообще можно считать количество независимых множеств в графе? Допустим, нам нужно посчитать его на графе, который выглядит как решетка размера 10х100 (в нем всего 1000 вершин, и вершина (i, j) соединена с (i+1, j) и (i, j + 1)). Для такого графа можно воспользоваться техникой под названием динамическое программирование по изломаному профилю. Идея в следующем. Будем идти по вершинам слева направо и сохранять "состояние" (всего 2^10 различных) вершин в последнем посещенном столбце. "Состояние" это то, какие вершины мы взяли в набор. И для каждого состояния будем хранить, сколькимя способами мы могли в него прийти. Дальше мы пытаемся добавить новую вершину и для каждого из 2^10 новых различных состояний посчитать количество способов в нем оказаться.

Можно обобщить этот алгоритм для произвольного графа. Будем добавлять вершины по одной, хранить состояния "кого взяли в множество из интересных вершин", и для каждого состояния их количество. При этом "интересные вершины" это те, у которых есть ребра в еще не посещенные вершины. В случае с решеткой это как раз вершины в последнем столбце. За сколько будет работать такой алгоритм? Примерно за количество различных состояний. Если добавлять вершины в случайном порядке, то скорее всего многие из них будут соединены с еще не посещенными и где-то в середине работы алгоритма придется хранить 2^200 состояний, что не реалистично.

Однако можно добавлять вершины в каком-то умном порядке, чтобы уменьшить количество состояний. Например, если бы в графе с решеткой мы бы добавляли вершины не слева направо, а сверху вниз, то пришлось бы хранить 2^100 состояний. Так что порядок очень важен! Как найти хороший порядок вершин для графа Лондонского метро? Заметим, что если у нас есть какой-то фиксированный порядок, то можно быстро посчитать сколько состояний для него придется хранить. Еще можно вспомнить, что граф нам дан, так что можно заранее его как-то предподсчитать.

Постоянные читатели моего блога наверняка знают какой алгоритм я очень люблю — Simulated Annealing. Можно начать со случайной перестановки и посчитать, сколько на нем будет работать алгоритм. Потом попробовать ее немного поменять и посмотреть, уменьшится ли количество состояний. Оказывается, что такими модификациями можно найти хорошую перестановку вершин, в которой общее количество состояний не будет превышать миллиона. А чтобы решить исходную задачу, можно захардкодить эту перестановку в решении, а потом воспользоваться динамическим программированием по изломаному профилю.

www.tgoop.com/bminaiev_blog/89

3.5K viewsFeb 15 at 12:40

London Underground.

Мой контест, о котором я писал в этом посте, теперь доступен на CodeForces!

Расскажу про мою любимую задачу из контеста. К сожалению, она довольно сложная (ее решило 5 команд), но зато у нее прикольное решение.

Вам дан (прямо файлом, можно скачать) граф реального Лондонского метро. В нем 426 станций и 505 перегонов между ними. Нужно посчитать (по модулю 998244353) количество назависимых подмножеств в этом графе. Т. е. посчитать сколько всего существует способов выбрать какие-то вершины так, чтобы не было двух, которые соединены напрямую перегоном.

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

Как вообще можно считать количество независимых множеств в графе? Допустим, нам нужно посчитать его на графе, который выглядит как решетка размера 10х100 (в нем всего 1000 вершин, и вершина (i, j) соединена с (i+1, j) и (i, j + 1)). Для такого графа можно воспользоваться техникой под названием динамическое программирование по изломаному профилю. Идея в следующем. Будем идти по вершинам слева направо и сохранять "состояние" (всего 2^10 различных) вершин в последнем посещенном столбце. "Состояние" это то, какие вершины мы взяли в набор. И для каждого состояния будем хранить, сколькимя способами мы могли в него прийти. Дальше мы пытаемся добавить новую вершину и для каждого из 2^10 новых различных состояний посчитать количество способов в нем оказаться.

Можно обобщить этот алгоритм для произвольного графа. Будем добавлять вершины по одной, хранить состояния "кого взяли в множество из интересных вершин", и для каждого состояния их количество. При этом "интересные вершины" это те, у которых есть ребра в еще не посещенные вершины. В случае с решеткой это как раз вершины в последнем столбце. За сколько будет работать такой алгоритм? Примерно за количество различных состояний. Если добавлять вершины в случайном порядке, то скорее всего многие из них будут соединены с еще не посещенными и где-то в середине работы алгоритма придется хранить 2^200 состояний, что не реалистично.

Однако можно добавлять вершины в каком-то умном порядке, чтобы уменьшить количество состояний. Например, если бы в графе с решеткой мы бы добавляли вершины не слева направо, а сверху вниз, то пришлось бы хранить 2^100 состояний. Так что порядок очень важен! Как найти хороший порядок вершин для графа Лондонского метро? Заметим, что если у нас есть какой-то фиксированный порядок, то можно быстро посчитать сколько состояний для него придется хранить. Еще можно вспомнить, что граф нам дан, так что можно заранее его как-то предподсчитать.

Постоянные читатели моего блога наверняка знают какой алгоритм я очень люблю — Simulated Annealing. Можно начать со случайной перестановки и посчитать, сколько на нем будет работать алгоритм. Потом попробовать ее немного поменять и посмотреть, уменьшится ли количество состояний. Оказывается, что такими модификациями можно найти хорошую перестановку вершин, в которой общее количество состояний не будет превышать миллиона. А чтобы решить исходную задачу, можно захардкодить эту перестановку в решении, а потом воспользоваться динамическим программированием по изломаному профилю.

BY Боря программирует