Toto je úloha z 30. ročníka domáceho kola Olympiády v informatike (2014/2015) kategórie A. Text je jemne upravený. Úloha bola pôvodne riešená na hodinách tohto predmetu v zimnom semestri v akademickom roku 2017/2018. Ide o implementáciu zjednodušeného riešenia problému zalamovania textu v imaginárnom sadzobnom systéme.

Zadania súťažných úloh Olympiády v informatike vyzerajú pekne, lebo sú zalamované v sadzobnom systéme TeX (čítaj tech). Môžete si napríklad všimnúť, že každý odsek textu je pekne zarovnaný k obidvom okrajom. Tento efekt sa dosiahne tak, že sa v každom riadku zvlášť vhodne zvolí veľkosť medzery medzi slovami. Všetky medzislovné medzery v rámci jedného riadka sú vždy rovnaké, ale v rôznych riadkoch často budú rôzne.

Samozrejme, keby sme mali v riadku primálo slov a medzi nimi obrovské medzery, vyzeralo by to zle. A keby sme sa do riadka snažili natlačiť viac slov ako sa tam zmestí, vyzeralo by to ešte horšie. Program vykonávajúci zalamovanie textu musí nájsť také rozdelenie slov do riadkov, ktoré bude vyzerať čo najlepšie.

Pri skutočnom zalamovaní je to celé, samozrejme, o niečo zložitejšie – môžeme napríklad rozdeliť niektoré slová na konci riadka, či prípadne zohľadniť to, že sa nepatrí nechávať na konci riadka predložky. V našej súťažnej úlohe však takéto detaily zanedbáme a budeme sa zaoberať najjednoduchšou možnou verziou.

Súťažná úloha

Strana má šírku 60 znakov. Každý znak má šírku 1 (arbitrárne). Medzislovné medzery môžu mať ľubovoľnú (nie nevyhnutne celočíselnú) šírku, avšak vždy to bude aspoň 1. V každom riadku, okrem posledného, musia byť aspoň dve slová.

Optimálna dĺžka medzery je 1. Túto dĺžku vždy použijeme v poslednom riadku. Pre každý iný riadok spočítame dĺžku medzier v ňom tak, že voľné miesto rovnomerne prerozdelíme. Formálne pre veľkosť medzier v riadku platí:

		60 − počet písmen v riadku
veľkosť medzery	=		.
		počet slov v riadku − 1

Škaredosť medzery je štvorec jej odchýlky od 1. Formálne teda škaredosť riadka vypočítame takto:

škaredosť riadka = (počet medzier v riadku) · (šírka medzery − 1)².

Všimnite si, že škaredosť posledného riadka je vždy 0.

Celková škaredosť riešenia je súčtom škaredosti jednotlivých riadkov.

Formát vstupu a výstupu

Na vstupe je postupnosť slov oddelených medzerami a koncami riadkov. Každé slovo je tvorené len malými a veľkými písmenami anglickej abecedy.

Na výstupe vypíšte tú istú postupnosť slov v tom istom poradí. Výstup sa môže od vstupu líšiť len rozdelením slov do riadkov. Každý riadok výstupu musí mať nanajvýš 60 znakov vrátane medzier. V každom riadku výstupu, okrem posledného, musia byť aspoň dve slová. V rámci každého riadka oddeľte dve po sebe idúce slová jednou medzerou. Za posledným slovom v riadku medzeru nevypisujte.

Hodnotenie

Je 10 testovacích vstupov, za každý môžete získať nanajvýš 1 bod. Body môžete získať len za testovacie vstupy, na ktorých vaše riešenie v časovom limite skončí a vypíše korektný výstup.

Počet bodov, ktoré získate za konkrétny vstup, vypočítame nasledujúcim vzorcom:

1 + škaredosť optimálneho riešenia

1 + škaredosť vášho riešenia

Príklad

vstup

Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi sed ullamcorper laoreet nisl Nunc tincidunt felis sed purus tristique a venenatis leo auctor Nam vel ultrices enim nec mattis erat Vestibulum vestibulum urna quis convallis accumsan sapien tortor aliquet massa a mattis ipsum lorem eget tellus Praesent sollicitudinidorcivenenatis pulvinar Aliquam vitae ullamcorper diam

optimálny výstup

Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi sed ullamcorpe
laoreet nisl Nunc tincidunt felis sed purus tristique a venenatis leo auctor
Nam vel ultrices enim nec mattis erat Vestibulum vestibulum urna quis
convallis accumsan sapien tortor aliquet massa a mattis ipsum lorem eget
tellus Praesent sollicitudinidorcivenenatis pulvinar Aliquam vitae
ullamcorper diam

