Matematická olympiáda – kategorie P
Řešení úloh ústředního kola (1. soutěžní den) 56. ročníku
P-III-1 Pizza vrací úder
Udělejme nejprve několik pozorování: Buď z nejmenší zisk, jehož Marco může dosáhnout. Zřejmě 0≤z < 2k, protože pokud by z bylo alespoň 2k, pak bychom mohli změnit libovolný příjem na výdaj, a tak snížit zisk o nanejvýš 2k.
Dále nás nezajímá pořadí zadaných čísel – výsledek záleží pouze na tom, kolikrát se které číslo z rozmezí 1 až k vyskytuje. Označme si ni počet výskytů čísla i. Úlohu si tedy můžeme přeformulovat tak, že hledáme k čísel xi (0≤xi≤ni) tak, že pokud xi výskytů čísla i prohlásíme za příjem a ni-xi za výdaj, zisk z=∑i=1k (2xi-ni)·i bude nezáporný a nejmenší možný. Označme (2xt-nt)·t jako yt. Výraz yt může nabýt libovolné z hodnot -t nt, -t (nt-2),..., t nt.
Nyní ukážeme, že stačí umět vyřešit úlohu v případě, že všechna čísla ni mají velikost nanejvýš 2k+1: Nechť z=∑i=1k yi je minimální zisk. Pokud nt>2k+1 pro nějaké t, snížíme hodnotu nt o 2 a tvrdíme, že optimální hodnota z pro novou úlohu je stejná jako pro původní úlohu. Stačí tedy dokázat, že původní hodnotu z lze vyjádřit s xt<nt-2. Tuto operaci můžeme samozřejmě opakovat, dokud existuje t, pro které je nt>2k+1 (v programu to realizujeme tak, že pokud nt>2k+1, rovnou ho nahradíme buď 2k nebo 2k+1 podle toho, zda je nt sudé či liché).
Podívejme se nyní na vyjádření optimálního zisku z=∑i=1k yi. Pokud platí |yt|< t nt, zisk z lze vyjádřit i po snížení nt. Zbývá vyřešit případ, že |yt|=t nt ≥t(2k+2). Předpokládejme, že yt je kladné, situace, kdy yt je záporné, se vyřeší analogicky. Jelikož ∑i=1k yi < 2k, musí existovat (nikoliv nutně navzájem různá) čísla i1, i2, ..., it (1≤ij≤k) tak, že můžeme postupně zvyšovat yi1 o 2i1, yi2 o 2i2, ..., a takto získané hodnoty budou nekladné.
Uvažme posloupnost součtů 0, i1, i1+i2, ..., i1+i2+...+ it. Mezi těmito t+1 součty musí být dva, které dávají stejný zbytek po dělení t, řekněme i1+...+ip a i1+...+iq (p < q), tedy součet x = ip+1+...+ iq≤kt je dělitelný t. Nicméně pak můžeme zmenšit yt o 2x a zvětšit yi o 2i pro všechna i=ip+1, ..., iq. Tím se nezmění zisk, ale |yt|≤t(nt-2). Proto lze snížit nt o 2.
S právě nalezeným pozorováním o omezení na velikost nt je snadné vytvořit algoritmus založený na dynamickém programování. Pro t od 1 do k si budeme postupně počítat, jakých zisků (či ztrát) lze dosáhnout pouze použitím hodnot y1, y2, ..., yt – množinu všech těchto zisků si označme Zt. Zjevně Z0={0} a Zt vytvoříme ze Zt-1 tak, že vezmeme všechna čísla, která jdou vyjádřit jako x+y, kde x∈Zt-1 a y je jedna z možných hodnot pro yt. Protože množina Zt obsahuje čísla s absolutní hodnotou nejvýše (2k+1)t2, velikost každé z množin Zt je nanejvýš O(k3). Hledaný zisk z je pak roven nejmenšímu nezápornému číslu, které je obsažené v množině Zk.
Jelikož možných hodnot pro každé yt je O(k), jednu množinu Zt lze snadno zkonstruovat v čase O(k4). Existuje ale chytřejší algoritmus: číslo z patří do Zt, pokud alespoň jedno z čísel z-t nt, z - t (nt-2),..., z + t nt patří do množiny Zt-1. My si dokonce pro každé z spočítáme, kolik z těchto čísel patří do Zt-1, označme si tento pročet mz. Pro prvních 2t hodnot z si mz určíme prostým vyzkoušením všech prvků, což zvládneme v čase O(k2). Pro každé další z nahlédneme, že mz je rovno mz-2t zvýšené o jedna, jestliže z + t nt ∈Zt-1, a snížené o jedna, jestliže z - t (nt+2) ∈Zt-1. Každé další číslo mz tedy určíme v konstantním čase. Díky omezení na velikost množiny Zt je časová složitost určení všech hodnot mz nanejvýš O(k3).
Čísla ni lze určit v lineárním čase, celková časová složitost algoritmu tedy je O(n + k4). Při konstrukci množiny Zt si stačí pamatovat pouze množinu Zt-1, paměťová složitost proto je O(k3) (zadaná čísla si nemusíme pamatovat, čísla ni si můžeme určit již při načítání).
Popsaný algoritmus lze ještě vylepšit, pokud nahlédneme, že stačí uvažovat množiny Zt obsahující čísla velikosti pouze O(k2) (tím se časová složitost sníží na O(n + k3) a paměťová na O(k2)). Toto tvrzení dokážeme podobně jako odhad na velikost čísel nt. Nechť z=∑i=1k yi je minimální zisk, a označme zt=∑i=1t yi. Hodnota zt je číslo, které se pro toto řešení bude vyskytovat v množině Zt. Dokažme, že lze předpokládat, že |zt|≤2k(k+2) pro každé t.
Nechť tomu tak není a |zt|> 2k(k+2) pro nějaké t. Zabývejme se případem, kdy zt je kladné, případ, kdy je záporné, se vyřeší analogicky. Pak musí existovat posloupnost čísel c1, c2, ..., cx (1≤cj≤t) taková, že ∑j=0x 2cj = S ≥2k(k+1) a můžeme postupně snižovat yc1 o 2c1, yc2 o 2c2, ..., a takto získané hodnoty budou nezáporné, a posloupnost čísel d1, d2, ..., dy (t< dj≤k) tak, že 0≤S - ∑j=0y 2dj<2k a můžeme postupně zvyšovat yd1 o 2d1, yd2 o 2d2, ..., a takto získané hodnoty budou nekladné. Všimněte si, že x≥k a y≥k. Čísla ci a -di přeuspořádejme do posloupnosti e1, e2, ..., ex+y takové, že 0≤∑i=1m ei < 2k pro každé m=0,1, ..., x+y. Podobně jako v odhadu velikosti nt nahlédneme, že existují indexy m1<m2 takové, že ∑i=m1m2 ei je dělitelné 2k. Protože |∑i=m1m2 ei|<2k, tento součet je roven 0. Nyní provedeme snížení a zvýšení hodnot yj tak, jak je to naznačeno prvky em1 em1+1, ..., em2, čímž se jejich absolutní hodnoty zmenší, ale součet se nezmění. Tuto operaci provádíme, dokud existuje t takové, že |zt|> 2k(k+2). Jelikož vždy zmenšíme absolutní hodnoty některých yj, po konečném počtu opakování skončíme s řešením, v němž platí |zt|≤2k(k+2) pro všechna t.
Program následuje:
const MAXK = 100; { maximální velikost příjmu či výdaje }
MAXZ = 2 * MAXK * (MAXK + 2); { maximální velikost prvku Z_t }
type mnozina = record
prvky : array[-MAXZ .. MAXZ] of boolean; { true je nastaveno na pozicích všech prvku množiny }
end;
var m : array[1 .. 2] of mnozina; { množiny Z_t a Z_(t+1) }
predchozi : integer; { Z_t je m[predchozi], Z_(t+1) je m[3-predchozi] }
k : integer;
amaxz : integer; { 2k(k+2) }
ni : array[1 .. MAXK] of integer; { čisla n_i }
mz : array[-MAXZ .. MAXZ] of integer; { čísla m_z ... }
{ ve skutečnosti by stačilo si pamatovat jen posledních 2t }
{ Inicializuje MN na prázdnou množinu }
procedure smaz (var mn : mnozina);
var i : integer;
begin
for i := -amaxz to amaxz do
mn.prvky[i] := false;
end;
{ Vrátí true pokud X je prvkem množiny MN }
function je_prvek (var mn : mnozina; x : integer) : boolean;
begin
je_prvek := (abs (x) <= amaxz) and mn.prvky[x];
end;
{ Z množiny Z_(T-1) (P) vytvoří množinu Z_T (MN) }
procedure dalsi_zisky (var p, mn : mnozina; t : integer);
var yt, i, z, max_yt : integer;
begin
max_yt := t * ni[t];
{ spočteme čísla m_z pro z v rozmezí -amaxz ... -amaxz + 2t-1 }
for z := -amaxz to -amaxz + 2 * t - 1 do
begin
i := 0;
yt := -max_yt;
while yt <= max_yt do
begin
if je_prvek (p, z + yt) then
inc (i);
inc (yt, 2 * t);
end;
mz[z] := i;
end;
{ a nyní zbývající hodnoty m_z }
for z := -amaxz + 2 * t to amaxz do
begin
i := mz[z - 2 * t];
if je_prvek (p, z + max_yt) then
inc (i);
if je_prvek (p, z - 2 * t - max_yt) then
dec (i);
mz[z] := i;
end;
{ do množiny mn dáme čísla z taková, že m_z není nula }
for z := -amaxz to amaxz do
if mz[z] <> 0 then
mn.prvky[z] := true;
end;
{ Vrátí nejmenší nezáporné číslo v množině MN }
function minimum (var mn : mnozina) : integer;
var i : integer;
begin
for i := 0 to amaxz do
if mn.prvky[i] then
begin
minimum := i;
break;
end;
end;
{ Načte seznam příjmů či výdajů }
procedure nacti;
var i, n, a : integer;
begin
readln (n, k);
amaxz := 2 * k * (k + 2);
for i := 1 to k do
ni[i] := 0;
for i := 1 to n do
begin
read (a);
inc (ni[a]);
end;
end;
{ Omezí čísla n_i na nanejvýš 2k+1 }
procedure omez_ni;
var i : integer;
begin
for i := 1 to k do
if ni[i] > 2 * k + 1 then
begin
if odd(ni[i]) then
ni[i] := 2 * k + 1
else
ni[i] := 2 * k;
end;
end;
var t : integer;
begin
nacti;
omez_ni;
smaz (m[1]);
smaz (m[2]);
predchozi := 1;
{ Z_0 = (0) }
m[predchozi].prvky[0] := true;
for t := 1 to k do
begin
dalsi_zisky (m[predchozi], m[3 - predchozi], t);
smaz (m[predchozi]);
predchozi := 3 - predchozi;
end;
writeln (minimum (m[predchozi]));
end.
P-III-2 Obdélník
Předvedeme si řešení, jehož časová složitost je O(N2) a jehož paměťové nároky jsou lineární v počtu daných bodů.
Nejprve vymyslíme, jak pro daný obdélník A1A2A3A4 rychle určit počet bodů, které leží uvnitř tohoto obdélníku. Pro každý bod Bi spočítáme počet bodů Bi', jejichž x-ová souřadnice je větší nebo rovna x-ové souřadnici bodu Bi a zároveň y-ová souřadnice je ostře menší než y-ová souřadnice bodu Bi. Tento počet označíme ai1. Podobně, ai2 bude počet bodů s x-ovou souřadnicí ostře větší a y-ovou souřadnicí větší nebo rovnou, ai3 počet bodů s x-ovou souřadnicí menší nebo rovnou a y-ovou ostře větší a konečně ai4 bude počet bodů s x-ovou ostře menší a y-ovou menší nebo rovnou. Každé z čísel ai1, ai2, ai3 a ai4 je snadné spočítat v čase O(N) (pro jeden bod Bi). Tedy na spočítání všech 4N čísel ai1, ai2, ai3 a ai4, 1≤i≤n, spotřebujeme čas O(N2).
Je snadné nahlédnout, že pokud vrchol Aj obdélníku A1A2A3A4 je bod Bij, pak počet bodů ležících uvnitř obdélníku A1A2A3A4 je N-ai11-ai22-ai33-ai44 (viz obrázek). Pro jeden obdélník A1A2A3A4 můžeme tedy určit počet bodů, které leží uvnitř tohoto obdélníku, v konstantním čase.
Nyní si popíšeme, jak můžeme rychle najít všechny obdélníky A1A2A3A4, jejichž hrany jsou rovnoběžné s osami a jejichž vrcholy jsou v některých ze zadaných bodů. Nejprve si všechny body setřiďme vzestupně podle x-ové souřadnice a ty body, které mají shodnou x-ovou souřadnici, setřídíme mezi sebou vzestupně podle y-ové souřadnice. Pro každý bod Bi tedy nyní můžeme vypsat ty body, které mají stejnou x-ovou souřadnici jako Bi a větší y-ovou souřadnici, v čase lineárním v jejich počtu. Podobně si setřídíme všechny body podle y-ové souřadnice a v případě shody podle x-ové, abychom mohli snadno nalézt body se stejnou y-ovou a větší x-ovou souřadnicí. Na setřídění bodů potřebujeme čas O(NlogN) (použijeme např. třídící algoritmus heapsort nebo quicksort) a pro uložení setříděného seznamu bodů včetně odkazů do něj pak potřebujeme paměť lineární v N.
Popíšeme si nyní postup, jak nalézt všechny obdélníky A1A2A3A4, které splňují podmínky ze zadání úlohy. Zafixujeme jeden bod Bi a určíme všechny body Bj takové, že bod Bi je vrchol A1 a bod Bj vrchol A3 nějakého obdélníku A1A2A3A4 (všimněte si, že vrcholy A2 a A4 jsou body Bi a Bj jednoznačně určeny).
K nalezení všech takových bodů Bj pro bod Bi si vytvoříme pomocné pole C, jehož všechny složky C[j] budou na počátku rovny nule. Uvážíme pak všechny body Bi', jež mají stejnou x-ovou souřadnici jako Bi a zároveň větší y-ovou souřadnici, a pro každý takový bod Bi' uvážíme všechny body Bi'', které mají stejnou y-ovou a větší x-ovou souřadnici než Bi'. Body Bi' zvládneme najít v čase lineárním v jejich počtu a podobně body Bi'' pro každý bod Bi' lze najít v čase lineárním v jejich počtu. Protože body Bi'' jsou různé pro různé body Bi', trvá nalezení všech bodů Bi'' čas lineární v N. Složku C[i''] pole C zvýšíme o jedna pro každý bod Bi'', který jsme takto nalezli. Zdůrazněme, že je nyní každá složka pole C rovna buď 0 nebo 1.
Poté pro bod Bi uvážíme všechny body Bi' se stejnou y-ovou a větší x-ovou souřadnicí a pro takové body Bi' najdeme všechny body Bi'' stejnou x-ovou souřadnicí a větší y-ovou souřadnicí. Za každý takový bod zvýšíme složku C[i''] pole C o jedna. Složky pole C jsou nyní rovny 0, 1 nebo 2. Dále platí, že C[j] je rovno 2 tehdy a jen tehdy, jestliže pro body Bi a Bj existuje bod, který má stejnou x-ovou souřadnici jako Bi a stejnou y-ovou souřadnici jako Bj, a zároveň existuje bod, který má stejnou x-ovou souřadnici jako Bj a stejnou y-ovou souřadnici jako Bi. Potom ale takové dva body tvoří vrcholy A2 a A4 obdélníku, jehož vrchol A1 je Bi a vrchol A3 je Bj. Pro daný bod Bi můžeme tedy v čase O(N) nalézt všechny body Bj, které tvoří protilehlé vrcholy A1 a A3 nějakého obdélníku A1A2A3A4. Určit počet vnitřních bodů takovéhoto obdélníku lze pak v konstantním čase, jak jsme si vysvětlili na začátku řešení.
Jak jsme si právě popsali, lze pro daný bod Bi v čase O(N) spočítat počet vnitřních bodů obdélníků A1A2A3A4, jejichž bod A1 je bod Bi. Takovéto obdélníky spočítáme pro všechny body Bi a vybereme z nich ten, který obsahuje nejvíce vnitřních bodů. Vzhledem k tomu, že bod Bi lze zvolit N způsoby, je časová složitost právě popsaného algoritmu O(N2). Paměťová složitost je pak lineární v N.
program obdelniky;
const MAXN=1000; { maximální počet zadaných bodů; pro jednoduchost používáme statická pole}
var N: word;
Bx: array[1..MAXN] of integer;
By: array[1..MAXN] of integer;
sorted_by_x: array[1..MAXN] of word;
sorted_by_y: array[1..MAXN] of word;
index_by_x: array[1..MAXN] of word;
index_by_y: array[1..MAXN] of word;
A1, A2, A3, A4: array[1..MAXN] of word;
C: array[1..MAXN] of byte;
nejlepsi_pocet: word;
nejlepsi: array[1..4] of integer;
procedure nacti;
var i: word;
begin
readln(N);
for i:=1 to N do readln(Bx[i],By[i]);
end;
procedure spocitej_A;
var i,j: word;
begin
for i:=1 to N do
begin
A1[i]:=0; A2[i]:=0; A3[i]:=0; A4[i]:=0;
for j:=1 to N do
begin
if (Bx[j]>=Bx[i]) and (By[j]<By[i]) then inc(A1[i]);
if (Bx[j]>Bx[i]) and (By[j]>=By[i]) then inc(A2[i]);
if (Bx[j]<=Bx[i]) and (By[j]>By[i]) then inc(A3[i]);
if (Bx[j]<Bx[i]) and (By[j]<=By[i]) then inc(A4[i]);
end;
end;
end;
procedure quick_x(L,P: word);
var i,j,k:word;
x,y:integer;
begin
i:=L; j:=P;
x:=Bx[sorted_by_x[(L+P) div 2]];
y:=By[sorted_by_x[(L+P) div 2]];
while i<j do
begin
while (Bx[sorted_by_x[i]]<x) or
((Bx[sorted_by_x[i]]=x) and (By[sorted_by_x[i]]<y)) do
inc(i);
while (Bx[sorted_by_x[j]]>x) or
((Bx[sorted_by_x[j]]=x) and (By[sorted_by_x[j]]>y)) do
dec(j);
if i>j then break;
k:=sorted_by_x[i]; sorted_by_x[i]:=sorted_by_x[j]; sorted_by_x[j]:=k;
inc(i); dec(j);
end;
if L<j then quick_x(L,j);
if i<P then quick_x(i,P);
end;
procedure quick_y(L,P: word);
var i,j,k:word;
x,y:integer;
begin
i:=L; j:=P;
x:=Bx[sorted_by_y[(L+P) div 2]];
y:=By[sorted_by_y[(L+P) div 2]];
while i<j do
begin
while (By[sorted_by_y[i]]<y) or
((By[sorted_by_y[i]]=y) and (Bx[sorted_by_y[i]]<x)) do
inc(i);
while (By[sorted_by_y[j]]>y) or
((By[sorted_by_y[j]]=y) and (Bx[sorted_by_y[j]]>x)) do
dec(j);
if i>j then break;
k:=sorted_by_y[i]; sorted_by_y[i]:=sorted_by_y[j]; sorted_by_y[j]:=k;
inc(i); dec(j);
end;
if L<j then quick_y(L,j);
if i<P then quick_y(i,P);
end;
procedure setrid;
var i:word;
begin
for i:=1 to N do sorted_by_x[i]:=i;
quick_x(1,N);
for i:=1 to N do index_by_x[sorted_by_x[i]]:=i;
for i:=1 to N do sorted_by_y[i]:=i;
quick_y(1,N);
for i:=1 to N do index_by_y[sorted_by_y[i]]:=i;
end;
procedure zkus_vrchol(i: word);
var i1, i2, j: word;
a2_index, a4_index: array[1..MAXN] of word;
begin
for j:=1 to N do C[j]:=0;
i1:=index_by_x[i]+1;
while Bx[sorted_by_x[i1]]=Bx[i] do
begin
i2:=index_by_y[sorted_by_x[i1]]+1;
while By[sorted_by_y[i2]]=By[sorted_by_x[i1]] do
begin
inc(C[sorted_by_y[i2]]);
inc(i2);
a2_index[i2]:=sorted_by_x[i1];
end;
inc(i1)
end;
i1:=index_by_y[i]+1;
while By[sorted_by_y[i1]]=By[i] do
begin
i2:=index_by_x[sorted_by_y[i1]]+1;
while Bx[sorted_by_x[i2]]=Bx[sorted_by_y[i1]] do
begin
inc(C[sorted_by_x[i2]]);
inc(i2);
a4_index[i2]:=sorted_by_y[i1];
end;
inc(i1)
end;
for j:=1 to N do
if (C[j]=2) and (N-A1[i]-A2[a2_index[j]]-A3[j]-A4[a4_index[j]]>nejlepsi_pocet) then
begin
nejlepsi_pocet:=N-A1[i]-A2[a2_index[j]]-A3[j]-A4[a4_index[j]];
nejlepsi[1]:=Bx[i];
nejlepsi[2]:=Bx[j];
nejlepsi[3]:=By[i];
nejlepsi[4]:=By[j];
end;
end;
var i: word;
begin
nacti;
spocitej_A;
setrid;
nejlepsi_pocet:=0;
for i:=1 to N do zkus_vrchol(i);
if nejlepsi_pocet=0 then
writeln('Neexistuje žádný obdélník.')
else
writeln('Obdélník s vrcholy o souřadnicích [', nejlepsi[1], ',', nejlepsi[3],
'], [', nejlepsi[2], ',', nejlepsi[3], '], [', nejlepsi[2], ',', nejlepsi[4],
'] a [', nejlepsi[1], ',', nejlepsi[4], '] obsahuje ', nejlepsi_pocet,
' vnitřních vrcholů a je to obdélník s nejvíce vnitřními vrcholy.');
end.
P-III-3 Grafomat a šamani
Nejprve si rozmyslíme, že stačí umět úlohu vyřešit pro stromy (souvislé grafy bez cyklů). Když totiž dostaneme obecný 3-graf, můžeme ho z označeného vrcholu prohledat do šířky a stejně jako v úloze domácího kola si u každého vrcholu zapamatovat, po které hraně jsme do něj přišli. Všimněte si, že tyto hrany tvoří strom s jedním význačným vrcholem, totiž počátečním vrcholem, kterému budeme říkat kořen. Navíc tento strom obsahuje všechny vrcholy grafu G, takže je to jeho kostra.
Důkaz: Máme ukázat, že graf H tvořený vrcholy grafu G a vybranými hranami je kostrou G. Sledujme běh algoritmu a označme si Hi tu část grafu H, kterou jsme sestrojili během prvních i kroků prohledávání do šířky. V Hi budou tedy právě ty vrcholy, jejichž vzdálenost od kořene je nejvýše i, a hrany, po nichž do těchto vrcholů prohledávání došlo. Graf H0 obsahuje pouze kořen a až se po k krocích algoritmus zastaví, bude Hk=H. Dokážeme indukcí, že žádný graf Hi, a tedy ani H, neobsahuje cyklus. Pro H0 je to určitě pravda, pokud přecházíme od Hi k Hi+1, nemůže žádný nový cyklus vzniknout, jelikož právě přidávané vrcholy ve vzdálenosti i+1 připojujeme každý jedinou hranou k nějakému vrcholu z Hi. Zbývá si všimnout, že jelikož G je souvislý, musí každý vrchol grafu G ležet v nějakém Hi, takže i v H.
Chceme tedy rozdělit na poloviny vrcholy zakořeněného stromu, čili obarvit je dvěma barvami tak, aby každou barvu dostala právě polovina vrcholů. Kdybychom nebyli omezeni možnostmi grafomatu, mohli bychom například strom procházet rekurzivně, vždy si pamatovat, jakou barvu jsme naposledy použili, a následující vrchol obarvit barvou opačnou:
function <projdi_strom>(v:vrchol; b:barva): barva; begin b := 1-b; v.barva := b; Pro všechny syny w vrcholu v: b := <projdi_strom>(w, b); end;
Taková funkce projde postupně všechny vrcholy a barvy pravidelně střídá, takže pokud byl počet vrcholů sudý, nutně musí obě barvy použít stejně často.
Na grafomatu můžeme udělat totéž, jen místo rekurze, kterou nemáme k dispozici, použijeme předávání značek. Značka vždy ponese informaci o naposledy použité barvě b a bude jednoho z těchto dvou typů: vstupní (říká, že jsme vrchol právě navštívili poprvé) nebo výstupní (ta signalizuje, že vrchol opouštíme a už se do něj nevrátíme; to odpovídá návratu z funkce <projdi_strom>). Značky budeme předávat tak, aby v každém taktu výpočtu byl označený právě jeden vrchol. Naší procházecí funkci pak budou odpovídat tato pravidla:
- Na počátku výpočtu obsahuje kořen vstupní značku s barvou 0.
- Pokud vrchol v obdrží vstupní značku, změní barvu v ní uvedenou na opačnou a obarví se podle ní. Poté:
- Pokud má nějaké syny, předá značku prvnímu z nich.
- Pokud žádné nemá, značku změní na výstupní a ponechá si ji.
- Pokud vrchol v obdrží výstupní značku:
- Pokud má mladšího bratra (to je vrchol, který má stejného otce a následuje v pořadí synů po v), předá mu vstupní značku se stejnou barvou.
- Pokud žádného nemá, předá svou značku svému otci.
- Pokud otec neexistuje (tj. výstupní značka doputovala do kořene), skončíme.
My si ovšem ukážeme o něco efektivnější řešení, které bude lineární vzhledem k hloubce stromu, tedy k délce nejdelší cesty z kořene do listu. Bude založené na tom, že strom budeme obarvovat shora dolů po hladinách (vždy všechny vrcholy se stejnou vzdáleností od kořene najednou). Barvy ale závisí i na vrcholech v nižších hladinách, takže si nejdříve předpočítáme, který podstrom má sudou velikost a který lichou (podle toho budeme podstromům říkat sudé a liché). Algoritmus bude vypadat následovně:
- Prohledáváme graf z počátečního vrcholu do šířky, čímž vznikne strom.
- Od listů ke kořeni budeme šířit informace o tom, který podstrom je sudý a který lichý. Listy ihned pošlou, že jsou liché. Ostatní vrcholy počkají, až se rozhodnou jejich synové, a podle toho se pak rozhodnou samy.
- Až se rozhodne i kořen (ten bude určitě sudý), začneme po hladinách obarvovat. Nejprve obarvíme kořen barvou 0.
- Jakmile obarvíme libovolný vrchol v, rozhodneme se, jak obarvit jeho syny. Prvního syna obarvíme opačně než v. Každého dalšího pak buďto stejně jako předchozího nebo opačně podle toho, zda je předchozí podstrom sudý nebo lichý.
var x: 0..1; { 1=počáteční vrchol, 0=ostatní }
y: 0..2 = 2; { výstupní barva: 0=červená, 1=zelená, 2=neurčena }
z: 0..4 = 0; { hrana vedoucí k otci vrcholu, 0=neurčena, 4=kořen }
q: 0..2 = 2; { parita podstromu: 0=sudá, 1=lichá, 2=neurčena }
i, k, l: 0..3 = 0; { pomocné proměnné }
begin
{ 1. fáze: prohledávání do šířky (stavění stromu) }
if z=0 then
begin
{ Kořen označíme speciálně }
if x=1 then z := 4
{ Pokud vrchol ještě nemá otce, vybere si za otce souseda,
který už otce má, nebo který je počáteční }
else for i:=1 to 3 do
if (S[i].z > 0) or (S[i].x = 1) then
z := i;
end
{ 2. fáze: počítání parity }
else if q=2 then
begin
l := 0; { kolik synů má lichou paritu }
k := 0; { už můžeme paritu určit? }
for i:=1 to 3 do
if S[i].z = 0 then { neprohledaný soused => určit nemůžeme }
k := 1
else if S[i].z = P[i] then { je to syn }
if S[i].q = 2 then k := 1 { syn nemá paritu => ani my }
else if S[i].q = 1 then l := l+1; { lichý syn }
if k = 0 then
q := 1 - l mod 2; { toto funguje i pro listy, ty mají 0 synů }
end
{ 3. fáze: barvení }
else if y=2 then
begin
if (x=1) and (q<2) then y := 0 { jakmile dopočítáme paritu, kořen obarvíme červeně }
else if (z>0) and (S[z].y < 2) then { otec už je obarven => }
begin { => dopočítáme svou barvu podle parity bratrů }
y := 1 - S[z].y;
k := P[z]; { číslo hrany vedoucí z otce sem }
for i := 1 to k-1 do
if S[z].S[i].q = 1 then { za každého lichého staršího bratra barvu otočíme }
y := 1 - y;
end;
end
{ Pokud už je vrchol obarven, zastavíme se }
else stop;
end.