2. Uzimený večer vzorové riešenie

4 
1 2 1 3
2 1 2 2
3 1 2 5
5 4 2 1

8

1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1

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

6

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árny¹. 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;
}