Matematická olympiáda – kategorie P

Ukázková úloha

(Úlohu najdete i jako příklad ve FIKSu.)

Časový limit: 1s, paměťový limit: 512 MB

Pepíček se celý opálený a spokojený vrací z dovolené v Tramtárii. Na letišti si ale vzpomněl, že zapomněl mamince a tatínkovi přivést suvenýry! Naštěstí má posledních \(k\) tramtárských liber. Ty jsou mu v rodném Kocourkově k ničemu, takže je chce všechny utratit. V místním obchodu prodávají \(n\) suvenýrů očíslovaných \(1\)\(n\), z nichž \(i\)-tý stojí \(a_i\).

Prodavač je podivín, proto každý má každý suvenýr jinou cenu a navíc jsou na poličce uspořádané podle ceny, tj. pro \(i\) od \(1\) do \(n-1\) platí \(a_i < a_{i+1}\).

Pomozte Pepíčkovi najít dvojici suvenýrů, za které by utratil zbylé tramtárské libry, tj. dva různé indexy \(i\) a \(j\) takové, že \(a_i + a_j = k\), nebo určete, že taková dvojice neexistuje. Pokud existuje víc řešení, vypište libovolné z nich.

Formát výstupu a výstupu

Na prvním řádku vstupu je počet suvenýrů \(n\) a kolik tramtárských liber Pepíček vlastní, \(k\). Na dalším řádku vstupu jsou ceny suvenýrů: celá čísla \(a_1, \ldots, a_n\). Pro \(i\) od \(1\) do \(n-1\) platí \(a_i < a_{i+1}\).

Na výstup vypište na jednom řádku dvě čísla \(i\) a \(j\) taková, že \(a_i + a_j = k\), nebo vypište reseni neexistuje v případě, že řešení neexistuje.

Omezení a hodnocení

V každé sadě platí \(1 \leq a_i \leq 10^9\), \(1 \leq k \leq 10^9\). V jednotlivých sadách platí:

Příklady

Vstup:

4 10
2 3 5 7

Výstup:

2 4

Výstup znamená, že volíme dvojici \((a_2, a_4)\). A vskutku, \(a_2 + a_4 = 3 + 7 = 10 = k\).

Vstup:

4 14
2 3 5 7

Výstup:

reseni neexistuje

Pro \(k=14\) neexistuje vhodná dvojice suvenýrů. 4 4 není platné řešení, protože používá dvakrát stejný suvenýr (koupit ho můžeme pouze jednou).

Řešení

Rychle nás napadne přímočarý algoritmus: zkusíme všechny dvojice suvenýrů, a pokud se ceny nějakých dvou sečtou na \(k\), máme řešení. Nyní si ukážeme, jak bychom jej mohli zapsat jako řešení teoretické úlohy a jako řešení praktické úlohy.

Teoretické řešení – pomalé

Projdeme všechny dvojice suvenýrů a pro každou dvojici zkontrolujeme, zda je součet cen roven \(k\). Dvojici pak vypíšeme jako výsledek. Protože projdeme všechny dvojice, nemůže se stát, že bychom řešení nenašli, i když existuje; pokud tedy žádnou dvojici nenajdeme, vypíšeme reseni neexistuje. Dvojic suvenýrů je nejvýše \(n^2\), projít všechny tedy trvá \(O(n^2)\) času. (Protože nezáleží na pořadí v rámci dvojice, stačilo by vyzkoušet pouze \(\binom{n}{2} = \frac{n(n-1)}{2}\) unikátních dvojic, ale na tom z hlediska asymptotické složitosti nezáleží.) Potřebujeme si kromě vstupu udržovat pouze konstantně mnoho proměnných, paměťová složitost je tedy \(O(n)\).

Praktické řešení – pomalé

Kód si můžete zkusit spustit online zde.

Všimněte si, že v praktickém řešení jsme museli řešit různé detaily, které jsme vynechali v teoretickém, například počítači musíme říct, aby přeskočil situace, kdy \(i=j\), ale v teoretickém stačilo napsat všechny dvojice. Také jsme museli na konci k indexům přičíst jedna, protože C++ indexuje pole od nuly. To v teoretickém také není třeba zmiňovat.

Toto řešení by získalo 3 body. Běžný počítač zvládne za sekundu provést řádově \(10^8\)\(10^9\) operací (slovo operace je zde použito v intuitivním nepřesném smyslu), a vyzkoušet všechny dvojice pro \(n=1000\) je asi \(10^6\) operací, což se do časového limitu vejde. Pro \(n=100\,000=10^5\) už bychom ale museli provést asi \(10^{10}\) operací, což je příliš mnoho.

Nyní zkusíme vymyslet chytřejší řešení. Zatím jsme nevyužili to, že je seznam suvenýrů seřazený. V seřazeném seznamu můžeme použít tzv. binární vyhledávání:

Teoretické řešení – binární vyhledávání

