Hľadanie šachovníc

Najprv zabudnime na to, že situácia sa bude časom meniť tým že budeme vyrezávať. Pozrime sa na úvodný stav a poďme v ňom hľadať najväčšie šachovnice. O každom políčku by sme chceli vedieť, aká veľká šachovnica v ňom môže končiť. Presnejšie, chceme vyrobiť pole $S[y][x]$, kde bude pre každé políčko zapísaná veľkosť najväčšej možnej šachovnice, ktorá má v tom políčku pravý dolný roh.

Toto sa dá spraviť cez dynamické programovanie. Netreba žiadne exotické triky, bude to klasická 2D dynamika v ktorej každá hodnota závisí len od hodnôt nášho ľavého, horného, a šikmého ľavého horného suseda. Len ten vzorec môže byť trochu neintuitívny.

Ak sme v prvom riadku alebo stĺpci, $S[y][x]$ je zjavne 1. Ak má nejaký náš sused nesprávnu farbu, tiež to bude 1. Ak majú všetci traja vyhovujúcu farbu, použijeme tento vzorec:

$$ S[y][x] = 1 + \min(S[y-1][x], \ S[y][x-1], \ S[y-1][x-1]) $$

Zamyslime sa, prečo to platí. $S[y][x]$ musí byť aspoň toľko čo hovorí tento vzorec, lebo bez ohľadu na to ktorý sused je ten najmenší, spolu s ostatnými susedmi sa poskladajú na o 1 väčší štvorec. Napríklad povedzme že vľavo odo mňa je hodnota presne 42 a hore aj vľavo hore odo mňa je aspoň 42 alebo viac. Keď sa tie tri šachovnice zjednotia, a pridáme naše políčko, vznikne šachovnica veľká (aspoň) 43.

$S[y][x]$ určite nemôže byť viac ako hovorí vzorec, pretože by z toho vyplynulo že ten sused má mať väčšiu hodnotu ako má. Napríklad povedzme že moja hodnota je 47 ale môj ľavý sused má iba 45. No ale ak ja mám pravý dolný roh platnej šachovnice veľkej 47, táto šachovnica pokrýva aj celú tú šachovnicu veľkú 45 môjho ľavého suseda, a aj prečnieva na ďalší riadok a stĺpec, takže ľavý sused by mal byť aspoň 46. Čo je spor.

$O(r^2c^2)$

riešenie

Opakujeme kým je čo vyrezávať: Na základe momentálneho stavu vyrobíme naším vzorcom pole $S$. Nájdeme v ňom najväčšiu hodnotu $S[y][x]$ (a najmenšie $y$, a najmenšie $x$). Tým sa dozvieme, že teraz máme vyrezať šachovnicu s touto veľkosťou a týmto pravým dolným rohom. O každom políčku tejto šachovnice si zapamätáme, že už je vyrezané (v ďalších kolách odteraz budú mať $S[y][x] = 0$ a tým ovplyvnia svojich susedov).

Šachovníc môže byť najviac $rc$ a v každej iterácii odznova vypočítame celé pole $S$ v čase $O(rc)$, takže dokopy nám to potrvá $O(r^2c^2)$.

Ktoré hodnoty sa vlastne

zmenia?

Nemusíme zakaždým odznova počítať celé pole $S$. Vždy keď vyrežeme ďalší štvorec, zmenia sa iba tie políčka, ktorých doterajšia maximálna šachovnica podľa $S$ sa prekrývala s tou našou vyrezanou, a tým pádom odteraz už nie je dostupná. Vtedy sa hodnota v $S$ zmenší (zväčšiť sa nemôže).

Pre políčka vľavo od ľavého okraja alebo hore od horného okraja vyrezanej šachovnice sa hodnota v $S$ nezmení. Berieme vždy pravý dolný roh, takže sa nemajú ako prekrývať.

