Zadanie
POZOR: táto úloha má neštandardný spôsob hodnotenia. Viac sa dozviete v časti Hodnotenie.
Pán Dirichlet je veľkochovateľ poštových holubov. Vo svojich početných holubníkoch chová obrovské množstvo holubov, z ktorých občas niektoré predá malochovateľom.
Dávid sa chce stať malochovateľom poštových holubov. Na záhrade si postavil celý rad holubníkov, ktoré (v duchu najlepších chovateľských tradícií) očísloval číslami \(1, 2, 3, \dots\). Následne si u pána Dirichleta objednal \(n\) holubov.
Pán Dirichlet teda Dávidovi pekne po jednom poslal1 \(n\) holubov.
Holuby sú teraz na ceste a Dávid sa pripravuje na ich prijatie. Plán je jednoduchý: holuby budú po jednom prilietať (v poradí, v akom boli poslané, keďže, ako je všeobecne známe, slušné poštové holuby sa navzájom nepredbiehajú) a vždy, keď nejaký holub priletí, Dávid ho strčí do niektorého z holubníkov. To však nemôže robiť len tak halabala. Sťahovanie sa z jedného holubníka do druhého je totiž pre takého holuba veľká udalosť a ak sa to urobí zle, holub si nikdy na svoj nový domov nezvykne, začne chradnúť a predčasne umrie. To, či sa holub v novom domove dobre aklimatizuje, sa riadi nasledovnými pravidlami:
Každý holub má nejakú extroverciu. Extrovercia holuba je nezáporné celé číslo, ktoré je pri introvertných holuboch nízke a pri extrovertných holuboch vysoké.
Keď holuba s extroverciou \(e\) nasťahujeme do nového holubníka, v ktorom už býva presne \(e\) iných holubov, náš holub sa do tejto spoločnosti bez problémov začlení a rýchlo (hneď) si na nový domov zvykne. Ak je však v holubníku iný počet holubov ako \(e\) (menej, alebo viac), náš holub sa v kolektíve necíti dobre a na nový domov si nikdy nezvykne.
Keď si už raz holub zvykne na svoj holubník (čo sa stane buď hneď po jeho príchode, alebo nikdy), nevadí mu, ak do tohto holubníka pridávame aj nové holuby.
Pán Dirichlet, ako dobrý chovateľ, pozná extrovercie všetkých svojich holubov a spolu s faktúrou poslal2 Dávidovi aj zoznam extrovercií odoslaných holubov, v poradí, v akom ich poslal. Dávid sa teraz na tento zoznam pozerá a snaží sa naplánovať, ako holuby napchať do holubníkov tak, aby sa všetky dobre aklimatizovali. Pomôžte mu!
Úloha
Na vstupe dostanete postupnosť \(n\) čísel \(e_1, e_2, \dots, e_n\) – extrovercie holubov v poradí, v akom budú prilietať. Nájdite takú postupnosť prirodzených čísel \(h_1, h_2, \dots, h_n\), že ak Dávid strčí prvého holuba do holubníka číslo \(h_1\), druhého do holubníka číslo \(h_2\), tretieho do \(h_3\) atď., všetky holuby si dobre zvyknú. Inými slovami, pre každé \(i \in \{1, 2, \dots, n\}\) musí platiť, že presne \(e_i\) spomedzi čísel \(h_1, h_2, \dots, h_{i-1}\) sa rovná číslu \(h_i\). Môžete predpokladať, že Dávid má aspoň \(n\) holubníkov a aspoň jedna vhodná postupnosť existuje (pán Dirichlet je dobrý chovateľ a neposlal by svoje holuby tak, aby boli niektoré z nich odsúdené na chradnutie).
Formát vstupu
V prvom riadku vstupu je celé číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)). V druhom riadku je \(n\) medzerami oddelených nezáporných celých čísel \(e_1, e_2, \dots, e_n\) – extrovercie holubov. Pre každé zmysluplné \(i\) platí \(0 \leq e_i \leq {n-1}\).
Formát výstupu
Vypíšte jeden riadok a v ňom \(n\) celých čísel oddelených medzerami – jednu vhodnú postupnosť \(h_1, h_2, \dots, h_n\). Pre každé zmysluplné \(i\) musí platiť \(1 \leq h_i \leq n\) (aj tak určite nebudete potrebovať viac ako \(n\) holubníkov). Ak je možných riešení viac, vypíšte ľubovoľné z nich.
Hodnotenie
V tejto úlohe budeme primárne hodnotiť pamäťovú zložitosť vášho algoritmu a až sekundárne časovú. Na časovú zložitosť budeme prihliadať iba tak, ako v iných úlohách prihliadame na pamäťovú (teda algoritmus s lepšou pamäťovou a horšou časovou zložitosťou považujeme za lepší, pokiaľ nie je jeho časová zložitosť absurdne veľká). Tomu zodpovedá aj pomerne voľný časový limit a veľmi malý pamäťový limit (najväčšie vstupy sa vám nezmestia do pamäte) v praktickom testovaní.
Pre jednotlivé vstupné sady platí:
číslo sady | 1 | 2 | 3, 4, 5 |
---|---|---|---|
maximálne \(n\) | 10 | 1000 | 1,000,000 |
V sade č. 3 navyše v každom vstupe platí, že existuje riešenie využívajúce nanajvýš \(1\,000\) holubníkov.
Príklad
Input:
4
0 0 0 0
Output:
1 2 3 4
Každý holub musí ísť do nového holubníka. Dobrým riešením je napríklad aj 4 3 2 1.
Input:
5
0 1 2 3 4
Output:
3 3 3 3 3
Všetky holuby musíme dať do rovnakého holubníka.
Input:
8
0 0 1 0 1 2 3 2
Output:
4 2 4 3 2 2 2 4
Jedno z mnohých možných riešení.
Vždy, keď Dávidovi priletí nejaký holub s extroverciou \(e\), musí ho Dávid nasťahovať do holubníka, v ktorom je presne \(e\) iných holubov. Niekedy sa môže stať, že Dávid má na výber viacero holubníkov s presne \(e\) holubmi.
Všimnime si, že všetky holubníky s \(e\) holubmi sa pre účely našej úlohy správajú úplne rovnako (do každého z nich môžeme strčiť holuba s extroverciou \(e\) a ak to urobíme, stane sa z neho holubník s \(e+1\) holubmi). To znamená, že vždy keď má Dávid na výber z viacerých holubníkov, môže si vybrať ľubovoľný z nich a určite tým nič nepokazí.
Priamočiare riešenie
Asi najpriamočiarejšie je celú situáciu simulovať. V jednom poli si budeme pre každý holubník pamätať, koľko je v ňom holubov. Vždy, keď priletí holub, nájdeme prvý holubník s vhodným počtom iných holubov a strčíme ho tam. Budeme si musieť pamätať \(n\) holubníkov (pre prípad, že by nám priletelo \(n\) holubov s extroverciou \(0\)), teda pamäťová zložitosť bude \(O(n)\). Hľadanie vhodného holubníka nám pri každom holubovi bude trvať v najhoršom prípade \(O(n)\), teda časová zložitosť bude \(O(n^2)\).
Šetrenie pamäťou
Ľahký spôsob, ako toto riešenie vylepšiť, je nepamätať si \(n\) holubníkov, ale len toľko, koľko potrebujeme. V najhoršom prípade to síce nepomôže (lebo v najhoršom prípade aj tak potrebujeme všetkých \(n\) holubníkov), ale vyrieši to tretiu sadu testovacích vstupov, kde máme sľúbené, že stačí použiť nanajvýš \(1\,000\) holubníkov.
Samozrejme, na začiatku nevieme, koľko holubníkov budeme potrebovať. Preto si nebudeme pamätať žiaden. Vždy, keď priletí holub s extroverciou \(0\), otvoríme mu nový holubník a začneme si pamätať počet holubov v ňom. Na tento účel sa veľmi hodí pole s možnosťou pridávania prvkov na koniec, napríklad vector
v C++, alebo ArrayList
v Jave.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> holubnik;
for(int i=0; i<n; i++)
{
int e;
scanf("%d", &e);
if(e == 0)
{
printf("%d", holubnik.size()+1);
holubnik.push_back(1);
}
else
{
for(int j=0; j<holubnik.size(); j++)
{
if(holubnik[j] == e)
{
printf("%d", j+1);
holubnik[j]++;
break;
}
}
}
if(i+1 < n) printf(" ");
else printf("\n");
}
return 0;
}
Rýchlejšie riešenie
V predošlom riešení sme každého nového holuba strkali do prvého vhodného holubníka. To okrem iného zaručuje, že počty holubov v jednotlivých holubníkoch tvorili v každom momente nerastúcu postupnosť. Teda nikdy sa nemohlo stať, že by v \(i\)-tom holubníku bolo menej holubov ako v \(i+1\)-vom.
V tomto riešení budeme holuby strkať do holubníkov rovnakým spôsobom, ale budeme si o holubníkoch pamätať inú informáciu. Konkrétne, pre každé číslo \(x\) od \(0\) po \(n-1\) si budeme pamätať číslo prvého holubníka obsahujúceho \(x\) holubov.
Trochu problém je s takými číslami \(x\), pre ktoré neexistuje holubník s presne \(x\) holubmi. Tento problém sa dá ošetriť rôznymi spôsobmi. Implementačne asi najjednoduchší z nich je pamätať si pre každé \(x\) číslo prvého holubníka, ktorý obsahuje \(x\) alebo menej holubov. Toto číslo má rozumnú hodnotu pre každé \(x\) z rozsahu \(0\) až \(n-1\) a ako sa ukáže, veľmi ľahko sa aktualizuje.
Na začiatku si teda budeme pamätať \(n\) jednotiek.
Vždy, keď priletí holub s nejakou extroverciou \(e\), pozrieme sa na prvý holubník obsahujúci \(e\) alebo menej holubov. Aspoň jeden holubník určite obsahuje presne \(e\) holubov (inak by sa holuby nedali dobre ubytovať). Počty holubov v holubníkoch tvoria nerastúcu postupnosť, teda prvý holubník s \(e\) alebo menej holubmi určite obsahuje presne \(e\) holubov. To znamená, že tam môžeme strčiť nového holuba. Následne si musíme aktualizovať naše informácie: číslo prvého holubníka obsahujúceho \(e\) alebo menej holubov sa nám zvýšilo o \(1\). Žiadne iné z čísel, ktoré si pamätáme, sa nezmenilo.
Takto vieme každého holuba spracovať v konštantnom čase. Časová zložitosť tohto riešenia je teda \(O(n)\), pamäťová je tiež \(O(n)\).
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> ma_najviac_x(n, 1);
for(int i=0; i<n; i++)
{
int e;
scanf("%d", &e);
printf("%d", ma_najviac_x[e]);
ma_najviac_x[e]++;
if(i+1 < n) printf(" ");
else printf("\n");
}
return 0;
}
Šetrenie pamäťou
Aj v tomto riešení sa dá ušetriť nejaká pamäť. V podstate iba inak ošetríme čísla \(x\), pre ktoré neexistuje holubník s \(x\) holubmi. Doteraz sme si pre takéto čísla pamätali prvý holubník s menej ako \(x\) holubmi. Teraz si pre ne nebudeme pamätať vôbec nič. Počas ubytovávania holubov sa nám totiž nikdy nestane, že by sme potrebovali zistiť číslo prvého holubníka s \(x\) alebo menej holubmi, ak neexistuje holubník s presne \(x\) holubmi.
To však prináša niekoľko technických problémov. Prvým problémom je, že už nám nestačí obyčajné pole indexované podľa počtu holubov v holubníku, keďže takéto pole by bolo príliš veľké. Stále však chceme byť schopní pre dané \(x\) rýchlo nájsť prvý holubník s \(x\) holubmi. Preto použijeme mapu založenú na vyvažovanom vyhľadávacom strome. Vo väčšine rozumných programovacích jazykov sú takéto stromy už implementované, v C++ je to std::map
, v Jave TreeMap
1. V takejto mape vieme k hodnote pre dané \(x\) pristupovať v čase \(O(\log m)\), kde \(m\) je počet prvkov v mape. V rovnakom čase vieme z mapy aj mazať a vkladať do nej nové prvky.
Druhý problém je aktualizácia našej informácie. Keď nám priletí holub s extroverciou \(e\) a ubytujeme ho, zanikne nám jeden holubník s \(e\) holubmi a vznikne nám holubník s \(e+1\) holubmi. Musíme teda skontrolovať, či sme predtým mali nejaký holubník s \(e+1\) holubmi. Ak nie, treba do našej mapy pridať informáciu o tom, že takýto holubník máme (aj s jeho číslom).
Ďalej potrebujeme overiť, či ešte stále máme nejaké holubníky s \(e\) holubmi. Ak áno, potom musíme aktualizovať číslo prvého z nich (teda zvýšiť ho o \(1\) oproti doterajšej hodnote). Ak nie, potom treba z mapy vyhodiť záznam o holubníkoch s \(e\) holubmi. Aby sme zistili, či máme holubník s \(e\) holubmi, stačí nám pozrieť sa na číslo prvého holubníka s menej ako \(e\) holubmi. Ak je to holubník hneď za holubníkom, do ktorého sme práve nasťahovali \(e+1\)-vého holuba, znamená to, že žiadne holubníky s \(e\) holubmi už nemáme. Ak je prvý holubník s menej ako \(e\) holubmi až niekde ďalej, potom ešte nejaké holubníky s \(e\) holubmi máme.
Polohu prvého holubníka s menej ako \(e\) holubmi vieme za pomoci našej mapy nájsť v čase \(O(\log m)\), kde \(m\) je počet záznamov v mape.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
map<int, int> prvy_presne_x;
prvy_presne_x[0] = 1;
for(int i = 0; i<n; i++)
{
int e;
scanf("%d", &e);
printf("%d", prvy_presne_x[e]);
if(prvy_presne_x.count(e+1) == 0)
{
prvy_presne_x[e+1] = prvy_presne_x[e];
}
prvy_presne_x[e]++;
if(e > 0)
{
map<int, int>::iterator it = prvy_presne_x.find(e);
it--;
if(it->second == prvy_presne_x[e])
{
prvy_presne_x.erase(e);
}
}
if(i+1 < n) printf(" ");
else printf("\n");
}
return 0;
}
S odhadom pamäťovej zložitosti to bude tentoraz veselé. Pre každé číslo \(x\) také, že v aspoň jednom holubníku je presne \(x\) holubov, si pamätáme jeden záznam v mape. Takýchto čísel \(x\) je však v každom momente najviac rádovo \(\sqrt{n}\). Ak totiž máme \(k\) rôznych nezáporných celých čísel, ich súčet je minimálne \(0 + 1 + \dots + (k-1) = \frac{k(k-1)}{2}\), čo je zhruba polovica z \(k^2\). To znamená, že môžeme mať najviac zhruba \(\sqrt{2n}\) rôznych \(x\), pre ktoré existuje holubník s \(x\) holubmi, inak by sme dokopy v našich holubníkoch museli mať viac než \(n\) holubov. Okrem mapy máme už iba konštantne veľa premenných, teda pamäťová zložitosť nášho algoritmu je \(O(\sqrt{n})\).
Každého holuba spracovávame v čase \(O(\log m)\), pričom v mape nikdy nebude viac ako rádovo \(\sqrt{n}\) čísel, teda môžeme povedať, že spracovanie jedného holuba nám bude trvať čas \(O(\log \sqrt{n}) = O(\log n)\). To znamená, že celý algoritmus pobeží v čase \(O(n \log n)\).
Možno sa pýtate, prečo nepoužijeme hešmapu, keď je rýchlejšia. Dôvod je taký, že pri aktualizovaní informácie budeme chcieť cez našu mapu vedieť iterovať podľa veľkosti \(x\).↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.