Dünaamiline planeerimine

1. Klassikalisi ülesandeid

1.1. Pikim kasvav osajada

Ülesanne. Antud massiiv, mis koosneb \(n\) täisarvust. Kustuta võimalikult vähe elemente nii, et järgi jääks kasvav jada. \(n \le 10^3\).

Proovime alustuseks välja mõelda rekursiivse funktsiooni, mis ülesannet lahendaks.

vector<int> arr; // massiiv, mille pikim kasvav osajada leida

// lis(x) - pikima sellise kasvava osajada pikkus,
// mille viimase elemendi indeks on x.
int lis (int idx) {
	// alati on võimalik, et see osajada koosneb ainult idx-ndast elemendist
	int ans = 1;

	// teine variant on, et selles osajadas on veel elemente
	// kui osajadast viimane element eemaldada, saame uue kasvava osajada,
	// mille viimane element on väikesem.
	// kindlasti on ka see osajada pikim võimalike seas
	for (int i = 0; i < idx; i++) {
		if (arr[i] < arr[idx]) {
			ans = max(ans, 1 + lis(i));
		}
	}

	return ans;
}

See algoritm annab kindlasti õige vastuse, aga kui seda proovida \(n = 1000\) juures, on see kaugelt liiga aeglane:

lis(n - 1) kutsutakse välja ühe korra;
lis(n - 2) kutsutakse välja ühe korra lis(n - 1) poolt;
lis(n - 3) kutsutakse välja kaks korda: ühe korra lis(n - 1) poolt ja ühe korra lis(n - 2) poolt;
lis(n - 4) kutsutakse välja neli korda: ühe korra lis(n - 1) poolt, ühe korra lis(n - 2) poolt ja kaks korda lis(n - 3) poolt;
lis(n - 5) kutsutakse välja kaheksa korda: ühe korra lis(n - 1), ühe korra lis(n - 2), kaks korda lis(n - 3) ja neli korda lis(n - 4) poolt.

Sama arutelu jätkates saame teada, et lis(0) kutsutakse välja \(2^{n - 2}\) korda. Probleem on selles, et iga kord, kui lis(x) välja kutsutakse, hakkame me kogu arvutuskäiku uuesti tegema, mis viib väljakutsete arvu eksponentsiaalse kasvuni. Meie rekursiivne funktsioon aga ei muuda kuidagi mingeid globaalseid muutujaid: iga kord, kui lis(5) välja kutsutakse, on vastus täpselt sama. Seega on mõistlik selle väärtus pärast esimest korda meelde jätta.

vector<int> arr;

// vektorid pikkusega n - kui has_memo[i] == 1, siis on lis(i) väärtus juba
// välja arvutatud ja salvestatud samasse kohta vektoris memo
vector<int> has_memo;
vector<int> memo;

int lis (int idx) {
	if (has_memo[idx])
		return memo[idx];

	int ans = 1;
	for (int i = 0; i < idx; i++)
		if (arr[i] < arr[idx])
			ans = max(ans, 1 + lis(i));

	has_memo[idx] = 1;
	memo[idx] = ans;
	return ans;
}

Nüüd on algoritm piisavalt kiire. Iga x jaoks tehakse lis(x) arvutamise sisuline töö läbi ainult ühe korra, mis võtab \(O(n)\) aega. Erinevaid x väärtusi on \(n\) tükki, seega kokku on keerukus \(O(n^2)\).

Milleks aga üldse rekursiivset funktsiooni vaja on? Teame, kuidas lis(x) väärtust arvutada, kasutades lis(0), lis(1), ... , lis(x - 1) väärtuseid. Seega võime need väärtused lihtsalt järjest välja arvutada:

vector<int> arr;

vector<int> lis (n);
for (int k = 0; k < n; k++) {
	lis[k] = 1;
	for (int i = 0; i < k; i++) {
		if (arr[i] < arr[k])
			lis[k] = max(lis[k], 1 + lis[i]);
	}
}

Täpselt samal meetodil on võimalik ka kasvavaid osajadasid loendada.

Mõnikord on vaja lisaks pikkusele leida ka pikim kasvav osajada ise. Selleks on kõige lihtsam võimalus jätta iga DP väärtusega koos meelde, milline varasem DP väärtus "selleni viis", s.t. missuguse k väärtuse juures oli 1 + lis[k] suurim.

