Matematická olympiáda – kategorie P

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

P-III-1 Jednotková podmatice

Nechť [i,j] jsou souřadnice některého prvku matice A. Potom tento prvek je pravým dolním rohem jednotkové podmatice velikosti d>0 právě tehdy, jsou-li splněny následující podmínky:

• A[i,j]=1
• na souřadnicích [i-1,j-1] leží v matici A pravý dolní roh jednotkové podmatice velikosti alespoň d-1
• alespoň d-1 prvků v matici A nad prvkem A[i,j] jsou nuly (t.j. A[i-1,j]=A[i-2,j]=...=A[i-d+1,j]=0)
• alespoň d-1 prvků v matici A nalevo od prvku A[i,j] jsou nuly (t.j. A[i,j-1]=A[i,j-2]=...=A[i,j-d+1]=0)

Označme jako m[i,j] velikost největší jednotkové podmatice, která má pravý dolní roh v prvku A[i,j]. Pokud A[i,j]=0, pak jistě bude m[i,j] = 0. Z technických důvodů dodefinujeme hodnoty m[i,0] = m[0,i] = 0 pro všechna i=1,2,...,N. Umožní nám to jednodušší zápis následující přesné definice hodnot m[i,j].

Nechť souvislý úsek nul (ukončený jedničkou nebo okrajem matice) nalevo od A[i,j] má délku B a souvislý úsek nul nad A[i,j] má délku C. Potom:
m[i,j] = 0, jestliže A[i,j]=0
m[i,j] = min{m[i-1,j-1], B, C} + 1, jestliže A[i,j]=1
Hodnoty B a C můžeme pro všechny prvky matice A snadno spočítat a uložit do pomocných matic při jediném průchodu v čase O(n²). Potom již můžeme postupně počítat všechny hodnoty m[i,j]. Budeme-li postupovat například po řádcích shora dolů, budeme mít při výpočtu m[i,j] už k dispozici hodnotu m[i-1,j-1]. Stačí tedy na základě známých hodnot m[i-1,j-1], B, C a A[i,j] v konstantním čase určit hodnotu m[i,j]. Celková časová složitost algoritmu je tudíž O(n²).

Právě popsané řešení úlohy nyní ještě vylepšíme z hlediska paměťové náročnosti. Hodnoty B a C totiž není třeba počítat předem pro všechny prvky matice A a ukládat je do pomocných matic. Hodnotu B si můžeme vždy průběžně počítat při průchodu řádkem matice zleva doprava a udržovat si ji v jedné pomocné proměnné (tato hodnota vůbec nezávisí na ostatních řádcích matice). Hodnoty C se snadno počítají na základě hodnot C v předchozím řádku, stačí nám tedy použít pomocné jednořádkové pole. Hodnoty m[i,j] si budeme ukládat přímo do matice A.

program Jednotkova_podmatice; {v dané matici z 0/1 hledá maximální jednotkovou podmatici} const MaxN = 20; {maximální velikost matice} var A: array[0..MaxN, 0..MaxN] of integer; {matice} C: array[1..MaxN] of integer; N: integer; {velikost matice} Max: integer; {výsledek} B, i, j:integer; function Min(a, b, c: integer): integer; {minimum ze tří čísel} begin if b < a then a := b; if c < a then a := c; Min := a; end; {function Min} begin writeln; write('Velikost zkoumané matice: '); readln(N); writeln('Prvky matice po řádcích - pouze 0/1:'); for i:=1 to N do for j:=1 to N do read(A[i,j]); A[0,0] := 0; for i:=1 to N do begin A[i,0] := 0; A[0,i] := 0; C[i] := 0 end; Max:=0; for i:=1 to N do {cyklus pro řádky} begin B := 0; for j:=1 to N do {cyklus pro sloupce} if A[i,j]=0 then begin B := B+1; {souvislý úsek nul v řádku} C[j] := C[j]+1; {souvislý úsek nul v sloupci} end else {A[i,j]=1} begin A[i,j] := Min(A[i-1,j-1], B, C[j]) + 1; if A[i,j] > Max then Max := A[i,j]; B := 0; C[j] := 0; end; end; writeln; writeln('Velikost strany maximální jednotkové podmatice: ',Max) end.

