3. Zved Tigrík vzorové riešenie

15 10
DZFDFZDFDDDDDDF

82

6 4
YJSNPI

4

Na začiatok jednoduchší prípad

Uvažujme na začiatok jednoduchšiu úlohu: čo ak by \(k\) bolo rovné \(n\)? Vtedy vieme, že Tigrík stihne navštíviť všetky svoje zdroje a treba len spočítať, koľko za tento deň zarobí.

Na to potrebujeme pre každý typ informácie zistiť, koľko zdrojov ju má. Inými slovami, potrebujeme spočítať počet výskytov každého písmena. Toto najľahšie spravíme tak, že pre každé písmeno budeme mať jedno počítadlo. Najlepšie je uložiť si tieto počítadlá do poľa veľkosti \(26\) – toľko je rôznych písmen v anglickej abecede.

Keď to už máme spočítané, tak si stačí uvedomiť, že ak máme \(x\) informácií rovnakého typu (teda \(x\) výskytov konkrétneho písmena), tak každé z nich má cenu \(x\), a dokopy za toto písmeno dostaneme \(x\times x = x^2\) peňazí.

Takže ak sme si spočítali počty výskytov jednotlivých písmen, stačí nám sčítať ich druhé mocniny a máme Tigríkov zárobok.

var n,k,sucet,i:int64;
	c : char;
	a : array[1..26] of int64;
begin
	readln(n,k);
	for i:=1 to 26 do a[i] := 0;
	for i:=1 to n do begin
		read(c);
		inc(a[ord(c)-ord('A')+1]);
	end;
	sucet := 0;
	for i:=1 to 26 do begin
		sucet := sucet + a[i]*a[i]; 
	end;
	writeln(sucet);
end.

Pôvodný problém

Teraz sa vráťme k všeobecnému zadaniu, kedy môže byť \(k<n\). Vtedy musíme zistiť, ktoré zdroje sa Tigríkovi oplatí navštíviť – inými slovami, ktorých \(k\) písmen máme zobrať, aby sme dokopy dostali čo najväčší zárobok.

Myslím, že každý z vás si všimol, že čím viac máme rovnakých písmen, tým viac Tigrík zarobí. Intuícia nám teda napovedá, že Tigrík by mal preferovať tie písmená, ktorých je na vstupe veľa.

Nádejne teda vyzerá nasledovný postup: Tigrík si nájde to písmeno, ktorého je na vstupe najviac, a zoberie čo najviac jeho výskytov. Potom spraví to isté s druhým najčastejším, tretím najčastejším, a tak ďalej, až kým už nemôže zobrať žiadne ďalšie písmeno.

Zamyslime sa najskôr, ako by sme takéto riešenie implementovali. Rovnako ako v prvej časti začneme tým, že si spočítame počty výskytov jednotlivých písmen. Teraz by sme ich potrebovali usporiadať podľa počtu výskytov. Keďže máme len 26 rôznych písmen, je úplne jedno, aký algoritmus na to použijeme. Môžeme použiť štandardné knižničné triedenie (napr. sort() v C++) alebo implementovať nejaké vlastné.

Po usporiadaní počtov výskytov už odpoveď vypočítame jednoduchým cyklom (všimnite si, že sa musíme zakaždým pozrieť, či môžeme zobrať všetky písmená daného typu, alebo ich je priveľa a len naplníme našu kapacitu):

{ pred týmto kusom programu usporiadame pole 'a' od najväčšieho po najmenšie }
sucet := 0;
i := 1;
while (k > 0) do begin
	if (k < a[i]) then kolko := k
	else kolko := a[i];
	sucet := sucet + kolko*kolko;
	k := k - kolko;
	inc(i);
end;
writeln(sucet);

Asi najjednoduchšie na implementáciu je triedenie max-sort. Priamo počas neho vieme aj počítať riešenie. Jednoducho postupne 26-krát zopakujeme nasledovný postup: “Nájdi najčastejšie sa vyskytujúce ešte nespracované písmeno a zober z neho najviac ako sa dá.”

Dôkaz správnosti

Teraz nás ale čaká tá ťažšia časť tohto vzorového riešenia. Je síce pekné, že sme si vymysleli jednoduché pažravé¹ riešenie, ktoré sa nám ľahko implementovalo, čo nám ale zaručí, že toto riešenie je naozaj optimálne? Nemôže sa niekedy stať, že by iný spôsob výberu písmen viedol k väčšiemu celkovému zárobku?

Aby bolo naše riešenie úplné, musíme na tieto otázky vedieť odpovedať. Inými slovami, potrebujeme ešte dokázať správnosť nášho algoritmu.

Pomocné tvrdenie

Dokážeme si nasledovné tvrdenie: “Nič nepokazíme, keď z najčastejšieho písmena zoberieme najviac kusov, ktoré môžeme zobrať.” Inými slovami, tvrdíme, že pre ľubovoľný vstup existuje medzi optimálnymi riešeniami také riešenie, v ktorom Tigrík zoberie najväčší možný počet výskytov najčastejšieho písmena.