1.2. Pikim ühine osajada

Ülesanne. Antud massiivid \(A\) ja \(B\). Kustuta kummastki massiivist võimalikult vähe elemente nii, et pärast kustutamist oleksid mõlemad massiivid samad. Kummagi massiivi pikkus on ülimalt \(10^3\).

Alustame ülesande lahendamist samamoodi, nagu eelmises ülesandes: defineerime rekursiivse funktsiooni, mis kuidagi ülesande lahendab. Seekord: olgu lcs(i, j) massiivi \(A\) esimese \(i\) ja massiivi \(B\) esimese \(j\) elemendi pikim ühine osajada.

lcs(i, 0) ja lcs(0, j) on muidugi nullid.
Kui \(A[i - 1] = B[j - 1]\), siis on võimalik, et pikima ühise osajada viimane element ongi see, ja lcs(i, j) on 1 + lcs(i - 1, j - 1).
Igal juhul on võimalik, et \(A[i - 1]\) ei osale pikimas ühises osajadas ja lcs(i, j) on sama, mis lcs(i - 1, j).
Samamoodi on võimalik, et \(B[j - 1]\) ei osale osajadas ja lcs(i, j) on lcs(i, j - 1).

Kokku pannes:

vector<int> A;
vector<int> B;

int lcs (int i, int j) {
	if (i == 0 || j == 0) {
		return 0;
	}

	int ans = 0;
	if (A[i - 1] == B[j - 1]) {
		ans = max(ans, 1 + lcs(i - 1, j - 1));
	}

	ans = max(ans, lcs(i - 1, j));
	ans = max(ans, lcs(i, j - 1));
	
	return ans;
}

Jällegi võib juhtuda, et väiksemate i ja j juures kutsutakse lcs(i, j) välja miljardeid kordi, kusjuures iga kord on vastus sama. Teeme sama, mis eelmine kord ja jätame välja arvutatud väärtused meelde. Kuna funktsioonil on seekord kaks parameetrit, siis tuleb väärtused meelde jätta kahemõõtmelisse tabelisse.

vector<int> A;
vector<int> B;

vector<vector<int>> memo;
vector<vector<int>> has_memo;

int lcs (int i, int j) {
	if (i == 0 || j == 0) {
		return 0;
	}

	if (has_memo[i][j]) {
		return memo[i][j];
	}

	int ans = 0;
	if (A[i - 1] == B[j - 1]) {
		ans = max(ans, 1 + lcs(i - 1, j - 1));
	}

	ans = max(ans, lcs(i - 1, j));
	ans = max(ans, lcs(i, j - 1));

	has_memo[i][j] = 1;
	memo[i][j] = ans;	
	return ans;
}

Nagu eelmises ülesandes, võib rekursiivsest funktsioonist loobuda ja lcs(i, j) väärtused lihtsalt järjest välja arvutada: valemid jäävad täpselt samaks.

vector<int> A;
vector<int> B;

vector<vector<int>> lcs (A.size(), vector<int> (B.size()));
for (int i = 0; i <= A.size(); i++) {
	for (int j = 0; j <= B.size(); j++) {
		if (i == 0 || j == 0) {
			lcs[i][j] = 0;
		} else {
			lcs[i][j] = 0;
			if (A[i - 1] == B[j - 1]) {
				lcs[i][j] = max(lcs[i][j], 1 + lcs[i - 1][j - 1]);
			}
			
			lcs[i][j] = max(lcs[i][j], lcs[i - 1][j]);
			lcs[i][j] = max(lcs[i][j], lcs[i][j - 1]);
		}
	}
}

1.3. Üldine meetod

Üldiselt tähendabki dünaamiline planeerimine ülesande lahendamist järgmise skeemi abil:

Mõtle välja rekursiivne funktsioon, mis ülesande lahendab. Veendu, et erinevate võimalike argumentide arv on piisavalt väike. Näiteks: \(f(k)\) on pikima sellise kasvava osajada pikkus, mis lõpeb \(k\)-nda elemendiga; \(g(i, j)\) on massiivide \(A[\colon i]\), \(B[\colon j]\) pikima ühise osajada pikkus.
Funktsiooni implementeerides kontrolli, kas antud argumentidel on juba funktsiooni välja kutsutud; kui on, siis tagasta kohe varem välja arvutatud väärtus.

