Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (2. soutěžní den) 49. ročníku

P-III-4 Pramen

Smerovník pri prameni číslo i nech ukazuje na prameň číslo s[i], pre 1<=i<=N. Hovoríme, že pramene p1,p2,..., pk tvoria cyklus, ak od prameňa p1 ukazuje smerovník k prameňu p2, od p2 k p3 a tak ďalej, až od prameňa pk k prameňu p1.

Ak vyštartujeme z ľubovoľného prameňa p1 a sledujúc smerovníky prechádzame postupne pramene p2, p3,..., po najviac N krokoch sa nám stane, že prídeme k prameňu pk+1, pri ktorom sme už boli, t.j. pk+1=pj pre nejaké j<=k. Keďže smerovník ukazujúci na prameň j bol vyrobený iba jeden, musí byť buď pk=pj-1, alebo j=1. Ak je k najmenšie také, že pk+1=pj, j<=k, potom j=1 a teda pramene p1,...,pk tvoria cyklus. Takýmto spôsobom vieme pre každý prameň určiť cyklus, do ktorého patrí.

Vzorový program využíva fakt, že ak vymeníme smerovníky pri dvoch prameňoch, ktoré patria do rovnakého cyklu, tento cyklus sa nám rozdelí na dva, t.j. počet cyklov sa zvýši o 1. Ak naopak vymeníme smerovníky pri prameňoch z rôznych cyklov, tieto dva cykly sa spoja do jedného.

Označíme si pramene, ktoré patria do toho istého cyklu ako prameň 1. Postupne budeme hľadať ďalšie cykly, ktoré budeme pripájať k cyklu obsahujúcemu prameň 1. Vždy, keď nájdeme nový cyklus, označíme si všetky pramene, ktoré doňho patria a zároveň spravíme výmenu smerovníkov, ktorou sa tento cyklus pripojí k cyklu obsahujúcemu prvý prameň. Všimnime si, že novovzniknutý cyklus obsahuje práve doposiaľ označené pramene. Ďalší cyklus potom hľadáme medzi neoznačenými prameňmi.

Implementácia

Na označovanie prameňov používame pole s. Prameň j považujeme za označený, ak s[j]<=q 0. Nový cyklus začíname hľadať od takého neoznačeného prameňa i, že všetky pramene s číslom menším ako i sú označené. Prameň i ako reprezentanta nového cyklu označíme s[i]=-1, ostatné pramene cyklu označíme nulou. Keď pri prechádzaní cyklom opäť natrafíme na prameň i, cyklus sme uzatvorili. Rovnakým postupom hľadáme ďalší cyklus, pričom vieme, že každý prameň na tomto cykle má číslo väčšie ako i.

Na záver vymeníme jeden smerovník z každého cyklu so smerovníkom pri niektorom prameni z cyklu obsahujúceho prameň 1, t.j. postupne vymieňame smerovník pri prameni 1 so smerovníkmi pri prameňoch označených -1 (reprezentanti cyklov). Potrebný počet výmen je o jednotku menší ako počet cyklov.

Časová a pamäťová zložitosť

Pamäťová zložitosť je zrejme O(N). Časová zložitosť algoritmu je tiež O(N), pretože s každým prvkom poľa s pracujeme maximálne trikrát (dvakrát pri hľadaní cyklov a na záver robíme ešte jeden prechod poľom s)

program Pramene; {P_49_III_4} const MAX = 30000; meno = 'pramen'; var s : array[1..MAX] of integer; N, i,j,jj,poc : integer; f,g : text; Begin Assign(f,meno+'.in'); ReSet(f); Assign(g,meno+'.out'); ReWrite(g); Read(f,N); for i:=1 to N do Read(f,s[i]); poc:=0; i:=1; for i:=1 to N do begin if s[i]<=0 then continue; j:=i; repeat jj:=s[j]; s[j]:=0; j:=jj; until j=i; s[i]:=-1; Inc(poc); end; WriteLn(g,poc-1); for i:=2 to N do if s[i]=-1 then WriteLn(g,'1 ',i); Close(g); Close(f); End.

P-III-5 Kina

Úlohu zo zadania si trochu zjednodušme a venujme sa len podstate úlohy. Je jasné, že ak sa z akéhokoľvek dôvodu budeme presúvať medzi dvoma mestami, tak optimálne bude, ak sa medzi nimi budeme presúvať najkratšou možnou cestou. Nech teda hi,j (1<=q i,j<=q N) označuje dĺžku najkratšej cesty medzi mestom i a mestom j. Riešenie podúlohy, ako zistiť dĺžky najkratších ciest je uvedené o pár odstavcov nižšie.