V prvom riadku výstupu je 8 medzier, každá z nich má dĺžku 1,0.

V druhom riadku je 8 medzier, každá s dĺžkou 1,125.

Tretí má 8 medzier s dĺžkou 1,75.

Vo štvrtom je pre zmenu 7 medzier a tie majú dĺžku 1,429.

V piatom riadku je opäť 8 medzier, tento raz s dĺžkou 1,375.

V predposlednom, šiestom riadku sú len 4 medzery, každá s dĺžkou 1,75.

V poslednom, siedmom riadku sú 3 medzery. Tie budú mať optimálnu dĺžku 1.

Celková škaredosť je teda 8 · 0,000² + 8 · 0,125² + 8 · 0,750² + 7 · 0,429² + 8 · 0,375² + 4 · 0,750² ≈ 9,286.

iný výstup

Lorem ipsum dolor sit amet consectetur adipiscing elit Morbi
sed ullamcorper laoreet nisl Nunc tincidunt felis sed purus
tristique a venenatis leo auctor Nam vel ultrices enim nec
mattis erat Vestibulum vestibulum urna quis convallis
accumsan sapien tortor aliquet massa a mattis ipsum lorem
eget tellus Praesent sollicitudinidorcivenenatis pulvinar
Aliquam vitae ullamcorper diam

Toto je iný korektný výstup zodpovedajúci tomu istému vstupu. Jeho celková škaredosť je 12,111. (Riadky majú postupne 8, 8, 9, 6, 8, 4 a 3 medzery. Ich dĺžky sú postupne: 1,000, 1,125, 1,222, 2,167, 1,375, 1,750 a 1,000.)

Toto riešenie by získalo (1 + 9,286) / (1 + 12,111) ≈ 0,785 bodu. Ak by váš program rovnako dobre vyriešil všetkých desať testovacích vstupov, získal by za celú úlohu 7 bodov.

Veľkosť testovacích vstupov

Každý riadok vstupu má nanajvýš 200 znakov.
Každé slovo na vstupe má nanajvýš 29 znakov (takže sa ľubovoľné dve slová zmestia do riadka výstupu).
Celý vstup má dokopy nanajvýš 100 000 slov.
V testovacích vstupoch 1, 2 a 3 platí, že vstup má nanajvýš 50 slov a optimálny výstup nanajvýš 5 riadkov. V testovacích vstupoch 4, 5, 6 a 7 platí, že vstup má nanajvýš 1 000 slov.

Riešenie (vzorové)

Prvý pokus

Najprv si potrebujeme uvedomiť, že jediná podstatná vec na vstupe sú jednotlivé slová a ich počet. Riadkovanie môžeme ignorovať. Dokonca ak by sme riešenie nemuseli vypisovať, stačilo by si pamätať len dĺžky jednotlivých slov. Tu sa dostávame k prvému problému. Pravdepodobne budeme niekde v riešení potrebovať rýchlo zisťovať počty písmen v i za sebou idúcich slovách. Na to nám poslúžia prefixové súčty. Vyrobíme si tabuľku, ktorá bude mať na i‑tej pozícií počet písmen v prvých i slovách (pre i od 0 po n, kde n je celkový počet slov). Potom, ak chceme zistiť počet písmen od i‑teho do j‑teho slova, tak sa len pozrieme na hodnotu prefix[j] − prefix[i − 1]. Toto vieme vypočítať vopred v čase O(n) s pamäťovou zložitosťou O(n), čo nám riešenie nemôže pokaziť, pretože je to zároveň časová a pamäťová zložitosť potrebná na načítanie vstupu.

Teraz sa podrobnejšie pozrieme na limity. Vidíme, že 3 body vieme získať aj za celkom pomalé riešenie. Môžeme teda skúsiť vymyslieť riešenie hrubou silou („brute‑force“ riešenie). Napríklad vyskúšať všetky možnosti na zlomy riadkov. Keďže máme zaručené, že optimálne riešenie má najviac k = 5 riadkov a na vstupe je maximálne n = 50 slov, mohli by sme teda stihnúť vyskúšať všetky možnosti, medzi ktoré slová dáme nové riadky (tie budú najviac 4). Týchto možností je približne \(\binom{49}{4}\) = 211 876. Každú musíme však otestovať, čo nám zaberie asi 50 operácií a v súčte (súčine) dostaneme približne 10 000 000 operácií, čo sa ešte stále do časového limitu zmestí. Časová zložitosť takéhoto riešenia je vo všeobecnosti \(O\left(n \binom{n-1}{k-1}\right)\) . Pamäťová značne závisí od implementácie, obzvlášť od toho ako prezeráme všetky možnosti. Bude to približne O(n).

