Брой 26 на Списание Инфоман
 


Национална олимпиада по информатика 2004, Задача 1.1. МИНИМУМ

Уловието на задачата може да прочетете тук.

Решение

Задачата може да се реши много лесно ако приложим метода на грубата сила и проверим за всяка комбинация от стойности на променливите каква ще е сумата от функциите и изберем най-малката такава. За съжаление такова решение има сложност O(2n.m) и за n=29 и m=9 няма да се вмести във времевото ограничение. Въпреки това решението не се отдалечава много от времевото ограничение и ако успеем да оптимизираме елементарното решение ще постигнем желания ефект.

Една лесна оптимизация е ако някоя променлива не участва в нито една функция няма да я включваме в изчерпването. Въпреки това може да се случи, че всички променливи участват в поне едно уравнение. Друга сравнително лесна оптимизация е ако някоя променлива участва само в една функция. Тогава може да извадим тази променлива от променливите, от които зависи функцията. Когато извадим една променлива от множеството на променливите на функцията се променя и множеството на стойностите на функцията. И по-точно то става два пъти по-малко. Какви ще бъдат новите стойности, които ще заема функцията. Нека вземем една комбинация от стойности на останалите променливи в множеството на функцията. В предишното множество от променливи са съществували две подобни комбинации от стойности. В едната от комбинациите отстранената променлива е била нула, в другата единица, а всички останали променливи имат стойности като в редуцираната комбинация (тази без отстранената променлива). Стойността, която ще съпоставим на комбинацията от редуцираното множество ще бъде по-малката от двете в нередуцираното множество. Логиката е, че щом премахната променлива участва само в тази функция, за всяка комбинация от другите променливи може да изберем стойност на отстранената променлива, която ще даде по-малка стойност на функцията. Така съумяхме да премахнем и променливите, които участват в само една функция.

Дали тези две оптимизации ще бъдат достатъчни. Според условието никоя функция не зависи от повече от пет променливи. Това значи, че имаме най-много 45 участия на променливи във функции. От друга страна за да участва всяка от 29 променливи в поне две функции са ни нужни поне 58 участия. Очевидно подобно нещо е невъзможно. Лесно се вижда, че в най-лошия случай ще трябва да изчерпваме по 22 променливи, като всяка от тях участва в поне 2 функции. Което е достатъчно подобрение и ще реши задачата за отпуснатото време.

Техническата реализация на решението включва използване на побитови операции. Стойностите които заема една функция ще бъдат съхранявани в масив, като позиция x ще отговаря за комбинация от стойности на променливите съответстваща на побитовото представяне на x. По-точно ако бит i на x е 1, то и променлива i има стойност 1. За всяка функция също ще пазим броя на променливите, от които зависи, както и масив от самите променливи. За променливите ще пазим в колко функции участват, както и една от функциите в които участват. Така ако някоя променлива участва в една функция ще знаем точно коя. В примерната реализация има две важни функции – findmin и compress. Първата генерира всички комбинации от стойности за променливите, които участват в поне две функции. Втората функция премахва променлива, която участва само в една функция, като преизчислява множеството от заеманите от функцията стойности.

Примерна реализация

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


const int maxn = 29;
const int maxm = 9;
const int maxc = 32;


int n, m, minval;
int func_val[maxm][maxc];
int var_count[maxm];
int vars[maxm][5];
int used[maxn], by_func[maxn];


void solve();

int main()
{
	solve();

	return 0;
}

void solve()
{
	int i, j;
	int comb[maxn];

	void findmin(int l, int comb[]);
	void compress(int x);

	scanf("%d%d", &m, &n);
	for (i = 0; i < m; i++)
	{
		scanf("%d", var_count + i);
		for (j = var_count[i] - 1; j >= 0; j--)
		{
			scanf("%d", vars[i] + j);
			vars[i][j]--;
			used[vars[i][j]]++;
			by_func[vars[i][j]] = i;
		}
		for (j = 0; j < 1 << var_count[i]; j++)
			scanf("%d", func_val[i] + j);
	}

	for (i = 0; i < n; i++)
		if (used[i] == 1)
			compress(i);

	minval = 10000;
	findmin(0, comb);

	printf("%d\n", minval);
}

void findmin(int l, int comb[])
{
	int i, j, x, val;

	if (l == n)
	{
		val = 0;
		for (i = 0; i < m; i++)
		{
			x = 0;
			for (j = 0; j < var_count[i]; j++)
				if (comb[vars[i][j]])
					x += 1 << j;
			val += func_val[i][x];
		}

		if (val < minval)
			minval = val;
	}
	else
	{
		comb[l] = 0;
		findmin(l + 1, comb);

		if (used[l])
		{
			comb[l] = 1;
			findmin(l + 1, comb);
		}
	}
}

void compress(int x)
{
	int i, pos, f, mask1, mask2;
	int new_val[maxc];

	f = by_func[x];
	for (pos = 0; vars[f][pos] != x; pos++)
		;

	var_count[f]--;
	for (i = pos; i < var_count[f]; i++)
		vars[f][i] = vars[f][i+1];

	mask1 = (1 << pos) - 1;
	mask2 = ~mask1;

	memset(new_val, 0, sizeof(new_val));
	for (i = 0; i < 1 << var_count[f]; i++)
		new_val[i] = min(func_val[f][(i&mask1)|((i&mask2)<<1)|1<<pos],
			func_val[f][(i&mask1)|((i&mask2)<<1)]);
	memcpy(func_val[f], new_val, sizeof(new_val));

	used[x] = 0;
}

			

Автор: Иван Анев


обратно към брой 26