Zadanie
Keď Emo pozrel von z okna a uvidel sneh, zmenil svoje plány a rozhodol sa, že päty z izby nevystrčí. Povedal si, že tento dlhý zimný večer strávi pri partičke šachu s so svojím spolubývajúcim Marcelom. Jediná šachovnica, ktorú zohnali, však bola pomaľovaná všetkými možnými farbami, a tak sa nedokázali sústrediť. Rozhodli sa preto, že ju opravia.
Zohnali si fixy všetkých potrebných farieb a povedali si, že niektoré políčka prefarbia tak, aby výsledná šachovnica bola iba dvojfarebná a farby políčok sa striedali ako biele a čierne na šachovnici. Keďže si ale fixky požičali, chcú ich čo najmenej vypísať. Koľko najmenej políčok musia prefarbiť tak, aby dostali peknú šachovnicu?
Úloha
Máme zadanú šachovnicu veľkosti \(n \times n\), ktorej každé políčko má nejakú farbu. Zistite, koľko najmenej políčok je potrebné prefarbiť tak, aby políčka šachovnice obsahovali iba \(2\) rôzne farby, ktoré sa striedajú horizontaĺne aj vertikálne (tak ako biele a čierne políčka na šachovnici).
Formát vstupu
Farby si budeme reprezentovať celými číslami. V prvom riadku vstupu je jedno celé číslo \(n\) (\(1 \leq n \leq 500\)) – rozmer šachovnice. Nasleduje \(n\) riadkov, každý z nich obsahuje \(n\) medzerou oddelených celých čísel – \(j\)-te číslo v \(i\)-tom riadku vstupu označuje farbu políčka v \(i\)-tom riadku a \(j\)-tom stĺpci šachovnice. Môžete predpokladať, že všetky čísla sú medzi \(0\) a \((n ^{2}-1)\).
Formát výstupu
Vypíšte jeden riadok obsahujúci jedno číslo – najmenší počet políčok, ktoré je potrebné zmeniť.
Hodnotenie
Riešenia budú testované na štyroch sadách testovacích vstupov, pre jednotlivé sady platia nasledovné obmedzenia:
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(n \leq\) | \(50\) | \(200\) | \(300\) | \(500\) |
Príklady
Input:
4
1 2 1 3
2 1 2 2
3 1 2 5
5 4 2 1
Output:
8
Zmenením vhodných \(8\) políčok vieme dostať nasledovnú šachovnicu:
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1
Input:
5
6 3 6 1 6
3 6 1 6 3
6 1 6 1 6
3 6 1 6 3
6 3 6 1 6
Output:
6
Buď prefarbíme všetky jednotky na trojky, alebo všetky trojky na jednotky. V oboch prípadoch musíme opraviť \(6\) políčok.
O farbách políčok
Políčka, ktoré majú mať rovnakú farbu ako políčko v ľavom hornom rohu, budeme v tomto vzoráku volať biele a políčka, ktoré majú mať opačnú farbu, budeme volať čierne. Ak si očíslujeme riadky a stĺpce šachovnice číslami \(0\) až \(n-1\) tak, že ľavý horný roh má súradnice \((0,0)\) a pravý dolný roh má súradnice \((n-1, n-1)\), biele políčka budú mať párny súčet súradníc a čierne nepárny1. Ak teda chceme o nejakom políčku zistiť, či je biele alebo čierne, stačí sa pozrieť na súčet jeho súradníc.
Hrubá sila
Našim cieľom bolo nájsť čo najmenej políčok, ktoré treba zmeniť na to, aby bola šachovnica len dvojfarebná. Môžeme teda vyskúšať všetky možnosti – pre všetky možnosti, na ktorú farbu nakoniec prefarbíme biele políčka vyskúšame všetky možnosti, na ktorú farbu prefarbíme čierne políčka. Pre každú takúto dvojicu farieb si prejdeme celú šachovnicu a spočítame, koľko políčok by sme museli prefarbiť. Zapamätáme si tú možnosť, pre ktorú sme toho museli prefarbiť najmenej.
Možností, ktorú farbu použijeme na biele políčka je \(n^2\), pre každú z nich je \(n^2-1\) možných farieb pre čierne. Skúšame teda \(n^2 \cdot (n^2-1)\) možností, čo je \(O(n^4)\). Pre každú možnosť prechádzame celú šachovnicu veľkosti \(n^2\), časová zložitosť algoritmu je teda \(O(n^6)\). Musíme si pamätať celú šachovnicu a zopár premenných navyše, takže naša pamäťová zložitosť je \(O(n^2)\).
Polohrubá sila
Aby sme nemuseli pre každú dvojicu farieb prechádzať celú šachovnicu, môžeme si pre každú z \(n^2\) farieb spočítať, koľkokrát sa nachádza na bielom políčku a koľkokrát na čiernom políčku. Keď potom chceme pre nejakú dvojicu farieb zistiť, koľko políčok by sme museli prefarbiť, stačí nám od počtu všetkých políčok (\(n^2\)) odrátať počet bielych políčok, ktoré už majú správnu farbu a počet čiernych políčok, ktoré už majú správnu farbu.
Časová zložitosť sa nám zníži na \(O(n^4)\). Pôvodnú šachovnicu si už pamätať nepotrebujeme, musíme si však pamätať počet výskytov na bielych a čiernych políčkach pre každú z \(n^2\) farieb. Pamäťová zložitosť teda ostáva \(O(n^2)\).
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
//pocty[x][0] = kolko krat bola farba x na 'bielom' policku, pocty[x][1] = na ciernom
vector< vector<int> > pocty(n*n,{0,0});
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
int x,farba = (i+j)%2;
cin >> x;
pocty[x][farba]++;
}
}
int best = n*n-1;
for(int biela=0;biela<n*n;++biela)
{
for(int cierna=0;cierna<n*n;++cierna)
{
if(biela == cierna)
continue; //nemozeme celu sachovnicu premalovat rovnakou farbou
best = min(best,n*n-pocty[biela][0]-pocty[cierna][1]);
}
}
cout << best << "\n";
return 0;
}
Vzorové riešenie
Jedna farba
Pozrime sa najprv na jednoduchší prípad, v ktorom by jedna farba šachovnice bola už opravená, napríklad biela, a my by sme potrebovali opraviť tú druhú.
Máme na šachovnici na čiernych políčkach rôzne farby a chceme vybrať jednu, na ktorú potom prefarbíme všetky ostatné čierne políčka. Z toho je zrejmé, že ak vyberieme farbu, ktorá sa na čiernych políčkach vyskytuje najviac, budeme potrebovať najmenej prefarbovania. Riešením by bolo zrátať pre každú farbu, koľkokrát sa na čiernych políčkach vyskytuje a následne vybrať farbu s maximálnym výskytom (ale nie tú, ktorou sú vyfarbené biele políčka). Stačí potom ostatné políčka prefarbiť na ňu.
Celá šachovnica
Ak by sme chceli predchádzajúce riešenie použiť na celú šachovnicu, narazíme na jeden problém. Mohlo by sa nám stať, že pre biele aj čierne políčka šachovnice vyberieme rovnakú farbu. To by ale potom nebola šachovnica, lebo by bola celá jednofarebná. Tento problém vyriešime tak, že si pre biele aj čierne políčka nájdeme dve najčastejšie sa vyskytujúce farby. Ak sa nám potom stane, že najčastejšie sa vyskytujúca farba je pre oba typy políčok rovnaká, pre jeden z nich využijeme druhú najčastejšiu farbu.
Máme pritom dve možnosti: buď vezmeme najlepšiu farbu pre biele políčka a druhú najlepšiu pre čierne, alebo najlepšiu pre čierne a druhú najlepšiu pre biele. Vyskúšame teda obe z nich a vyberieme si tú lepšiu.
Implementácia
Najprv chceme hľadať najčastejšiu farbu pre biele aj čierne políčka. Mohli by sme pre každú farbu prejsť celú šachovnicu a spočítať, koľkokrát sa vyskytuje na oboch typoch políčok. Ak by ale malo každé políčku inú farbu, trvalo by nám to až \(O(n^2 \cdot n^2)\). Vytvoríme si preto pole veľkosti \(n^2\), v ktorom si budeme pre jednotlivé farby pamätať, na koľkých bielych políčkach sa vyskytujú. Také isté pole si vytvoríme aj pre výskyty na čiernych políčkach. Teraz nám stačí jedno prejdenie šachovnice. Pri každom políčku sa pozrieme, či je to biela alebo čierna pozícia a potom do vhodného prvku príslušného poľa prirátame jedna. Po prejdení celej šachovnice máme zrátané výskyty všetkých farieb na oboch typoch pozícií.
Potrebujeme teraz nájsť dve najväčšie hodnoty v oboch poliach. Mohli by sme naše polia utriediť a potom použiť najväčšie hodnoty. To by nám ale trvalo až \(O(n^2 \log n^2)\). Namiesto toho nám stačí obe naše polia raz prejsť. Pritom si budeme v dvoch premenných pamätať, aké su dve najčastejšie farby a pri prechádzaní poľa to postupne aktualizovať. Takto nám nájdenie najčastejších farieb bude trvať už len \(O(n^2)\).
Potom nám už len stačí na základe početnosti najčastejších a druhých najčastejších farieb vybrať, akou farbou ofarbíme čierne políčka a akou biele. Počet políčok, ktoré treba prefarbiť, zrátame ako \(n^2\) mínus počet políčok (bielych aj čiernych), ktoré už majú správnu farbu.
V riešení najprv načítame celú šachovnicu, pričom si rátame počty farieb na bielych a čiernych pozíciách. To nám trvá čas \(O(n^2)\). Následne hľadáme najčastejšie farby jedným prejdením v dvoch poliach veľkosti \(n^2\) a to nám bude tiež trvať \(O(n^2)\). Celková časová zložitosť bude preto \(O(n^2)\). Keď sa pozrieme na pamäť, pamätáme dve polia pre výskyty farieb, ktoré majú veľkosť \(2n^2\). Výsledná pamäťová zložitosť je teda \(O(n^2)\).
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
//pocty[x][0] = kolko krat bola farba x na 'bielom' policku, pocty[x][1] = na ciernom
vector< vector<int> > pocty(n*n+1,{0,0});
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
int x,farba = (i+j)%2;
cin >> x;
pocty[x][farba]++;
}
}
//best[0][x] = najcastejsie cislo na polickach farby x, best[1][x] = druhe najcastejsie
int best[2][2] = { {n*n,n*n}, {n*n,n*n} };
for(int i=0;i<n*n;i++)
{
for(int farba=0;farba<2;++farba)
{
if(pocty[i][farba] > pocty[ best[farba][0] ][farba])
{
best[farba][1] = best[farba][0];
best[farba][0] = i;
}
else if (pocty[i][farba] > pocty[ best[farba][1] ][farba])
{
best[farba][1] = i;
}
}
}
if(best[0][0] != best[1][0])
cout << n*n - (pocty[best[0][0]][0] + pocty[best[1][0]][1]) << "\n";
else cout << n*n - max( pocty[best[0][0]][0]+pocty[best[1][1]][1],pocty[best[0][1]][0]+pocty[best[1][0]][1] ) << "\n";
return 0;
}
Pri číslovaní od jednotky to platí tiež.↩
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ť.