P-III-2 Kódy

Následující kód řeší obě podúlohy (nikoliv však současně - není schopen rozhodnout, jestli došlo k opravitelné jednochybě nebo neopravitelné dvojchybě).

Nechť zpráva má n=2^k-1 bitů označených b₁..b_n (v případě, že je kratší, považujeme zbylé bity za nuly). My ji doplníme o paritní bit p (stejně jako v ukázkovém příkladu v zadání) a zabezpečovacími bity c₀ až c_k-1, jež budou paritními bity jednotlivých bloků zvolených podle následujícího pravidla: v i-tém bloku budou právě ty bity, jejichž pořadové číslo (pro bit b_z to je z) má v i-tém binárním řádu jedničku (každý bit původní zprávy tak patří do alespoň jednoho bloku a je jednoznačně identifikován tím, do kterých bloků patří a do kterých nikoliv).

Úloha a

Po příjmu zprávy zkusíme podle přijatých datových bitů znovu spočíst všechny bity kontrolní (tedy p a všechna c_i). Pokud souhlasí s těmi, které byly přijaty, zpráva byla přijata bezchybně nebo došlo k více jak jedné chybě. Pokud došlo k právě jedné chybě, mohlo k ní dojít těmito způsoby:

• V jednom datovém bitu b_i: v tomto případě zaručeně nesouhlasí paritní bit p a rovněž některé z blokových paritních bitů c_j - konkrétně ty, jež odpovídají blokům, do nichž bit b_i patří. Jenže tím, ve kterých blocích se b_i nachází, je již jeho pořadové číslo i jednoznačně určeno.
• V jednom kontrolním bitu c_i: v tomto případě souhlasí centrální paritní bit p, čímž tento případ snadno odlišíme.
• V centrálním paritním bitu p: v tomto případě nesouhlasí tento bit, ale souhlasí všechny ostatní kontrolní bity, což znamená, že chyba se nenachází v žádném bloku, ale to u chyb v datových bitech nastat nemůže.

Úloha b

Nedošlo-li k žádné chybě, souhlasí všechny zabezpečovací bity s jejich vypočtenými hodnotami (viz řešení úlohy a). Došlo-li k právě jedné chybě, nesouhlasí centrální paritní bit nebo jeden z blokových paritních bitů (viz diskuse výše). Došlo-li k právě dvěma chybám, mohou nastat následující případy:

• Chyba ve dvou různých datových bitech: centrální paritní bit jistě souhlasí, ale jelikož každý datový bit je jednoznačně popsán kombinací bloků, do nichž patří, zaručeně existuje alespoň jeden blok, do kterého patří právě jeden z chybně přijatých bitů, a proto jeho blokový paritní bit nesouhlasí.
• Chyba ve dvou různých blokových paritních bitech: centrální paritní bit souhlasí, ale oba chybně přijaté blokové paritní bity nikoliv.
• Chyba v jednom datovém bitu a jednom blokovém paritním bitu: nesouhlasí centrální paritní bit.
• Chyba v jednom datovém bitu a centrálním paritním bitu: centrální paritní bit souhlasí, ale alespoň jeden z blokových nikoliv (každý datový bit je v alespoň jednom bloku).
• Chyba v centrálním paritním bitu a jednom z blokových: nesouhlasí centrální paritní bit.

Ve všech případech tedy poznáme, že k chybě došlo.

P-III-3 Kombinační sítě

Nechť A= {0,1,2,3,4,5,6,7,8,9,@} je abeceda naší sítě. Pak pro všechny symboly s, prvky A, označíme C _{<= s} počet vstupů A_i, na nichž je hodnota menší nebo rovná s (jelikož C _{<= s} <= n, lze všechna C _{<= s} vyjádřit ve dvojkové soustavě nějakými bity C _{<= s,1 ... m}, kde m=[log₂ n]). Výstup B_i pak bude mít hodnotu s právě tehdy, je-li s největší prvek abecedy, pro nějž platí C _{<= s} <= i. Jinými slovy: setříděná posloupnost vypadá tak, že nejdříve obsahuje C _{<= 0} nul, pak až do pozice C _{<= 1} jedničky ... až do pozice C _{<= 9}=n devítky.

