Úloha 5.u4: Rozdělení balíčku (3 b)

Zadáno v čísle 23.5.

Řešeno v čísle 23.7.

Zadání

Mám balíček $n$ karet, každá karta je buď červená, nebo černá. Počty červených a černých karet nemusí být stejné. Balíček zamíchám a rozložím do řady. Chci určit, zda a kde můžu řadu rozdělit tak, aby vlevo od rozdělení bylo právě tolik červených karet, kolik je černých karet vpravo od rozdělení. Rychleji proveditelná řešení budou hodnocena lépe.
Bonusový úkol: Nevím, kolik karet mám, a místo rozložení do řady se na ně budu postupně koukat. Kolik nejméně bitů informace si potřebuji pamatovat v momentě, kdy jsem viděl už $N$ karet, abych uměl reagovat jak na $(N+1)$-ní kartu, tak na informaci, že to již byly všechny karty? V prvním případě si chci nějak spočítat nové informace k zapamatování (staré pak zapomenu), v druhém chci odpovědět počtem karet, které je potřeba ze začátku balíčku odebrat, aby v odebrané části bylo tolik červených karet, kolik bude černých ve zbytku.

Řešení

Možná poměrně překvapivě, řešením je, že balíček chceme rozdělit na pozici odpovídající počtu černých karet v celém balíčku. Proč tomu tak je? Podívejme se rovnou na verzi, kdy karty dostáváme postupně. Správnost našeho postupu budeme dokazovat indukcí podle počtu karet.

Na začátku jsme žádné karty neviděli a náš algoritmus balíček rozdělí na pozici nula, což je správně. Nyní indukční krok. Pokud nám přijde červená karta, tak se dostala vpravo od rozdělení, což nijak neovlivní to, kde chceme balíček rozdělit. Pokud nám přijde černá karta, máme vpravo od rozdělení o jednu černou kartu víc, než je počet červených nalevo od rozdělení. Pokud posuneme pozici rozdělení balíčku o jedna doprava, mohou nastat dvě situace. První možností je, že jsme přesunuli na levou část červenou kartu, čímž jsme vyrovnali počty karet. Druhou možností je, že jsme přesunuli černou kartu. V tom případě bude na pravé straně o černou kartu méně, čímž jsme opět vyrovnali počet červených karet nalevo od rozdělení a počet černých karet napravo od rozdělení.

Pokud přišla červená karta, nechali jsme původní pozici rozdělení balíčku, pokud přišla černá karta, tak jsme pozici rozdělení posunuli o jedna vpravo. Řešením je tedy opravdu počet černých karet, z čehož jde i vidět, že řešení vždy existuje.

Nikdy nebudeme chtít ukládat číslo větší, než $N$. K uložení si tak velkého čísla budeme potřebovat $\mathcal{O}(\log N)$ bitů paměti.

Bonusová verze této úlohy (tedy ta, kde karty přichází postupně) je pěknou ukázkou takzvaných online algoritmů. Ty na rozdíl od běžných (offline) algoritmů nemají na začátku k dispozici celý vstup, ale dostávají ho postupně a nemají možnost si ho zapamatovat celý. Je možná až překvapivé, kolik problémů se dá řešit online – jedním z takových byla i tato úložka. Když nějaký problém nelze vyřešit online, tak lze často najít alespoň přibližné řešení – pokud máme nějakou míru, jak je dané řešení problému dobré, tak lze často najít online algoritmus, který dá řešení nejvýše konstanta-krát horší, než je optimum. Takové algoritmy mají i tu výhodu, že potřebují méně paměti a jsou často rychlejší než jejich offline verze. V praxi nám často stačí řešení přibližné, což je důvodem, proč se online algoritmy často používají, když je potřeba zpracovávat hodně dat – třeba při zpracovávání DNA.

Kuba