Alternatiivselt võib dünaamilist planeerimist kasutada iteratiivselt:

Defineeri mingid olekud, mis vastavad ülesande mingi osa lahendamisele.
Tuleta valemid, millega saab arvutada vastuse mingi oleku jaoks, kasutades eelmiste olekute vastuseid.
Täida järjest tabel, kasutades tuletatud valemeid.

Raske osa on kummagi skeemi juures esimene samm. Õige funktsiooni või õigete olekute valimine nõuab kõige rohkem harjutamist. Lihtsamaid ülesandeid saab nende skeemide abil otse lahendada. Raskemates võib olla vaja täiendavat tööd, näiteks valemite arvutamise kiirendamine mõne andmestruktuuri abil.

Need kaks skeemi on üldiselt samaväärsed, aga kasulik on mõlemat meetodit kasutama harjuda. Rekursiivne meetod on paljudele intuitiivselt lihtsam, samuti mugavam graafiteoreetilistes ülesannetes (vt. puuülesandeid allpool). Mõnes ülesandes on aga lihtsam mõelda mitte sellest, kuidas olekute väärtus eelmiste põhjal arvutada, vaid sellest, kuidas olekud järgmisi mõjutavad. Sel juhul on parem kasutada iteratiivset meetodit.

1.4. Edit distance

Ülesanne. Antud string \(A\), mis on vaja teisendada stringiks \(B\). Selleks saab kasutada kolme tüüpi operatsioone:

kustutada stringist \(A\) üks täht (hind \(x\));
lisada stringi \(A\) üks täht (hind \(y\));
asendada stringi \(A\) üks täht teisega (hind \(z\)).

Mis on vähim koguhind, millega saab \(A\) teisendada \(B\)-ks? Kummagi stringi pikkus on ülimalt \(10^3\).

DP olekud: \(dp[i][j]\) on odavaim viis teisendada \(A\) esimesed \(i\) sümbolit \(B\) esimeseks \(j\) sümboliks.

Selleks, et teisendada \(A\) esimesed \(i\) sümbolit \(B\) esimeseks \(j\) sümboliks, võime:

kustutada stringist \(A\) \((i-1)\)-nda sümboli ja teisendada \(A\) esimesed \(i - 1\) sümbolit \(B\) esimeseks \(j\) sümboliks: \(x + dp[i - 1][j]\);
lisada \(A\) \(i\)-ndaks sümboliks \(B\) \((j-1)\)-nda sümboli ja teisendada \(A\) esimesed \(i\) sümbolit \(B\) esimeseks \(j-1\) sümboliks: \(y + dp[i][j - 1]\);
asendada \(A\) \((i-1)\)-s sümbol \(B\) \((j-1)\)-nda sümboliga ja teisendada \(A\) esimesed \(i-1\) sümbolit \(B\) esimeseks \(j-1\) sümboliks: \(z + dp[i - 1][j - 1]\); kui need sümbolid juba on võrdsed, siis \(dp[i - 1][j - 1]\).

vector<vector<int>> dp (1 + A.size(), vector<int> (1 + B.size()));

for (int i = 0; i <= A.size(); i++) {
	for (int j = 0; j <= B.size(); j++) {
		if (i == 0 && j == 0) {
			dp[i][j] = 0;
			continue;
		}

		dp[i][j] = INF;
		if (i != 0)
			dp[i][j] = min(dp[i][j], x + dp[i - 1][j]);
		if (j != 0)
			dp[i][j] = min(dp[i][j], y + dp[i][j - 1]);

		if (i != 0 && j != 0) {
			if (A[i - 1] == B[j - 1])
				dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
			else
				dp[i][j] = min(dp[i][j], z + dp[i - 1][j - 1]);
		}		
	}
}

vector<vector<int>> has_memo;
vector<vector<int>> memo;

int edit_dist (int i, int j) {
	if (i == 0 && j == 0)
		return 0;

	if (has_memo[i][j])
		return memo[i][j];

	int ans = INF;
	if (i != 0)
		ans = min(ans, x + edit_dist(i - 1, j));
	if (j != 0)
		ans = min(ans, y + edit_dist(i, j - 1));
	
	if (i != 0 && j != 0) {
		if (A[i - 1] == B[j - 1])
			ans = min(ans, edit_dist(i - 1, j - 1));
		else
			ans = min(ans, z + edit_dist(i - 1, j - 1));
	}

	has_memo[i][j] = 1;
	memo[i][j] = ans;
	return ans;
}