Projdeme všechny indexy \(i\) a pro každé \(i\) se pokusíme najít \(j\) takové, že \(a_i+a_j=k\). Díky tomu, že je seznam seřazený, platí, že pokud pro nějaké \(j_1\): \(a_i + a_{j_1} \gt k\), pak pro všechna \(j_2 > j_1\) také platí \(a_i + a_{j_2} > k\). Jakmile tedy nějaké takové \(j_1\) najdeme, nemusíme zkoušet \(j > j_1\). Obdobně pokud najdeme \(j_1\) takové, že \(a_i + a_{j_1} < k\), nemusíme zkoušet \(j<j_1\).

To nám umožní použít binární vyhledávání. Budeme si udržovat interval \([j_{min}, j_{max}]\) hodnot \(j\), které má ještě cenu zkoušet. Vyzkoušíme \(j\) uprostřed tohoto intervalu, tj. za \(j\) zvolíme zaokrouhlený průměr \(j_{min}\) a \(j_{max}\). Pokud \(a_i+a_j=k\), nalezli jsme řešení. Pokud \(a_i + a_j < k\), nemá cenu zkoušet menší hodnoty \(j\), omezíme tedy náš interval na \([j+1,j_{max}]\). Obdobně pokud \(a_i+a_j > k\), omezíme interval na \([j_{min}, j-1]\). Ve chvíli, kdy je interval prázdný, neexistuje pro toto \(i\) vhodné \(j\). Protože v každém kroku se zmenší interval alespoň na polovinu, zabere pouze \(\log_2 n\) kroků, než bude interval prázdný. Jedno hledání tedy zabere \(O(\log n)\) kroků.

Binární vyhledávání provedeme pro každé \(i\), pokud pro nějaké najdeme vhodné \(j\), vypíšeme výsledek. Jinak řešení neexistuje. Časová složitost je \(O(n \log n)\), paměťová složitost \(O(n)\).

Detailnější popis binárního vyhledávání najdete v Průvodci. Stačilo by řešení napsat ještě o něco stručněji; můžete předpokládat, že opravovatelé vědí, co je to binární vyhledávání, což jsme zde nepředpokládali. Obecně můžete předpokládat, že pojmy, techniky a algoritmy popsané v IOI Syllabu není potřeba blíže rozepisovat.

Praktické řešení – binární vyhledávání

Toto řešení by získalo 7 bodů. Platí, že \(\log_2 10^5 \approx 17\), takže operací bude zhruba \(2 \cdot 10^6\). Pro \(n=10^7\) by řešení nebylo dost rychlé.

Dodejme, že i kdyby seznam na vstupu nebyl seřazený, mohli bychom si ho seřadit sami a protože řazení trvá \(O(n \log n)\), celková časová složitost by byla pořád \(O(n \log n)\). Ukážeme si ale rychlejší řešení, které používá metodu dvou ukazatelů (two pointers) a běží v čase \(O(n)\). To už musí předpokládat, že je seznam seřazený, jinak by se časová složitost zhoršila.

Teoretické řešení – rychlé

Budeme procházet všechny suvenýry \(i\) od \(1\) do \(n\). Pro dané \(i\) budeme hledat vhodné \(j\). Začneme s \(j=n\) a dokud je součet cen suvenýrů \(i\) a \(j\) moc velký, znamená to, že správné \(j\) pro toto \(i\) (pokud existuje) musí být někde nalevo, tj. musí být menší. Dokud je tedy součet moc velký, budeme snižovat \(j\).

Buď skutečně najdeme \(j\), pro které \(a_i + a_j = k\), nebo se dostaneme do situace, kdy už nám posouvání \(j\) nepomůže (součet už je menší než \(k\)) nebo ani \(j\) posouvat nemůžeme (když \(j=1\)). Pokud jsme nenašli vhodnou dvojici pro toto \(i\), zkusíme \(i\) zvýšit.

Označme starou hodnotu \(i_1\) a novou hodnotu \(i_2\). Nejdůležitější pozorování je, že pokud \(a_{i_1} + a_j > k\), pak \(a_{i_2} + a_j > k\). To proto, že seznam je seřazený a tedy \(a_{i_2} > a_{i_1}\). To znamená, že nemusíme zkoušet žádné hodnoty \(j\), které jsme už vyřadili pro \(i_1\). Místo od \(n\) tedy začneme tam, kde jsme přestali.

Časová složitost tohoto algoritmu je \(O(n)\); pro fixní \(j\) vyzkoušíme dvojici jen s jedním \(i\), pak už ho vyřadíme. Kromě toho uděláme \(O(n)\) kroků při posouvání \(i\), dohromady tedy pořád \(O(n)\). Potřebujeme si kromě vstupu udržovat pouze konstantně mnoho paměti, paměťová složitost je tedy \(O(n)\).

Praktické řešení – rychlé

Řešení by získalo plný počet bodů. Poznamenejme ještě, že v praktických úlohách je pro zadavatele často obtížné nastavit úlohu tak, aby \(O(n)\) řešení získalo plný počet bodů, ale chytře optimalizované \(O(n \log n)\) řešení neprošlo. Ve skutečnosti by tedy dost možná praktické řešení využívající binární vyhledávání bylo dost rychlé, aby také získalo 10 bodů. V teoretické úloze by se to pochopitelně stát nemohlo.