Pažravé riešenie

Čo tak úlohu riešiť pažravo? Budeme postupne brať slová a kým sa zmestia do jedného riadka, tak ich tam budeme dávať. Čím plnší riadok, tým menšia škaredosť.

Takýto postup síce zväčša vyrobí dobré riešenie, nebude však nevyhnutne optimálne. Prečo to nebude fungovať? Ak by sme mali napríklad 31 slov s dĺžkou 1 a potom dve s dĺžkou 29, tak vznikne nasledujúca „šarapata“: V prvom riadku budeme mať 30 jednopísmenových slov a škaredosť tohoto riadka bude 0,034. V druhom budeme mať jedno jednopísmenové a jedno 29‑písmenové. Tento má škaredosť 841. No a posledný má 0. Ak by sme však čo i len jedno slovo z prvého riadka dali do druhého, tak v prvom riadku by sme získali škaredosť 0,32 a v druhom 364,5, čo je dohromady oveľa menej. Pažravý (greedy) prístup teda nefunguje. (Ak však nevieme nič lepšie, tak sa ho stále oplatí implementovať a získať za neho celkom slušné množstvo bodov. Obzvlášť v kombinácii s hrubou silou pre malé vstupy.)

Hlbšie zamyslenie sa

Prečo vlastne pažravé riešenie nefungovalo? Preto, lebo sa nám môže oplatiť zobrať do riadka aj menej slov ako sa tam práve zmestí. To, koľko presne však závisí od toho ako dobre vieme zalomiť zvyšok.

Povedzme, že chceme zalomiť n slov. Máme dve možnosti: buď sa všetky zmestia do jedného riadka (a teda majú škaredosť 0), alebo nie. Prvý prípad je jednoduchý – nič lepšie ako dať ich do jedného riadka nevymyslíme. V tom druhom prípade sa musíme rozhodnúť, koľko slov vložíme do prvého riadka a koľko vložíme neskôr (do ostatných riadkov).

Ak by sme to prepočítali na menšie n‑ká, tak vypočítať naše aktuálne n je jednoduché. Stačí prejsť všetky možnosti m od 1 po n slov na prvom riadku, pozrieť sa, či je tento riadok validný (má aspoň dve slová a zmestí sa do 60 znakov), vypočítať jeho škaredosť, pozrieť sa do tabuľky na akú najmenšiu škaredosť sa dá zalomiť zvyšných n − m slov a vybrať to najlepšie m‑ko. Musíme si dať pozor iba na to, aby sme škaredosť počítali rozumne a teda s pomocou prefixových (respektíve sufixových) súm. Na záver už len podľa zapamätaných údajov spätne zostrojíme jedno optimálne riešenie.

Formálne si toto riešenie môžeme sformulovať takto:

Slová na vstupe očíslujeme od 1 po n. Nech s_i je najmenšia možná škaredosť, ktorú vieme dosiahnuť keď máme slová s číslami i až n zalomiť do ľubovoľného počtu celých riadkov. Budeme postupne počítať hodnoty s_n až s₁ (čo je hľadaná celková optimálna cena). Pre každú z týchto hodnôt sme odvodili tento vzťah:

s_i	=	min	(škaredosť riadka obsahujúceho slová i až i + m − 1) + s_{i + m}
		^{1 ≤ m ≤ n − i + 1}

(pričom ak sa dotknuté slová do riadka nezmestia, tak považujeme škaredosť za nekonečnú).

Toto riešenie má časovú zložitosť O(n²), lebo pre každý počet slov O(n) sa potrebuje pozrieť na všetky možnosti toho, koľko slov je v prvom riadku O(n). Keďže si pamätáme tabuľku s výsledkami pre jednotlivé n‑ká, tak pamäťová zložitosť bude O(n).

Posledné zlepšenie

Koľko slov je vôbec rozumné skúšať vložiť do jedného riadka? Toľko, koľko sa tam zmestí. Keďže má každé slovo dĺžku aspoň 1, tak viac ako 30 slov sa do riadka nikdy nezmestí. To znamená, že pre každé n sa stačí pozrieť len na 30 (konštantne veľa) možností pre počet slov v prvom riadku. Tak sa rázom dostávame na časovú zložitosť O(n) a so správne napísaným kódom aj na plný bodový zisk.

Výpis vzorovej implementácie v jazyku C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define For(Q, W) for (int Q = 0; Q < W; ++Q)

