Решения медленного человека. Подсчет количества независимых множеств.

Revision ru5, by dyatkovskiy, 2019-10-03 14:51:28

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" в данной маске.

Как выглядит наивное решение?

  1. Перебираем все подмножества данного множества. Зависимые, независимые — любые.
  2. Перебираем все вершины текущего подмножества, и убеждаемся, что они не инцидентны другим вершинам этого же подмножества. Иначе — данное множество "зависимое" и мы его пропускаем.
  3. Если множество независимое, учитываем его в подсчете.

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.

  1. Перебираем все подмножества данного множества. Зависимые, независимые — любые. (без изменений). И кстати, мы ведь также включаем в перебор пустое множество.
  2. Перебираем все вершины текущего подмножества, и убеждаемся, что они не инцидентны другим вершинам этого же подмножества. Иначе — данное множество "зависимое" и мы его пропускаем.

И здесь есть 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 или его подмножеством или вообще не соединено ни с чем из S1. Задумайтесь над этим.

Как же вычислить количество независимых 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;
}
Tags независимые множества, жадные алгоритмы, наивные алгоритмы, meet-in-the-middle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English dyatkovskiy 2019-10-12 16:28:18 5 Tiny change: ' counting.\n\nUnfort' -> ' counting.[cut]\n\nUnfort'
ru9 Russian dyatkovskiy 2019-10-12 16:27:07 5 Мелкая правка: ' конечное.\n\nСущест' -> ' конечное.[cut]\n\nСущест'
ru8 Russian dyatkovskiy 2019-10-05 14:22:24 85
ru7 Russian dyatkovskiy 2019-10-04 14:16:02 2 Мелкая правка: 'с чем из S1. Задумайт' -> 'с чем из S2. Задумайт'
en7 English dyatkovskiy 2019-10-03 18:01:57 34
ru6 Russian dyatkovskiy 2019-10-03 17:43:24 2 Мелкая правка: 'ем случае вы считаем ' -> 'ем случае мы считаем '
en6 English dyatkovskiy 2019-10-03 15:07:59 17
ru5 Russian dyatkovskiy 2019-10-03 14:51:28 107
ru4 Russian dyatkovskiy 2019-10-03 14:49:44 44 Мелкая правка: 'жествам S2 вычислять' -> 'жествам S2, вычислять'
ru3 Russian dyatkovskiy 2019-10-03 14:39:06 1 Мелкая правка: ' интересно начинаетс' -> ' интересное начинаетс'
ru2 Russian dyatkovskiy 2019-10-03 14:37:25 47
ru1 Russian dyatkovskiy 2019-10-03 14:35:33 10410 Первая редакция перевода на Русский
en5 English dyatkovskiy 2019-10-03 14:24:39 15
en4 English dyatkovskiy 2019-10-03 14:17:48 248
en3 English dyatkovskiy 2019-10-03 14:17:22 8
en2 English dyatkovskiy 2019-10-03 14:16:38 116
en1 English dyatkovskiy 2019-10-03 14:15:32 9511 Initial revision (published)