1.5. Knapsack

Ülesanne. Sul on \(n\) kivi, igal kivil on kaal \(w_i\) ja hind \(c_i\). Vali mingi hulk kive nii, et nende kogukaal ei ületaks \(W\) ja et nende hind oleks võimalikult suur. \(n, W \le 10^3\).

Seekord proovime dünaamilist planeerimist kasutada teistpidi: mõtleme, kuidas olekud mõjutavad järgmisi. Loome \((n + 1) \times (W + 1)\) tabeli dp. dp[i][j] on maksimaalne hind, mis on võimalik saavutada, valides mõned kivid esimese i seast nii, et nende koguhind on täpselt j.

Alguses on dp[i][j] väärtus iga i ja j korral \(-\infty\), välja arvatud dp[0][0], milleks on 0.

vector<int> weight, value; // mõlemad pikkusega n

// lõpmatuse asemel kasutame mingit hästi suurt arvu INF
vector<vector<int>> dp (n + 1, vector<int> (W + 1, -INF));
dp[0][0] = 0;

for (int i = 0; i < n; i++) {
	for (int j = 0; j <= W; j++) {
		// nüüdseks on dp[i][j] väärtus õige
		// uuendame selle põhjal järgmisi väärtusi

		// on võimalik, et kivi i me lahendusse ei võta:
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);

		// teine võimalus on, et võtame
		if (j + weight[i] <= W)
			dp[i + 1][j + weight[i]] = max(dp[i + 1][j + weight[i]], value[i] + dp[i][j]);
	}
}

Ülesanne on sellega lahendatud, aga siin on võimalik mälukasutust optimeerida: dp[i][j] mõjutab ainult väärtusi dp[i + 1][*]. Seega peame korraga meeles pidama ainult vektoreid dp[i] ja dp[i + 1].

vector<int> weight, value; // mõlemad pikkusega n
vector<int> dp (W + 1, -INF));
dp[0] = 0;

for (int i = 0; i < n; i++) {
	vector<int> next_dp (W + 1, -INF); // vana dp[i + 1]

	for (int j = 0; j <= W; j++) {
		// on võimalik, et kivi i me lahendusse ei võta:
		next_dp[j] = max(next_dp[j], dp[j]);

		// teine võimalus on, et võtame
		if (j + weight[i] <= W)
			next_dp[j + weight[i]] = max(next_dp[j + weight[i]], value[i] + dp[j]);
	}

	dp = next_dp;
}

Sama meetodit on võimalik kasutada ka teistes ülesannetes, kus DP tabeli iga rida sõltub ainult eelmisest. Selles ülesandes on tegelikult võimalik minna veelgi kaugemale: et dp[i][j] ei mõjuta väärtusi dp[i + 1][k], kus \(k < j\), siis piisab ainult ühe rea korraga meeles hoidmisest:

vector<int> weight, value; // mõlemad pikkusega n
vector<int> dp (W + 1, -INF));
dp[0] = 0;

for (int i = 0; i < n; i++) {
	for (int j = W - weight[i]; j >= 0; j--) {
		dp[j + weight[i]] = max(dp[j + weight[i]], value[i] + dp[j]);
	}
}

2. Veel ülesandeid

Ülesanne. Kuristiku vasakul pool on järjest \(n\) punkti; paremal pool järjest \(m\) punkti. Iga punkti iseloomustab tema väärtus ja tema värv.

Sul on võimalik lisada sildu kahe vastaspoolel oleva punkti vahele; sillad ei tohi üksteist ületada, samuti ei tohi ühest punktist alata mitu silda. Silla lisamise teenid sa skoori — otspunktide väärtuste summa.

Leia maksimaalne skoor ja minimaalne sildade arv, millega seda skoori on võimalik saavutada. \(n, m \le 1000\).

DP olekud

\(dp[i][j]\): maksimaalne võimalik skoor, kui sildu on lisatud ainult vasakul esimese \(i\) ja paremal esimese \(j\) punkti vahele.

