Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Romanovi na [email protected]
Macín a Ondro sú ostrieľaní lezci a na jar sa rozhodli vyraziť za adrenalínom do Tatier. Pred expedíciou si kúpili turistickú mapu, ktorá vyzerala nasledovne:
Medzi každými dvoma vrcholmi na mape je jedno číslo, ktoré reprezentuje rozdiel nadmorskej výšky pravého a ľavého vrcholu. Macín s Ondrom sa po mape budú pohybovať zľava doprava. Nevedia však, v ktorom vrchole svoju expedíciu začnú a preto potrebujú pomoc pri výbere trasy.
Vrcholy z mapy si očíslujeme zľava doprava $0$ až $N$. Údaje o nadmorských výškach budeme reprezentovať pomocou poľa $A$, ktoré obsahuje jednotlivé rozdiely. Prvok $A[i]$ obsahuje rozdiel medzi výškou vrchola $i+1$ a $i$. Pole $A$ pre našu mapu vyzerá nasledovne:
Terka chalanom poradila, aby si predpočítali pre pole $A$ prefixové súčty. Ide o list, na ktorého $i$-tej pozícii je súčet všetkých čísel, ktoré sú v pôvodnej postupnosti na pozíciách od $0$ po $i - 1$. Pre pole $A$ bude preto pole $P$ prefixových súčtov vyzerať nasledovne:
Všimnite si, že tento list je o jedna dlhší ako $A$ a začína $0$. Na $0$-tej pozícii totiž musí byť súčet čísel od $0$ po $−1$, čo je $0$. Napríklad na $3$-tej pozícii je $6$, pretože súčet prvých $3$ čísel poľa $A$ je $3 - 1 + 4 = 6$.
(2 body) Ondru pred cestou zaujíma, kde má mapa svoje stredové vrcholy. Stredový vrchol je taký vrchol, pre ktorý je súčet rozdielov z najľavejšieho vrcholu na mape rovnaký ako súčet rozdielov od najpravejšieho vrcholu na mape. Presnejšie teda hľadáme všetky vrcholy $k$ také, že $$A[0] + \dots + A[k - 1] = A[k] + \dots + A[N - 1]$$ Napríklad na mape zo začiatku zadania sú stredovými vrcholmi vrcholy $3$ a $6$. Vymyslite ako efektívne nájsť stredové vrcholy pre pole $A$. Efektívnym riešením v tomto prípade myslíme také, ktoré pristupuje k jednotlivým prvkov poľa $A$ a $P$ čo najmenejkrát. Pošlite nám slovný popis vášho postupu. Váš popis by mal byť zrozumiteľný aj bez znalosti programovania a mal by ho vedieť odsimulovať ktokoľvek s perom a papierom.
(2 body) Macín a Ondro plánujú špeciálnu túru, pri ktorej skončia v rovnakej nadmorskej výške, z akej vyrážali. To znamená, že celkový súčet rozdielov nadmorských výšok na trase je rovný $0$. Viete im poradiť, ako pomocou prefixových súčtov nájsť súvislý úsek v poli $A$, ktorého súčet je $0$? Pri tejto podúlohe neposielajte algoritmus, iba popíšte, ako si v poli prefixových súčtov všimnúť úsek so súčtom $0$.
(3 body) Chalanov pri plánovaní často zaujíma, aký je celkový rozdiel nadmorskej výšky medzi konkrétnymi dvoma vrcholmi. Napríklad pre vrcholy $2$ a $5$ je celkový rozdiel $4 - 3 + 5 = 6$. Všimnite si, že pre vrcholy $a$ a $b$ také, že $a < b$, vieme vypočítať celkový rozdiel ako súčet čiastkových rozdielov, tj. $A[a] + A[a + 1] + … + A[b - 1]$. Macín ale stále prichádza s novými nápadmi na trasy a Ondrovi sa už nechce počítať rozdiely prvok po prvku. Musí to ísť predsa lepšie! Vašou úlohou je preto prísť na to, ako šikovne spočítať celkový rozdiel medzi výškami vrcholov $a$ a $b$ pomocou poľa prefixových súčtov $P$.
(3 body) Ako pre pole $A$ vytvoriť pole prefixových súčtov $P$? Podobne ako v podúlohe a) vymyslite efektívne riešenie, teda také, ktoré k prvkom poľa $A$ a $P$ prístupi čo najmenejkrát, a pošlite nám jeho slovný popis.
(5 bodov) Telo sa musí vyššej nadmorskej výške vždy prispôsobiť. Výstupiť preto za jeden deň oveľa vyššie a prenocovať tam by mohlo byť nebezpečné. Chalani si určili výšku $k$, o ktorú chcú za jeden deň vystúpiť vyššie. Vašou úlohou bude nájsť všetky dvojice vrcholov, medzi ktorými je celkový rozdiel nadmorských výšok práve $k$. Napríklad na našej mape by pre $k = 4$ splňovali túto podmienku dvojice vrcholov $(2, 3)$ a $(2, 6)$. Opäť nám pošlite slovný popis čo najefektívnejšieho riešenia.
Ak viete programovať, niektoré z podúloh si môžete vyskúšať naprogramovať a poslať nám vaše kódy. Nedostanete síce body naviac, ale vaše programy okomentujeme a poradíme vám, čo by sa dalo spraviť lepšie alebo krajšie. Pri programátorských úlohách vám nedávame spätnú väzbu k vašim programom, preto máte teraz jedinečnú šancu.
P.S.: Ondro s Macínom a kamarátmi Tatry skutočne navštívili. Ako sa Čechom v Tatrách darilo a či ich zachraňovala horská služba, sa dozviete v článku od Ondru.
Táto úloha bola venovaná prefixovým súčtom, ktoré sú neoddeliteľnou súčasťou výbavy programátora. Pochopenie vzorového riešenia vám určite pomôže pri riešení mnohých úloh v budúcnosti.
Vašou úlohou bolo nájsť všetky vrcholy $k$ také, že $$A[0] + \dots + A[k - 1] = A[k] + \dots + A[N - 1]$$ V zadaní bolo spomenuté, že pole prefixových súčtov $P$ obsahuje na $i$-tej pozícii súčet všetkých čísel, ktoré sú v pôvodnej postupnosti na pozíciách od $0$ po $i - 1$. To je vlastne prvý súčet z rovnosti vyššie. Teda pre každý vrchol $k$ platí, že $$P[k] = A[0] + \dots + A[k - 1]$$ Napríklad pre vrchol $4$ je súčet $A[0] + A[1] + A[2] + A[3]$ rovný $3$, a preto aj hodnota $P[4]$ je $3$.
Všimnite si, že súčet na druhej strane rovnosti, $A[k] + \dots + A[N - 1]$, je rovný celkovému súčtu prvkov poľa $A$ bez ľavej strany z pôvodnej rovnosti. Formálne $$A[k] + \dots + A[N - 1] = (A[0] + \dots + A[N - 1]) - (A[0] + \dots + A[k - 1])$$ Posledné pozorovanie je, že celkový súčet poľa $A$ nájdeme v poli prefixových súčtov na poslednom, $N$-tom mieste.
Aby $k$ bolo stredovým vrcholom, musí preto platiť $$P[k] = P[N] - P[k]$$
Pri riešení teda stačí prejsť v jednom cykle postupne všetky možné $k$, a pri každom overiť podmienku uvedenú vyššie.
`pre k := 0 do N:
ak (P[k] == P[N] - P[k]):
vypis(k + ' je stredovy vrchol')`
Pri každom vrchole sa pozrieme na 3 hodnoty poľa $P[]$, spravíme jedno porovnanie a prípade niečo vypíšeme. Celkovo teda pre jeden vrchol vykonáme konštantne veľa operácii. To znamená, že počet operácií pre jeden vrchol nezávisí od vstupných hodnôt, napríklad od hodnoty $N$. Vrcholov máme $N + 1$, takže program vykoná $3 \cdot (N + 1)$ prístupov k prvkom poľa $P$. To je lineárne veľa v závislosti od $N$, a preto má naše riešenie časovú zložitosť $O(N)$. Uvedomte si, že rýchlejšie riešenie nevymyslíme, pretože v najhoršom prípade by každý z vrcholov bol stredový (samé hodnoty 0) a v takom prípade by sme museli vypísať všetkých $N + 1$ vrcholov. Operácia vypísania $N + 1$ prvkov má zložitosť $O(N)$, takže aj keby sme našli všetky stredové vrcholy rýchlejšie ako v $O(N)$, ich výpis nám zaberie $O(N)$ operácii.
Kedy je úsek medzi dvoma vrcholmi $a$ a $b$ ($a < b$) rovný $0$? V zadanej úlohe túto podmienku spĺňajú napr. vrcholy $1$ a $4$ a tiež $34$ a $6$. Zjavne musí platiť $$A[a] + A[a + 1] + \dots + A[b - 1] = 0$$ Súčet na ľavej strane môžeme dostať aj tak, že odčítáme súčet prvkov po $A[a - 1]$ od súčtu po $A[b - 1]$. Teda $$A[a] + A[a + 1] + \dots + A[b - 1] = (A[0] + \dots + A[b - 1]) - (A[0] + \dots + A[a - 1])$$ Na pravej strane dostávame prefixové súčty $P[b]$ a $P[a]$ takže skrátene $$A[a] + A[a + 1] + \dots + A[b - 1] = P[b] - P[a]$$ Tu zároveň dostávame riešenie nasledujúcej podúlohy, ktorá sa pýta, ako vypočítať súčet úseku od $a$ po $b - 1$. Pokračujme ale ďalej. My teraz chceme, aby bol súčet medzi $a$ a $b$ rovný $0$. Preto môžeme do rovnice vyššie namiesto všeobecného súčtu napísať práve $0$, ktorú chceme dostať. $$0 = P[b] - P[a]$$ Odtiaľ vidíme, že tento prípad nastane práve vtedy, keď $P[a] = P[b]$. Preto môžeme povedať, že súčet medzi vrcholmi $a$ a $b$ je rovný $0$ ak sa prefixové súčty $P[a]$ a $P[b]$ rovnajú.
Ako bolo avizované v predošlom riešení, súčet $A[a] + A[a + 1] + \dots + A[b - 1]$ pre $a < b$ vieme získať pomocou prefixových súčtov ako rozdiel $P[b]$ a $P[a]$. $$A[a] + A[a + 1] + \dots + A[b - 1] = P[b] - P[a]$$ Ak už máme vypočítané prefixové súčty, stačí nám jediná aritmetická operácia na vypočítanie celého súčtu úseku. Namiesto postupného pričítavania hodnôt medzi $a$ a $b-1$, ktorých by mohlo byť až $N$ máme zakaždým zaručené iba jedno odčítanie. Takéto riešenie je teda oveľa rýchlejšie.
Ako prvé riešenie by nám mohlo napadnúť $i$-tu pozíciu $P$ spočítať tak, že spočítame všetky prvky od $0$ po $i - 1$, teda
`pre i := 0 do N:
sucet := 0
pre j := 0 do i - 1:
sucet := sucet + A[j]
P[i] := sucet`
Toto je korektné riešenie, ale zbytočne pomalé. V našom programe $P[i]$ počítame tak, že sčítame postupne všetky prvky $A[0], \dots, A[i - 1]$. Potom pre $i + 1$ znovu sčítavame postupne $A[0], \dots, A[i - 1], A[i]$. Všimnite si, že medzi členmi $i$ a $i + 1$ poľa $P$ nie je veľký rozdiel, konkrétne $P[i + 1]$ obsahuje oproti $P[i]$ hodnotu $A[i]$ navyše. Veľa roboty tak robíme opakovane. Tento fakt vieme využiť nasledovne:
`P[0] := 0
pre i := 0 do N - 1:
P[i + 1] := P[i] + A[i]`
Je jasné, že druhé riešenie je výrazne rýchlejšie, prvý cyklus je totiž rovnaký, v prvom v prípade sa v ňom však opakujeme, v druhom už nie. Toto zlepšenie je však výrazné aj v časovej zložitosti. Keď sa pozrieme na počet sčítaní, ktoré musíme spraviť, v prvom prípade to bude
$$1 + 2 + 3 + \dots + N = \frac{N(N+1)}{2}$$
, pretože v prvom opakovaní spravíme jedno sčítanie, v druhom dve, atď1. Takýto počet operácií potom zaokrúhlime na $N^2$ a povieme, že časová zložitosť je $O(N^2)$.
Druhé riešenie však spraví iba $N$ sčítaní a jeho časová zložiosť je preto iba $O(N)$, čo je opäť raz optimálne, keďže hodnoty poľa $A$ musíme v čase $O(N)$ načítať.
Táto podúloha má aj svoju ťažšiu verziu. Jej zadanie nájdeš na konci vzoráku.
V tejto podúlohe bolo vašou úlohou vypísať všetky dvojice $(a, b)$, pre ktoré platí $P[b] - P[a] = k$. Nasledujúce riešenie prejde v cykle všetky dvojice $(i, j)$ také, že $i < j$ a overí podmienku zo zadania.
`pre i := 0 do N:
pre j := i + 1 do N:
ak (P[j] - P[i] == k):
vypis(i + ' ' + j)`
Všetkých dvojíc je spolu $\frac{N(N + 1)}{2}$. Prečo? Predstavte si, že pre vrchol $0$ vyberáme druhý vrchol do dvojice. Máme $N$ možností ($1, 2, \dots, N$). Ak pre vrchol $1$ vyberáme druhý vrchol do dvojice, máme $N - 1$ možnosti ($2, 3, \dots, N$). Ak by sme takto pokračovali ďalej, dostaneme spolu počet všetkých dvojíc $$N + (N - 1) + \dots + 2 + 1 + 0$$ Ak tento súčet otočíme, je to opäť súčet prvých $N$ prirodzených čísel, s ktorým sme sa už stretli v podúlohe D. V poznámke pod vzorákom sa dozviete prečo sa tento súčet rovná $\frac{N(N + 1)}{2}$.
V podúlohe D sme tiež zistili, že tento počet rastie kvadraticky v závislosti na $N$. To znamená, že naše riešenie má kvadratickú časovú zložitosť $O(N^2)$, pretože každú dvojicu prejde práve raz a spraví pre ňu konštantne veľa operácií (pristúpi k $2$ prvkom poľa $P$, vyhodnotí podmienku a prípadne vypíše hlášku na výstup). Uvedomte si, že lepšie riešenie nevymyslíme, pretože v najhoršom prípade by každá z dvojíc vrcholov mohla mať medzi sebou rozdiel $k$ a všetky by sme ich tak museli vypísať.
Ťažšia verzia tejto úlohy sa nepýta na všetky dvojice s rozdielom $k$, ale iba na ich počet. Výstupom tak bude už iba jedno číslo, čiže časová zložitosť riešenia nie je limitovaná veľkosťou výstupu ako v pôvodnej podúlohe. Prídete na to ako efektívne vyriešiť túto úlohu?