3. Asymetrický bambus vzorové riešenie

5
3 2 0 2 3

4
0 4 1 3

3
1 2 0

3
1 0 2

Na začiatok si uvedomme čo po nás vlastne úloha žiada. Máme vytvoriť vežu z kusov bambusu, ktorá nespadne. Každý bambus má 1m a vie uniesť nad sebou \(n\)m bambusu. Čo to pre nás teda znamená? Máme rôzne čísla, ktoré chceme dať do nejakého poradia, aby za číslom \(k\) nasledovalo najviac \(k\) čísel a chceme aby bol tento rad čísel najdlhší možný zo zadanej množiny. Od teraz budeme hovoriť o takejto verzii úlohy.

Postupné stavanie radu

Predpokladajme, že už máme nejaký rad hotový a chceme k nemu nájsť ďalšie číslo. Očividne chceme použiť najväčšie dostupné číslo, aby sme vedeli aj naďalej rad rozširovať čo najviac. Použiť tam menšie číslo by znamenalo, že by sme zaň mohli pridať iba menej čísel. Aj keby sme toto väčšie číslo využili neskôr, nepomohli by sme si, lebo menšie číslo, ktoré sme využili skôr zaručene vynúti nižšiu maximálnu dĺžku radu ako by sme mohli dosiahnuť pomocou tohto väčšieho čísla.
V každom bode si pre aktuálny rad potrebujeme pamätať ešte jednu kľúčovú vlastnosť a tou je, aké máme aktuálne obmedzenie na jeho dĺžku. To si môžme pamätať ako počet prvkov, ktoré ešte môžme pridať (označíme ho \(l\)). Tento počet bude začínať na \(\infty\) a bude sa postupne meniť podľa toho, aké čísla pridávame. Ak pridáme číslo \(k\), tak \(l\) nového radu bude menšie číslo z \(l-1\) (predchádzajúce \(l\), mínus nové číslo) a \(k\) (za číslo \(k\) môže byť max. \(k\) čísel).
Ak sa dostaneme do situácie kde \(l=0\), tak vieme, že už nemôžme pridať žiadne ďalšie číslo a môžme sa zastaviť lebo už máme najdlhší rad.

Týmto sme opísali iteratívne riešenie, ktoré nám postupne postavý správny rad v čase \(O(n^2)\) (rad má najviac \(n\) prvkov a pre každý z nich musíme nájsť najvyššie nevyužité číslo, čo nám zaberie \(O(n)\) času). Toto ale vieme ľahko zrýchliť na \(O(n\log n)\), ak využijeme haldu.

Zjednodušenie

Čo si môžeme na vyššie popísanom riešení všimnúť je, že v podstate jediné čo robíme je, že vždy berieme najväčšie ešte nevyužité číslo. To vieme veľmi ľahko urobiť, ak si rad hneď na začiatku zoradíme zostupne. Potom už stačí len brať prvky z jeho začiatku a máme zaistené, že vždy berieme najväčšie doteraz nevyužité číslo. Samozrejme, nesmieme zabudnúť na obmedzenie \(l\), ale to už vieme ľahko skontrolovať pri lineárnom prechádzaní radu.

Takéto riešenie už má časovú zložitosť \(O(n\log n)\), nakoľko zoradenie radu nám zaberie \(O(n\log n)\) času a potom už len lineárne prechádzame rad a kontrolujeme obmedzenie \(l\).

Implementácia

Najzložitejšia časť riešenia je vypísanie radu, nakoľko nevypisujeme prvky, ale ich index z pôvodného radu. To vieme ľahko urobiť, ak si na začiatku prvky zapamätáme ako dvojicu čísel namiesto jedného. Prvým číslom bude samotný prvok a druhým jeho index. Potom môžeme vo väčšine jazykov použiť zabudovanú funkciu na zoradenie. Dvojice zoradí primárne podľa prvého prvku (t.j. to čo chceme) a až v prípade jeho rovnosti podľa druhého prvku (to nás už netrápi). V Pythone sa na dvojice dá využiť tuple a zabudovaná funkcia sort, v C++ by to bol pair a sort.

V Pythone by sme mohli riešenie napísať nasledovne:

n = int(input())
# kadzy prvok si naformatujeme ako (prvok, index)
k = [(int(x), i) for i, x in enumerate(input().split())]

# zoradime prvky zostupne
k.sort(reverse=True)

# pouzijeme -1 ako nekonecno
l = -1
i = 0
while i < n:
	if l == 0:
		# uz nemozme pridat ziadne dalsie cislo
		break
	if i == 0:
		# pridame prvy prvok, l musi byt k
		l = k[i][0]
	else:
		# pridame dalsi prvok, l je minimum z l-1 a k
		l = min(l-1, k[i][0])
	i += 1

# vypiseme pocet prvkov, ktore ma rad
print(i)
for j in range(i):
	# vypiseme indexy prvkov
	print(k[j][1], end='')
	if j < i-1:
		print(' ', end='')
print()