int main()
{
	vector<string> text;

	// Načítame text – slová zo štandardného vstupu
	// a vložíme ich do zoznamu.
	{
		string slovo;
		while (cin >> slovo) text.push_back(slovo);
	}

	int pocetSlov = text.size();

	// Prevrátime poradie slov, lebo budeme počítať od konca.
	reverse(text.begin(), text.end());

	vector<int> prefixSum(1, 0);

	For(i, pocetSlov)
	{
		// Vypočítame prefixové sumy dĺžok slov.
		prefixSum.push_back(prefixSum[i] + text[i].size());
	}

	vector<int> vRiadku(pocetSlov);

	// Na začiatku máme veľmi veľkú škaredosť.
	vector<double> skaredost (pocetSlov + 1, 99999999);

	For(i, pocetSlov)
	{
		// Chceme zalomiť i + 1 slov.
		if (i - 1 + prefixSum[i + 1] <= 60)
		{
			// Ak sa všetky slová zmestia do riadka, tak je to posledný
			// riadok a škaredosť je rovná 0.
			skaredost[i + 1] = 0.0;

			// V tomto riadku je i + 1 slov.
			vRiadku[i] = i + 1;
		}
		else
		{
			// Inak sa rozhodneme, koľko slov dáme do tohoto riadka,
			// pričom musia byť najmenej dve a najviac 30. Najviac 30,
			// pretože každé slovo má aspoň jedno písmeno, čiže viac
			// ako 30 slov by malo viac ako 30 písmen s viac ako 29
			// medzerami medzi nimi, čo by bolo viac ako 60 znakov.
			for (int j = 2; j <= 30 && i - j >= 0; ++j)
			{
				// Ak sa nezmestia do jedného riadka, tak nemá význam
				// skúšať vložiť viac slov.
				if (prefixSum[i + 1] - prefixSum[i - j + 1] + j - 1 > 60)
					break;

				// Škaredosť toho, čo nedáme do prvého riadka.
				double nova = skaredost[i - j + 1];

				// Vypočítame škaredosť pre j slov v tomto riadku.
				double medzera = (60.0 - prefixSum[i + 1] +
					prefixSum[i - j + 1]) / (j - 1.0);

				nova += (medzera - 1) * (medzera - 1) * (j - 1);

				if (skaredost[i + 1] > nova)
				{
					// Ak to malo význam, tak aktualizujeme škaredosť…
					skaredost[i + 1] = nova;

					// … a zapamätáme si počet slov na riadku.
					vRiadku[i] = j;
				}
			}
		}
	}

	// Už len správne vypíšeme text zo vstupu.
	for (int i = pocetSlov - 1; i >= 0; --i)
	{
		cout << text[i];

		// Jedno sme už vypísali.
		int vypis = vRiadku[i] - 1;

		For(j, vypis)
		{
			--i;
			cout << " " << text[i];
		}

		cout << endl;
	}
}

Konverzia vzorovej implementácie do jazyka Java s použitím programovacieho rámca GRobot

import knižnica.*;

