Disclaimer: Решение не мое! Я просто разжевал его для себя. Ну и выложил еще здесь.
Недавно я разбирал решение задачи "1221G — Граф и числа"
И самой сложной и непонятной частью для меня был подсчет независимых множеств. Именно сам способ объединения двух под-решений в конечное.
Существующего объяснения, мне ясно дело не хватило (см. префикс ко всем моим разборам). Мне оно показалось скорее набором подсказок и не более.
Но должен заметить, что это отнюдь не критика. Нет, правда! Это отличная мотивация разобраться во всем самому. Иметь такие подсказки — гораздо лучше, чем не иметь ничего, и возможно даже лучше, чем иметь разжеванное объяснение вроде этого. Так что спасибо за это awoo и BledDest! И да, яб всем порекомендовал вначале попробовать решить задачу самостоятельно, и если вы потратили, скажем больше суток, читайте вначале legacy разбор. И если вы и после этого нечего не поняли, читайте этот текст.
В оригинальном коде с решением тоже нет никаких коментов. Но опять таки, все равно — спасибо! Вы можете либо просто использовать его, либо, если вы не понимаете в чем тут суть, вам придется как следует в него повсматриваться. Если вы и после этого ничего не поняли. Снова — добро пожаловать в этот пост!
В общем дальше нечто вроде reverse engineering оригинального разбора. А именно разжевывание сути функции countIndependentSets.
Я не использовал тег spoiler. Так что, если вы не хотите читать разбор, остановитесь немедленно. И не смотрите вниз!
Tutorial
Наивное решение подсчета независимых подмножеств занимает O(N*2^N), при N=40 это примерно O(k*40*256*4млрд). Число неподъемное для обычных компов.
Так что, предлагается рассмотреть подход meet-in-middle ("встретимся посредине"). Это означает, что мы выполняем вычисления для половинок множеств, и затем как-нибудь пытаемся объединить их в конечный результат. В нашем случае мы считаем независимые множества. И если сделать это брут-форсом для половинок мы получим сложность O(N*2^(N/2)), при N=40 это уже можно сделать на обычном компьютере.
Итак. В данной задаче мы представляем граф как набор инцидентных масок IM[i] для каждой вершины. Или говоря по-русски, набор соседей. Другими словами IM[i] представляет собой набор ребер, которые исходят из i-ой вершины к вершинам, которые промаркированы "1" в данной маске.
Как выглядит наивное решение?
- Перебираем все подмножества данного множества. Зависимые, независимые — любые.
- Перебираем все вершины текущего подмножества, и убеждаемся, что они не инцидентны другим вершинам этого же подмножества. Иначе — данное множество "зависимое" и мы его пропускаем.
- Если множество независимое, учитываем его в подсчете.
Runtime алгоритма O(N*2^N).
Meet in the middle (M-I-M).
Делим множество на два подмножества: S1 и S2.
Далее в тексте если мы говорим о каком-то подмножестве множества S1, мы можем называть его SS1, аналогично для множеств из S2 мы будем пользоваться обозначением SS2.
Для того, чтоб M-I-M стал возможен нам нужно собирать кое-какие дополнительные данные для S1.
Затем используя эти данные мы можем, идя по подмножествам S2, вычислять уже непосредственно результат. И делать это жадно :-)
Но как?
Самое интересное начинается здесь
Пусть у нас есть некое независимое подмножество SS2 (из множества S2). Для него существует k и только k независимых подмножеств из S1, которые никак не соединены с ним, назовем этот набор SS1SS2. Именно с ними будет образован полный набор комбинаций независимых подмножеств S=S1+S2, в которых обязательно участвует SS2. Получается, что для SS2 у нас будет 1+|SS1SS2| комбинаций. Само подмножество SS2, плюс всевозможные соединения с одним и только одним подмножеством из SS1SS2.
Но! Если мы включим пустое множество в SS1SS2, то мы избавимся от "1+" в нашей формуле. И получим просто значениe |SS1SS2|.
Если для каждого SS2 мы на этапе решения для S1 соберем значения |SS1SS2|, то, перебирая независимые подмножества SS2, мы будем просто добавлять к конечному ответу значение |SS1SS2|. Это число учтет как само SS2, так и все его комбинации с независимыми подмножествами SS1.
Answer += |SS1SS2|.
Как же получить это славное число |SS1SS2|?
Нам придется немного поправить алгоритм для S1.
- Перебираем все подмножества данного множества. Зависимые, независимые — любые. (без изменений). И кстати, мы ведь также включаем в перебор пустое множество.
- Перебираем все вершины текущего подмножества, и убеждаемся, что они не инцидентны другим вершинам этого же подмножества. Иначе — данное множество "зависимое" и мы его пропускаем.
И здесь есть UPD: У каждой вершины есть маска инцидентности. Эти маски будем складывать OR-м. В результате получится маска представляющая набор всех вершин которые инцидентны с вершинами из SS1. Если мы из этой маски исключим вершины из S1, тогда останутся только врешины из S2, образуя некое SS2. И данное SS1 будет инцидентно именно SS2. Когда мы говорим что множество А инцидентно множеству B, мы имеем в виду максимально возможное множество вершин B, которым инцидентны вершины из A.
Очевидно, что мы можем столкнуться с каким-то SS2 несколько раз. Ведь вполне может статься, что несколько SS1 инцидентны SS2. У нас будет некий счетчик "столкновений" с SS2 (cnt[SS2]). И если SS1 независимо, то мы будем увеличивать этот счетчик на 1.
Шаг 3. После шага 2, в этом счетчике для cnt[SS2] будет хранится общее количество независимых SS1 которые инцидентны именно SS2 ("именно" значит, что инцидентно не его подмножеству и не одному из его надмножеств, а конкретно SS2).
Шаг 4. Для каждого подмножества SS2 (в том числе и самого SS2), пройдемся по всем его подмножествам и сложем все их cnt значения, сохраним их обратно в cnt[SS2].
Теперь это число будет означать количество независимых подмножеств инцидентных либо SS2 либо его подмножеству но не его надмножествам. Столкновения {} из S1 c единственно возможным вариантом из S2, который будет еще одним {} тоже учитываются.
Весь шаг №4 на самом деле тоже можно уложить в сложность O(N*2^(N/2)). Если применить жадный алгоритм, ну или вернее — динамическое программирование. В общем, смотрите код ниже :-).
И тут очень важный момент!
Очень важный момент.
Пустое множество. Поскольку SS2 включает {} как подмножество, то cnt[SS2] включает в себя и количество таких независимых SS1, которые вообще никак не соединены с S2. И получается, что cnt[SS2] будет хранить то, что соединено с SS2 или его подмножеством или вообще не соединено ни с чем из S2. Задумайтесь над этим.
Как же вычислить количество независимых SS1 которые НЕ соединены с SS2?
В общем надо пойти от обратного. Рассмотрим множество S2\SS2 (S2 без SS2).
cnt[S2\SS2] хранит в себе количество независимых SS1 либо вообще не соединенных с S2, либо соединенных с чем угодно, но только не с вершинами SS2. Это то, что нам нужно! |SS1SS2| это на самом деле cnt[S2\SS2]!
S2
Теперь, во время нашего прохода по независимым SS2 (аналогичный наивный перебор), для каждого SS2 мы берем число |SS1SS2|=cnt[S2\SS2] и добавляем его к ответу.
Тут лично я немного встрял на моменте с пустыми множествами. Чтобы учесть SS2 сам по себе, нужно по сути, чтобы была учтена его связь с пустым множеством из S1. Такая связь учитывается см. пункты №4 и №1 дополненного алгоритма. Да там два пустых подмножества. Вернее оно конечно всегда одно, но в данном случае его удобно раздвоить, поскольку рассматриваются комбинации когда мы делаем пустую выборку из S1 и потом в каких-то случаях сочетаем ее с пустой выборкой из S2.
Ниже код BledDest-а, функция countIndependentSets c моими коментами.
const int N = 40;
const int M = 20;
long long incident_mask[N];
// ...
long long cntmask[1 << M];
// ...
long long countIndependentSets()
{
// S2 will have 20 or less vertices
int m1 = min(n, 20);
// S2 will contain the rest
int m2 = n - m1;
//cerr << m1 << " " << m2 << endl;
// cntmask is actually what we called "cnt" in our tutorial
memset(cntmask, 0, sizeof cntmask);
// Go over all subsets SS1, "i" is SS1
for(int i = 0; i < (1 << m1); i++)
{
long long curmask = 0;
bool good = true;
// Go over all vertices "j" and skip ones that doesn't belong to SS1
for(int j = 0; j < m1; j++)
{
if((i & (1 << j)) == 0)
continue;
// If "j" is in current incident mask already,
// then it is incident to some of vertices from current SS1
// mark such SS1 as dependent (good=false).
if(curmask & (1 << j))
good = false;
// Otherwise register "j" in incidence mask, and also register all its
// incident vertices.
curmask |= ((1 << j) | incident_mask[j]);
}
if(good)
{
// SS1 is independent,
// SS2 = high(curmask) = (curmask >> m1) represent SS2 that SS1 incident to.
// See step #3 of updated algorithm.
cntmask[curmask >> m1]++;
}
}
// This is step #4,
// This is how we enumerate all SS2, and also its subsets, and
// accumulate exact bumps of all its subsets.
// I would probably reorder that loops, though.
for(int i = 0; i < m2; i++)
for(int j = 0; j < (1 << m2); j++)
if(j & (1 << i))
cntmask[j] += cntmask[j ^ (1 << i)];
// This is a naive variation for S2 part calculations
long long ans = 0;
// Go over all subsets of S2, namely SS2=i
for(int i = 0; i < (1 << m2); i++)
{
long long curmask = 0;
bool good = true;
// Go over all vertices "j" and skip ones that are not in SS2=i
for(int j = m1; j < n; j++)
{
if((i & (1 << (j - m1))) == 0)
continue;
// Filter out dependent sets
if(curmask & (1ll << j))
good = false;
curmask |= (1ll << j) | incident_mask[j];
}
if(good)
{
// If SS2 is independent count all its combinations with
// independent subsets from S1, including combination with {}.
// Here (i ^ ((1 << m2) - 1)) actually selects subset S2\SS2.
// and thus cntmask[S2\SS2] means |SS1SS2|
//cerr << i << endl;
ans += cntmask[(i ^ ((1 << m2) - 1))];
}
}
return ans;
}