Pre ostatné políčka sa hodnota v $S$ zmeniť môže, ale iba ak sú k vyrezanej šachovnici relatívne blízko. Je to tak preto, že šachovnice vyrezávame od najväčšej veľkosti. V momente keď režeme šachovnicu veľkú $d\times d$, už nikde nenájdeme väčšiu – už sú všetky $S[y][x] \leq d$. Takže nás trápia len šachovnice, ktoré sa prekrývajú s vyrezanou, a sú veľké $d$ alebo menej. Také šachovnice nemôžu byť vzdialené viac ako $d$.

Takže vždy keď vyrežeme šachovnicu veľkú $d$ s pravým dolným rohom $(y, x)$, stačí aktualizovať hodnoty $S$ vo štvorci veľkom $2d\times 2d$ ktorý siaha od $y-d$ po $y+d$ a od $x-d$ po $x+d$ (uhhhh plusmínus jedna…).

To si môžeme dovoliť! Obsah štvorca $2d\times 2d$ je štvornásobok obsahu štvorca $d\times d$. Dá sa povedať, že vyrezanie jedného políčka nás stojí štyri updaty v $S$. Koľko dokopy vyrežeme políčok? Samozrejme $rc$. Takže koľkokrát dokopy budeme niečo prepisovať v $S$? $4rc$, čiže $O(rc)$.

$O(rc\cdot\min(r,c))$ riešenie

Vyskúšame fakt každú možnú šachovnicu v predpísanom poradí. Čiže:

Pre každú veľkosť $d$ od $\min(r, c)$ po $1$: Pre každé $y$: Pre každé $x$: Pozrime sa, či je $S[y][x] = d$. Ak áno, super, našli sme šachovnicu ktorú chceme vyrezať. Zapíšeme si o každom jej políčku že je vyrezané, prepočítame hodnoty $S$ v okolitom štvorci veľkom $2d\times 2d$, a ideme ďalej.

Tento algoritmus je $O(rc\cdot\min(r, c))$. Za prepočítanie malého okolia $S$ neplatíme nič extra, lebo dokopy všetkých zmien v $S$ robíme len $O(rc)$, a novú hodnotu v $S$ náš vzorec spočíta v konštantnom čase.