Ülesanne. On \(n\) tüüpi kasti; iga tüüpi kaste on piiramatus koguses. Kaste iseloomustab tema kaal ja kandevõime. Kastidest tuleb ehitada torn nii, et ühegi kasti peal ei ole kokku suurem kaal, kui selle kasti kandevõime. Lisaks ei tohi suurema järjekorranumbriga kastitüübi kasti peal olla väikesema numbriga kastitüübi kaste. \(n \le 10^3\), kastide kaalud ja kandevõimed ülimalt \(10^4\).

DP olekud

\(dp[i][j]\): maksimaalse kõrgusega torn, mille kogukaal on \(j\) ja mis kasutab ainult kastitüüpe \(i, i + 1, \ldots, n - 1\).

DP väärtused tuleks arvutada kahanevas järjekorras ja optimeerida mälukasutust nagu knapsack ülesandes. Pane tähele, et iga tüüpi kaste on kasutada piiramatu arv!

Ülesanne. On \(n\) kingitust, igal kingitusel konkreetne väärtus. Kingitusi visatakse ette määratud järjekorras. Kingitusi püüavad lapsed kolmest lastekodust; iga lastekodu iseloomustab laste arv ning iga selle lastekodu lapse korvi pindala. Tõenäosus, et konkreetne laps kingituse kinni püüab, on võrdeline tema korvi pindalaga. Kui laps kingituse kinni püüab, läheb ta koju ja rohkem ei püüa.

Leia iga lastekodu kohta, mis on selle kodu laste püütud kingituste keskmine väärtus. Igas lastekodus on ülimalt \(100\) last.

DP olekud

\(dp[i][j][k]\) on kolmik: esimese, teise ja kolmanda lastekodu juba kinni püütud kingituste keskväärtused, kui alles on jäänud \(i\), \(j\) ja \(k\) vastavalt esimese, teise ja kolmanda lastekodu last.

Sõltuvalt täpsest implementatsioonist võib olla vaja meeles pidada ka tõenäosust, et antud olekusse üldse jõutakse.

Teisendused: leia \(i\), \(j\) ja \(k\) põhjal, millist kingitust viskama hakatakse ja arvuta tõenäosused, et kingi püüab vastava lastekodu laps.

3. DP puu peal

Ülesanne. Antud puu \(n\) tipuga. Iga tipp tuleb värvida siniseks, punaseks või roheliseks; mõned tipud on juba värvitud. Mitu võimalust on määrata ülejäänud tippudele värvid nii, et ükski tipp ei oleks ühegi oma naabriga sama värvi? Leia vastus mooduli \(10^9 + 7\) järgi. \(n \le 10^5\).

Valime puule mingi juure. Nüüd tähistagu \(dp[u][c]\) — mitu võimalust on värvida tipu \(u\) alampuu tipud nii, et tipu \(u\) enda värv on \(c\). Et arvutada \(dp[u][c]\) väärtus, arvutame esiteks rekursiivselt need väärtused kõikide tema laste jaoks. Seejärel saame iga lapse jaoks eradli valida sõltumatult ühe kahest värvist, mis ei ole \(c\).

// color[u]: -1, kui värvimata; 0, 1 või 2, kui juba värvitud
// children[u]: tipu u lapsed pärast juure valimist
// dp[u][c]: DP tabel

void calc (int u) {
	// arvutame rekursiivselt DP väärtused u laste jaoks
	for (int nxt : children[u]) {
		calc();
	}

	for (int c = 0; c < 3; c++) {
		if (color[u] != -1 && color[u] != c) {
			// on 0 võimalust tipp värvida värvi c, sest tipp on 
			// juba mingit teist värvi
			dp[u][c] = 0;
			continue;
		}

		dp[u][c] = 1;
		for (int nxt : children[u]) {
			Modint ways = 0;  // mitu viisi on valida tipu nxt alampuu värvid?
			// siin Modint on klass, millel tehted +, * jne ümber defineeritud nii,
			// et pärast iga tehet võetakse jääk

			for (int d = 0; d < 3; d++) {
				if (c == d)
					continue;
				ways += dp[nxt][d];
			}

			dp[u][c] *= ways;
		}		
	}
}

Ülesanne. Antud puu. Sa võid korrata kuitahes mitu korda järgmist operatsiooni:

Vali tipp, millel on paarisarv naabreid ja kustuta see.