Takto zredukovanú úlohu budeme riešiť metódou dynamického programovania. Označme Ei,j (1<=q i<=q N, 0<=q j<=q K) dĺžku najkratšej trasy končiacej v deň j v meste i, takej, že sme videli filmy p1, p2,..., pj a pritom sme posledný film pj videli v meste i. Ak hodnota Ei,j neexistuje (t.j. neexistuje trasa popísaných vlastností), položíme Ei,j rovno nekonečnu.

Hodnoty Ei,j budeme postupne počítať z iných skôr vypočítaných hodnôt Ei,j a z hodnôt hi,j. Začneme zrejme takto: E1,0 = 0 a Ei,0 je nekonečno (2<=i<=N).

Počítajme hodnotu Ei,j pre 1<=j<=N. Máme dve možnosti: V meste i nehrajú film pj. Trasa požadovaných vlastností končiaca v meste i neexistuje, preto Ei,j je nekonečno.

Druhá možnosť je, že film pj v meste i hrajú. Rozoberme túto možnosť. Na to, aby sme videli filmy p1,p2,..., pj sme museli vidieť filmy p1,p2,..., pj-1. Film pj-1 sme mohli vidieť v nejakom meste s. Do mesta s sme sa pritom zrejme dostali najkratšou trasou, končiacou v tomto meste. Dĺžka tejto trasy je Es,j-1. Z mesta s do mesta i sme takisto museli ísť najkratšou cestou. Teda dĺžka takejto trasy bude Es,j-1 + hs,i. Prostým vyskúšaním všetkých možných miest s dostaneme dĺžku najkrašej cesty Ei,j.
Ei,j = min { Es,j-1 + hs,i | 1<=q s<=q N }
Najkratšia trasa, potrebná na zhliadnute všetkých K filmov končí v nejakom meste i. Stačí nám teda vybrať z dĺžok trás, ktoré končia v jednotlivých mestách tú najmenšiu. Pre dĺžku optimálnej trasy E teda platí
E := min { Ei,K | 1<=q i<=q N }
Ostáva nám ešte zistiť, cez ktoré mestá vlastne optimálna trasa vedie. Označme Di,j mesto, z ktorého sme prišli v deň j do mesta i, ak by sme išli po optimálnej trase končiacej v meste i v deň j. Hodnotu Di,j budeme počítať súbežne s hodnotou Ei,j. Di,j bude vlastne to mesto s, pre ktoré bude Es,j-1 + hs,i minimálne.

Mesto, v ktorom končí hľadaná optimálna trasa (t.j. také, pre ktoré je Ei,K minimálne) označme xK. Potom predchádzajúce mesto na optimálnej trase bude xK-1 = DxK,K. Vo všeobecnosti mesto na optimálnej trase, z ktorého sme prišli do mesta xi bude mesto xi-1 = Dxi,i.

Nakoniec venujme pár slov otázke, ako vzdialenosti hi,j ( 1<=qi,j<=qN) medzi jednotlivými mestami počítať. Použijeme štandardný Floyd-Warshallov algoritmus. Vstupom tohto algoritmu je matica hi,j (1<=i,j<=N), obsahujúca dĺžky ciest, spájajúcich jednotlivé dvojice miest (pre cestu vedúcu medzi mestami i a j s dĺžkou l položíme hi,j=hj,i=l, ak medzi i a j nevedie žiadna cesta, položíme hi,j=hj,i je nekonečno). Výstupom algoritmu je matica h, v ktorej hi,j je minimálna vzdialenosť, ktorú musíme precestovať, aby sme sa dostali z mesta i do mesta j.

Algoritmus bude pracovať v N cykloch. Po vykonaní k-teho cyklu (0<= k<=N) bude platiť, že hi,j je dĺžka najkratšej trasy z mesta i do mesta j, ktorá prechádza len cez mestá s číslom menším alebo rovným k. Na začiatku (t.j. po vykonaní 0 cyklov) je v hi,j uložená dĺžka priamej trasy bez prechádzania cez iné vrcholy. Pri vykonávaní k-teho cyklu, dĺžka trasy hi,j môže byť buď rovnaká ako v predchádzajúcom cykle (ak nevyužijeme možnosť viesť trasu z mesta i do mesta j cez mesto k), alebo rovná hi,k+hk,j (ak trasu z i do j vedieme cez mesto k). Vždy si samozrejme vyberieme kratšiu možnosť.