public class Medzery extends GRobot
{
	private Medzery()
	{
		Zoznam<String> text = new Zoznam<>();

		// Načítame text – slová zo štandardného vstupu
		// a vložíme ich do zoznamu.
		/*{
			// Upozornenie! Tento spôsob vyžaduje, aby bol štandardný
			// vstup konečný, napríklad presmerovaný na čítanie zo súboru:
			//
			// 	java -cp c:\_jEdit\GRobot.jar;. Medzery < lorem-ipsum.txt
			//
			// (Inak sa aplikácia ocitne v nekonečnom cykle.)
			String slovo;
			// while (cin >> slovo) text.push_back(slovo);
			while (null != (slovo = Svet.čakajNaVstup())) text.pridaj(slovo);
		}*/

		// Prečítame text – slová zo súboru a vložíme ich do zoznamu.
		try
		{
			súbor.otvorNaČítanie("lorem-ipsum.txt");
			String slovo;
			while (null != (slovo = súbor.čítajRiadok())) text.pridaj(slovo);

			// Vypíšeme prečítané slová.
			Svet.vypíšRiadok(text);
			Svet.vypíšRiadok();
		}
		catch (Throwable t)
		{
			t.printStackTrace();
		}

		int početSlov = text.dĺžka();

		// Prevrátime poradie slov, lebo budeme počítať od konca.
		// reverse(text.begin(), text.end());
		for (int i = (početSlov / 2) - (0 == početSlov % 2 ? 1 : 0);
			i >= 0; --i) text.vymeň(i, početSlov - i - 1);

		Zoznam<Integer> prefixováSuma = new Zoznam<>();
		prefixováSuma.pridaj(0);
		for (int i = 0; i < početSlov; ++i)
			// Vypočítame prefixové sumy dĺžok slov.
			prefixováSuma.pridaj(prefixováSuma.daj(i) + text.daj(i).length());

		Zoznam<Integer> vRiadku = new Zoznam<>();
		for (int i = 0; i < početSlov; ++i) vRiadku.pridaj(0);

		Zoznam<Double> škaredosť = new Zoznam<>();
		for (int i = 0; i < početSlov + 1; ++i)
			// Na začiatku máme veľmi veľkú škaredosť.
			škaredosť.pridaj(99_999_999.0);

		for (int i = 0; i < početSlov; ++i)
		{
			// Chceme zalomiť i + 1 slov.
			if (i - 1 + prefixováSuma.daj(i + 1) <= 60)
			{
				// Ak sa všetky slová zmestia do riadka, tak je to posledný
				// riadok a škaredosť je rovná 0.
				škaredosť.prepíš(i + 1,  0.0);

				// V tomto riadku je i + 1 slov.
				vRiadku.prepíš(i, i + 1);
			}
			else
			{
				// Inak sa rozhodneme, koľko slov dáme do tohoto riadka,
				// pričom musia byť najmenej dve a najviac 30. Najviac 30,
				// pretože každé slovo má aspoň jedno písmeno, čiže viac
				// ako 30 slov by malo viac ako 30 písmen s viac ako 29
				// medzerami medzi nimi, čo by bolo viac ako 60 znakov.

				// (Poznámka: Cyklus sa dá významne optimalizovať. Okrem
				// jediného prípadu všade pracujeme s hodnotou j - 1 (resp.
				// -j + 1, čo je po algebrickej úprave to isté ako -(j - 1)),
				// takže môžeme cyklus zostaviť tak, aby sa hodnota j menila
				// v rozsahu posunutom o -1 a podľa toho prepísať všetky
				// výskyty j.)
				//
				// (Poznámka: V podmienke i - j >= 0 je pravdepodobne „chyba,“
				// resp. je „prehnane bezpečná,“ čo mierne prekáža pri
				// optimalizácii. V rámci procesu optimalizácie opísaného
				// vyššie by pre nás bolo výhodné, keby podmienka pred
				// optimalizáciou znela: i - j + 1 >= 0 (čo bol pravdepodobne
				// pôvodný zámer, ale autor sa zrejme chcel „zbaviť“ + 1).
				// Potom by sa po optimalizácii dala podmienka tiež zapísať
				// v tvare: i - j >= 0.)
				for (int j = 2; j <= 30 && i - j >= 0; ++j)
				{
					// Ak sa nezmestia do jedného riadka, tak nemá význam
					// skúšať vložiť viac slov.
					if (prefixováSuma.daj(i + 1) -
						prefixováSuma.daj(i - j + 1) +
						j - 1 > 60) break;

					// Škaredosť toho, čo nedáme do prvého riadka.
					double nová = škaredosť.daj(i - j + 1);

					// Vypočítame škaredosť pre j slov v tomto riadku.
					double medzera = (60.0 - prefixováSuma.daj(i + 1) +
						prefixováSuma.daj(i - j + 1)) / (j - 1.0);
					nová += (medzera - 1) * (medzera - 1) * (j - 1);

					if (škaredosť.daj(i + 1) > nová)
					{
						// Ak to malo význam, tak aktualizujeme škaredosť…
						škaredosť.prepíš(i + 1, nová);

						// … a zapamätáme si počet slov na riadku.
						vRiadku.prepíš(i, j);
					}
				}
			}
		}

		/**/
		// Už len správne vypíšeme text zo vstupu.
		Svet.vypíšRiadok();
		for (int i = početSlov - 1; i >= 0; --i)
		{
			// cout << text[i];
			Svet.vypíš(text.daj(i));

			// Jedno sme už vypísali.
			int vypis = vRiadku.daj(i) - 1;

			for (int j = 0; j < vypis; ++j)
			{
				--i;
				// cout << " " << text[i];
				Svet.vypíš(' ', text.daj(i));
			}

			// cout << endl;
			Svet.vypíšRiadok();
		}
		/**/
	}

	public static void main(String[] args)
	{
		// Svet.použiKonfiguráciu("Medzery.cfg");
		new Medzery();
		Svet.zbaľ();
	}
}

Vzorový vstupný súbor

lorem‑ipsum.txt 432,00 B (432,00 B), 22. 9. 2020