Kas niimoodi on võimalik kustutada terve puu? \(n \le 10^5\)

DP olekud

Samaväärne ülesanne: suuna puu servad nii, et igast tipust oleks paarisarv väljuvaid. Siis:

\(dp[u][0]\): kas tipu \(u\) alampuus on suunamine võimalik, juhul kui serv tipu \(u\) ja tema vanema vahel on suunatud üles?
\(dp[u][1]\): kas tipu \(u\) alampuus on suunamine võimalik, juhul kui serv tipu \(u\) ja tema vanema vahel on suunatud alla?

3.1. Juure liigutamisega DP

Ülesanne. Antud puu. Lahenda iga \(r\) jaoks järgmine ülesanne:

Arvuta, mitu võimalust on värvida mõned servad mustaks nii, et igal teekonnal \(v \leadsto r\) on ülimalt üks must serv.

Leia vastused mooduli \(10^9 + 7\) järgi. \(n \le 2 \cdot 10^5\)

Esiteks mõtleme, kuidas lahendada ülesanne ainult ühe \(u\) jaoks: eeldame, et \(r = 1\). Seame puu juureks tipu \(r\). Paneme tähele, et kui tipu \(u\) alampuus on vähemalt üks värvitud serv, siis ükski serv teekonnal \(u \leadsto r\) ei tohi olla värvitud. Olgu \(dp[u]\) — mitu võimalust on värvida tipu \(u\) alampuus mõned (võibolla mitte ühtegi) serva nii, et ühelgi teekonnal \(v \leadsto u\) ei ole rohkem, kui üks must serv.

Kuidas arvutada \(dp[u]\), kui on teada tema laste DP väärtused? Iga lapse \(v\) jaoks on meil järgmised valikud:

värvime \(v\) alampuus mõned servad (\(dp[v]\) võimalust) ja serva \(uv\) ei värvi;
ei värvi \(v\) alampuus ühtki serva ja värvime serva \(uv\);

Kokku on iga lapse jaoks \((dp[v] + 1)\) võimalust. Need arvud korrutame kokku; viimaks lahutame 1 (mis vastab üldse mitte ühegi serva värvimisele).

Nii on ülesanne ühe konkreetse \(r\) väärtuse jaoks lahendatud. Kui aga sama lahendust iga \(r\) jaoks eraldi rakendada, oleks see liiga aeglane. Selle asemel paneme tähele, et kui liigutame puu juure tipust \(r\) tippu \(s\), siis muutuvad ainult \(dp[r]\) ja \(dp[s]\) väärtused. Seega piisab ainult \(dp[r]\) ja \(dp[s]\) ümber arvutada ja uus vastus on käes. Nüüd saame liigutada puu juurt nii, et kõik puu tipud käiakse läbi. Selleks on vaja vaid \(2n - 2\) liigutust.

Aga isegi \(dp[r]\) ja \(dp[s]\) nullist üle arvutamine on liiga aeglane (lisaülesanne: leia graaf, kus niisugune lahendus võtaks ca. \(n^2\) korrutamistehet). Selle asemel:

uuendame \(dp[r]\) väärtust, jagades selle (vana) \(dp[s] + 1\)-ga
uuendame \(dp[s]\) väärtust, korrutades selle (uue) \(dp[r] + 1\)-ga

See oleks muidu täislahendus, aga siin on üks konks juures. Täisarvudes opereerides on \(dp[s] + 1\) on alati positiivne täisarv ja jagamine alati võimalik. Ülesannet lahendades aga töötame täisarvudega mod \(10^9 + 7\), ja võib juhtuda, et \(dp[s] + 1\) on nüüd null ja jagamine seega võimatu.

Selle probleemi ära hoidmiseks hoiame iga \(u\) kohta meeles, mitu nulli on tegurite seas avaldises

\[ (dp[v_1] + 1) (dp[v_2] + 1) \cdots (dp[v_k] + 1). \]

Kui tegurite seas on kaks või enam nulli, siis on korrutis null ka pärast ühe teguri eemaldamist. Kui tegurite seas on täpselt üks null, siis peame meeles kõigi ülejäänud tegurite korrutist. Kui eemaldatav tegur on null, siis on uus korrutis see meelespeetav arv; vastasel korral null. Kui tegurite seas ei ole nulle, siis pole probleemi.