Dôkaz: Nech \(v\) je počet výskytov najčastejšieho písmena a nech \(z\) je celkový počet písmen, ktoré ešte môžeme zobrať. Dôkaz nášho tvrdenia si rozdelíme na dva prípady.

Prípad prvý: \(v > z\), teda nemôžeme zobrať všetky výskyty najčastejšieho písmena.

V ľubovoľnom riešení by sme zobrali nejakých \(z\) písmen. Keďže každého z nich by sme zobrali najviac \(z\) kusov, bol by celkový zisk najviac \(z^2\). Viac ako \(z^2\) sa zjavne dosiahnuť nedá. No a pri našej stratégii zoberieme \(z\) kusov najčastejšieho písmena a dostaneme tak zisk presne \(z^2\), čo je zjavne optimálne.

Prípad druhý: \(v \leq z\), teda môžeme zobrať všetky výskyty nášho písmena a možno ešte aj niečo navyše.

Chceme teraz dokázať, že existuje optimálne riešenie, v ktorom Tigrík vezme všetkých \(v\) kusov tohto písmena. Toto dokážeme tak, že ukážeme, že k ľubovoľnému riešeniu, v ktorom zoberie menej ako \(v\) kusov, existuje aspoň tak isto dobré riešenie, v ktorom ich vezme viac.

Uvažujme teda ľubovoľné riešenie, v ktorom Tigrík nezobral \(v\) kusov nášho písmena, ale len \(w\), pričom \(w<v\).

• Podprípad 2a: Nejakého iného písmena zobral Tigrík \(x > w\) kusov.

  V tomto prípade vieme dostať rovnako dobré riešenie tak, že zoberieme \(x\) kusov nášho a \(w\) kusov toho druhého písmena. (Touto zmenou sme zväčšili počet zobratých kusov nášho písmena.)

• Podprípad 2b: Každého iného písmena zobral Tigrík \(w\) alebo menej kusov.

  Za každé písmeno teraz Tigrík dostane \(w\) alebo menej bodov. V tejto situácii vieme vyrobiť ostro lepšie riešenie tak, že zahodíme jedno iné písmeno a namiesto neho zoberieme jedno ďalšie naše. Ak tých iných písmen bolo doteraz \(x\) (pričom \(x \leq w\)), tak zisk klesol o \(2x-1\) za odstránené písmeno, ale stúpol o \(2w+1\) za písmeno pridané, a teda v súčte aspoň o 2 stúpol. Oplatí sa nám teda vymieňať písmená za tie, ktoré sa tam vyskytujú častejšie.

A tým je dôkaz hotový.

Záver dôkazu správnosti

Z práve dokázaného pomocného tvrdenia už priamočiaro vyplýva dôkaz správnosti nášho algoritmu. Na začiatku vieme, že existuje optimálne riešenie, v ktorom zoberieme najväčší možný počet výskytov najčastejšieho písmena, tak to urobíme. Na toto písmeno môžeme teraz šťastne zabudnúť. Ostala nám opäť taká istá situácia: máme na výber nejaké písmená a máme nejakú voľnú kapacitu. Teraz môžeme znovu použiť tú istú argumentáciu – z toho písmena, ktoré je teraz najčastejšie, určite môžeme zobrať najviac ako sa dá. A tak ďalej.

Zložitosti

Načítanie vstupu má časovú zložitosť lineárnu od \(n\), čo zapisujeme \(O(n)\). Počas toho vieme aj postupne zvyšovať počítadlá písmen. Celý zvyšok riešenia už má konštantnú časovú zložitosť – rôznych písmen je len 26, a teda na ich usporiadanie podľa počtu výskytov aj na ich následné spracovanie nám stačí konštantný počet krokov, nezávislý od veľkosti vstupu. Výsledná časová zložitosť je teda \(O(n)\).

Pamäťová zložitosť je \(O(1)\), teda konštantná. Vôbec si totiž nemusíme držať v pamäti celý vstup, stačí si pamätať iba 26 počítadiel a nejaké pomocné premenné.

var n,k,sucet,i,j,kolko,pozMax,pomocna:int64;
	c : char;
	a : array[1..26] of int64;
begin
	readln(n,k);
	for i:=1 to 26 do a[i] := 0;
	for i:=1 to n do begin
		read(c);
		inc(a[ord(c)-ord('A')+1]);
	end;

	//triedenie max-sort, najde maximum a da ho na zaciatok, potom najde
	//maximum zo zvysnych a da ho na druhe miesto ...
	for j := 1 to 25 do begin
		pozMax := j;
	    for i := j+1 to 26 do begin
			if a[i] > a[pozMax] then pozMax := i;
	    end;
	    if pozMax <> j then begin
			pomocna := a[pozMax];
			a[pozMax] := a[j];
			a[j] := pomocna;
	    end;
	end;

	sucet := 0;
	i := 1;
	while (k > 0) do begin
		if (k < a[i]) then kolko := k
		else kolko := a[i];
		sucet := sucet + kolko*kolko;
		k := k - kolko;
		inc(i);
	end;
	writeln(sucet);
end.