6. O introvertných a extrovertných holuboch vzorové riešenie

4
0 0 0 0

1 2 3 4

5
0 1 2 3 4

3 3 3 3 3

8
0 0 1 0 1 2 3 2

4 2 4 3 2 2 2 4

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¹. 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)\).