Implementácia

Dĺžky ciest načítavame priamo do poľa h, v ktorom aj počítame vzdialenosti medzi mestami F-W algoritmom. Na výpočet si nepotrebujeme pamätať všetky hodnoty Ei,j, stačí si pamätať iba dva stĺpce pre j a j+1. To robíme v poli optim, pričom optim[0] obsahuje hodnoty Ei,j pre j párne a optim[1] pre j nepárne. Ak však chceme zrekonštruovať optimálnu trasu, potrebujeme si pamätať aspoň hodnoty Di,j. Na tie nám však stačí typ byte. Hodnoty Di,j máme v poli pred, ktoré je vo vzorovom programe alokované dynamicky, aj keď obmedzenia v zadaní dovoľovali použiť statické pole.

Časová a pamäťová zložitosť

Časová zložitosť celého algoritmu bude O(N3 + KN2), z toho O(N3) je Floyd-Warshallov algoritmus. Pamäťová zložitosť bude O(N2 + KN), kde O(N2) pamäte zaberá matica h a O(NK) zaberajú matice E a D.

Poznámka

Existuje algoritmus, ktorý nepotrebuje úvodné predvypočítanie vzdialeností F-W algoritmom a ktorý na výpočet každého stĺpca matice E používa modifikáciu Dijkstrovho algoritmu. Tento algoritmus má časovú zložitosť O(K (M log N)), resp. O(K N2) (podľa implementácie Dijkstrovho algoritmu) a pamäťovú zložitosť O(M + NK).

Program Kina; {MO-P 49-III-5} const MAXN = 150; MAXK = 3000; VVELA = 1000000000; meno = 'kina'; type byteptr = ^byte; var h : array[1..MAXN, 1..MAXN] of word; {vzdialenosti medzi mestami} film : array[1..MAXN] of integer; {v ktorom meste aky film} por : array[1..MAXK] of integer; {poradie filmov, ktore chceme vidiet} pred : array[1..MAXN] of byteptr; E : array[0..1,1..MAXN] of longint; N,M,K : integer; p : integer; f,g : text; Procedure Nacitaj; var i,j,a,b,l : integer; Begin ReadLn(f,N,M,K); for i:=1 to N do Read(f,film[i]); for i:=1 to N do for j:=1 to N do h[i,j]:=60000; for i:=1 to N do h[i,i]:=0; for i:=1 to M do begin ReadLn(f,a,b,l); if h[a,b]>l then begin h[a,b]:=l; h[b,a]:=l; end; end; for i:=1 to k do Read(f,por[i]); End; Procedure Pocitaj; var i,j,kk,minkk,tmp1 : integer; min,pom : longint; tmp : byteptr; Begin {Floyd-Warshallov algoritmus na hladanie najkratsich ciest} for kk:=1 to N do for i:=1 to N do for j:=1 to N do begin pom:=h[i,kk]+longint(h[kk,j]); if h[i,j]>pom then h[i,j]:=pom; end; for i:=1 to N do GetMem(pred[i],K+1); for i:=1 to N do E[0,i]:=VVELA; E[0,1]:=0; p:=0; for i:=1 to K do begin for j:=1 to N do begin min:=VVELA; minkk:=0; if film[j]=por[i] then for kk:=1 to N do if min>E[p,kk]+h[kk,j] then begin min:=E[p,kk]+h[kk,j]; minkk:=kk; end; E[1-p,j]:=min; tmp:=pred[j]; Inc(tmp,i); tmp^:=minkk; end; p:=1-p; end; End; Procedure Vypis; var i, mini : integer; tmp : byteptr; buf : array[1..MAXK] of integer; Begin mini:=1; for i:=2 to N do if E[p,i]<E[p,mini] then mini:=i; if E[p,mini]>=VVELA then begin WriteLn(g,'nemozno'); end else begin WriteLn(g,E[p,mini]); buf[k]:=mini; for i:= k-1 downto 1 do begin tmp:=pred[buf[i+1]]; Inc(tmp,i+1); buf[i]:=tmp^; end; for i:=1 to k do begin Write(g,buf[i]); if i<k then Write(g,' ') else WriteLn(g); end; end; End; Begin Assign(f,meno+'.in'); ReSet(f); Assign(g,meno+'.out'); ReWrite(g); Nacitaj; Pocitaj; Vypis; Close(g); Close(f); End.