Pro realizaci tohoto algoritmu kombinační sítí budeme využívat následující podsítě:

• TEST _<= (s,x) - hradlo mající na výstupu 1, pokud x <= s, jinak 0.
• ADD_t(X_{1... t}, Y_{1... t}) = Z_{1... t} - sčítačky sčítající t-bitová binární čísla X a Y s výsledkem Z (odvozeno v oblastním kole s hloubkou O(log t)).
• CMP_t(A_{1... t}, B_{1... t}) = R - komparátory porovnávající dvě t-bitová binární čísla a dávající výsledek R=0 pro A=B, R=1 pro A < B a R=2 pro A > B. Odvodíme známým způsobem:
  • Pro t=1 triviální: CMP₁(0,0) = CMP₁(1,1) = 0, CMP₁(0,1) = 1, CMP₁(1,0) = 2. Tento předpis přímo definuje hradlo CMP₁.
  • Pro t=2t^p: rozdělíme obě čísla na poloviny: A=A^HA^L, B=B^HB^L, vypočteme t^p-bitovými komparátory hodnoty C^H=CMP_t^p(A^H,B^H) a C^L=CMP_t^p(A^L,B^L) a pokud C^H <> 0, použijeme jako výsledek C^H, jinak je výsledkem C^L (pro tuto funkci opět definujeme hradlo).
  Tímto postupem získáme pro porovnávání dvou t-bitových čísel síť hloubky O(log t).
• STEP_s(a,x) (s prvkem A) - hradla s následující přechodovou funkcí:
  • STEP_s(a,x) = s, pokud x <> 1.
  • STEP_s(a,1) = a.
• FIRST(x₀, ..., x₉) - výstupem je nejmenší s takové, že x_s <> 1. Konstruujeme z hradel STEP_s:
  • FIRST(x₉) = 9
  • FIRST(x_s,...,x₉) = STEP_s (FIRST(x_s+1,...,x₉),x_s).
  Hloubka sítě FIRST je 9.

Nejprve spočteme pomocné proměnné X _{<= s,i} = TEST _<= (s,X_i) mající hodnotu 1 právě tehdy, je-li X_i <= s, jinak 0 (to zvládneme sítí hloubky 1). Rozšíříme-li každou z těchto proměnných nulami na m-bitové číslo X _{<= s,i,1 ... m}, je zjevně C _{<= s} součtem čísel X _{<= s,i} přes všechna i. Pro určení tohoto součtu stačí využít asociativity sčítání a nejdříve sečíst všechny dvojice X _{<= s,2k} + X _{<= s,2k+1}, pak dvojice těchto dvojic atd. (viz hledání minima a maxima v domácím kole, kde se používá tentýž trik), čimž získáme konečný součet C _{<= s} sítí o m úrovních, z nichž každá se skládá z m-bitových sčítaček (ADD_m) hloubky O(log m), tedy celková hloubka sítě určující C _{<= s} je O(m log m)=O(log n loglog n).

Poté spočteme pro každou výstupní pozici i a každý symbol abecedy s hodnoty Z_s,i = CMP_m(C _{<= s}, i) (hloubka O(log m)) a definujeme B_i = FIRST(Z_0,i, ..., Z_9,i) jako výstupy sítě (hloubka O(1)). Tedy B_i je nejmenší s takové, že CMP_m(C _{<= s},i) <> 1, tudíž nejmenší takové, pro nějž C _{<= s} >= i, což je přesně hodnota odvozená v prvním odstavci.

Síť se skládá ze čtyř částí hloubek po řadě O(1), O(log n loglog n), O(loglog n) a O(1), její celková hloubka proto je O(log n loglog n).