(Un)fun fact: Tento bruteforce mi ako organizátorovi spôsobuje samé problémy. Asymptotická časová zložitosť nie je optimálna, ale má úžasnú konštantu. V praxi je hrozne rýchly a nie veľmi chápem prečo. :( Nepodarilo sa mi nastaviť veľkosť vstupov a časový limit tak, aby prešlo všetko čo má prejsť, ale tento neprešiel. Smutný život.

$O(rc\cdot\log(rc))$ riešenie

Spravíme vyvažovaný vyhľadávací strom, napríklad std::set, ktorý nám poslúži ako “prioritná fronta s editovaním”. Bude obsahovať trojicu $(d,y,x)$ vždy práve vtedy keď platí $S[y][x]=d$. Vhodne skonštruujeme trojice (dáme tam záporné $d$) alebo definujeme custom porovnávaciu funkciu, aby boli vo vhodnom poradí a na začiatku setu bola vždy najlepšia šachovnica. Vždy keď v $S$ niečo zmeníme, upravíme aj set (zmažeme starú trojicu a pridáme novú).

Opakujeme kým je čo vyrezávať: Zistíme zo setu najlepšiu existujúcu šachovnicu. Zapíšeme si o každom jej políčku že je vyrezané, prepočítame hodnoty $S$ v okolitom štvorci veľkom $2d\times 2d$, upravíme set, a ideme ďalej. Toto trvá $O(rc\cdot\log(rc))$, lebo veľkosť setu je najviac $rc$, takže každá zmena v ňom trvá $\log(rc)$, a robíme $O(rc)$ zmien v $S$ a teda aj v sete.

Pre záujem zopár optimalizácii čo sa tu dá spraviť. V KSP sa väčšinou snažíme aby ich nebolo treba, a toto aj tak nie je optimálne riešenie, ale možno sa vám niekedy v živote zídu.

• std::set má veľkú konštantu. Môžeme namiesto neho použiť haldu, napríklad std::priority_queue, alebo std::make_heap a spol. Jediná komplikácia je, že z haldy nejde zmazať ľubovoľný prvok, iba vrchný. Nevadí, tak ich proste pri zmene $S$ nebudeme mazať. Naša halda bude mať nielen trojice $(d,y,x)$ také že $S[y][x]=d$, ale aj všelijaké smeti, o ktorých to kedysi platilo. Vždy keď vyberieme vrchnú trojicu z haldy, najprv skontrolujeme či ešte stále $S[y][x]=d$. Veľkosť haldy aj vrátane smetí je najviac $O(rc)$, takže časová zložitosť bude rovnaká, ale halda je v praxi o dosť rýchlejšia (aspoň v tejto úlohe).

• Namiesto std::tuple<int, int, int> alebo structu s 3 číslami môžete trojice namačkať po bitoch do jedného intu. Vďaka tomu sa viac dát zmestí do CPU cache, a nejakú rýchlosť tým vyžmýkate. Pri std::priority_queue to môže spraviť skoro dvojnásobok.

• Operácie na std::set aj std::priority_queue sú drahé. Nemeňte ich pre úplne každé políčko v $2d\times 2d$ štvorci, iba tie, kde sa hodnota v $S$ fakt zmenila.

Riešenie, ktoré implementuje tieto 3 zlepšováky, bolo u nás asi 4x rýchlejšie ako bez nich.

$O(rc)$

riešenie

Podobne ako v $O(rc\cdot\min(r,c))$ riešení, vo vonkajšom cykle spracujeme samostatne každú veľkosť $d$ od $\min(r, c)$ po $1$. Podobne ako v $O(rc\cdot\log(rc))$ riešení s haldou, budeme si v nejakej štruktúre pamätať políčka podľa toho, akú majú hodnotu v $S$ (alebo sú to smeti čo ju kedysi mali), aby sme nemuseli skúšať každé $y$ a $x$.

Tá štruktúra bude normálne pole. Každá veľkosť $d$ bude mať svoje vlastné pole $Q_d$, ktoré obsahuje tie dvojice $(y,x)$ o ktorých platí $S[y][x]=d$, alebo kedysi platilo. Tieto polia budú zo začiatku neutriedené. Keď ideme spracovávať veľkosť $d$, utriedime pole $Q_d$ a prejdeme ho. O každom prvku najprv skontrolujeme, či tá šachovnica stále existuje, alebo sú to smeti. Ak existuje, vyrežeme ju, prepočítame okolie $2d\times 2d$, a zmeny v $S$ si poznačíme v poliach $Q_?$. Hodnoty v $S$ môžu iba klesať, a pri spracovávaní $d$ už nie je žiadna väčšia ako $d$, takže v poli $Q_d$ už nebude nič pribúdať po tom, čo sme ho utriedili.

Trik je v tom, že na triedenie použijeme radix sort. Na dvojicu $(y,x)$ sa dá pozrieť ako dvojciferné číslo v $\max(r,c)$-kovej sústave. Zoradiť $n$-prvkové pole $l$-ciferných čísel v $s$-kovej sústave trvá $O(l\cdot(n+s))$. Takže utriediť jedno pole $Q_d$ potrvá $O(2\cdot(|Q_d|+\max(r,c)))=O(|Q_d|+\max(r,c))$. Sčítajme prvý člen: súčet všetkých $O(|Q_d|)$, čiže súčet dĺžok polí $Q_d$, sa rovná počtu zmien čo sme robili v $S$, čo je $O(rc)$. Sčítajme druhý člen: robíme $\min(r,c)$ triedení a každé trvá $O(\max(r,c))$, čiže $O(\min(r,c)\max(r,c))$, čo je samozrejme $O(rc)$. A ako v predošlých riešeniach, všetko vyrezávanie objavených šachovníc a upravovanie $S$ tiež dokopy trvá $O(rc)$. Hurá, všetko je to $O(rc)$!

Pamäťová zložitosť je samozrejme tiež $O(rc)$.

Radix sort

Radix sort je špecializovaný triediaci algoritmus. Dokáže triediť rýchlejšie ako klasické v $O(n \log n)$. Daň za to je, že nevie triediť podľa ľubovoľného kritéria, ale len podľa celých čísel.

Najprv utriedi čísla podľa poslednej (najmenej dôležitej) cifry, potom predposlednej, a tak ďalej až po prvú. Každý krok zachová vzájomné poradie tých čo sa tam rovnajú, takže na konci budú úplne utriedené.

Triedenie podľa konkrétnej cifry vyzerá takto: Spočítame počet, ktorú číslicu sme videli koľkokrát. Z počtov spravíme prefixové súčty. Tie nám povedia o každej číslici, odkiaľ pokiaľ majú byť vo výstupe umiestnené čísla, čo ju majú. Prejdeme znova vstupné čísla a skopírujeme ich na správne miesto vo výstupnom poli, pričom si pamätáme, koľko sme zatiaľ videli s každou číslicou (alebo proste inkrementujeme pozíciu v poli prefixových súčtov).

#include <cstdint>
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
using namespace std;

using dvojica = array<int, 2>;

int H, W;
int minHW, maxHW;
vector<vector<char>> mapa;
vector<vector<int>> S;
vector<vector<dvojica>> Q;
vector<pair<int, int>> results;

void vypocitaj(int y, int x) {
  if (mapa[y][x] == 2) {
    S[y][x] = 0;
  } else if (y == 0 || x == 0 ||
      mapa[y-1][x] != 1-mapa[y][x] ||
      mapa[y][x-1] != 1-mapa[y][x] ||
      mapa[y-1][x-1] != mapa[y][x]) {
    S[y][x] = 1;
  } else {
    S[y][x] = 1 + min(min(S[y-1][x], S[y][x-1]), S[y-1][x-1]);
  }
}

vector<dvojica> sortuj_podla(int cifra, const vector<dvojica>& vstup) {
  vector<int> kolko(maxHW, 0);
  for (dvojica d : vstup) kolko[d[cifra]]++;

  vector<int> kdepatri(maxHW, 0);
  for (int i = 1; i < maxHW; i++) kdepatri[i] = kdepatri[i-1] + kolko[i-1];

  vector<dvojica> vystup(vstup.size());
  for (dvojica d : vstup) {
    vystup[kdepatri[d[cifra]]] = d;
    kdepatri[d[cifra]]++;
  }
  return vystup;
}

int main() {
  cin >> H >> W;
  minHW = min(H, W);
  maxHW = max(H, W);
  mapa.resize(H, vector<char>(W));
  S.resize(H, vector<int>(W));
  Q.resize(minHW + 1);

  for (int y = 0; y < H; y++) {
    cin.ignore(); // koniec riadku
    for (int x = 0; x < W; x += 4) {
      char ch = cin.get();
      int val = ch >= 'A' ? ch - 'A' + 10 : ch - '0';
      for (int sub = 0; sub < 4; sub++) {
        mapa[y][x+sub] = (val & (8>>sub)) ? 1 : 0;
      }
    }
  }

  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      vypocitaj(y, x);
      Q[S[y][x]].push_back({y, x});
    }
  }

  for (int velkost = minHW; velkost > 0; velkost--) {
    if (Q[velkost].empty()) continue;

    vector<dvojica> zoradeny = sortuj_podla(0, sortuj_podla(1, Q[velkost]));

    int pocet = 0;
    for (auto [rohy, rohx] : zoradeny) {
      if (S[rohy][rohx] == velkost) {
        pocet++;

        for (int y = rohy - velkost + 1; y <= rohy; y++) {
          for (int x = rohx - velkost + 1; x <= rohx; x++) {
            mapa[y][x] = 2;
          }
        }

        for (int y = rohy - velkost + 1; y <= rohy + velkost - 1 && y < H; y++) {
          for (int x = rohx - velkost + 1; x <= rohx + velkost - 1 && x < W; x++) {
            int old = S[y][x];
            vypocitaj(y, x);
            if (S[y][x] != old && S[y][x] != 0) {
              Q[S[y][x]].push_back({y, x});
            }
          }
        }
      }
    }

    if (pocet) results.push_back({velkost, pocet});
  }

  cout << results.size() << endl;
  for (auto [velkost, pocet] : results) {
    cout << velkost << ' ' << pocet << endl;
  }
}