1. Párty vzorové riešenie

5 1 2

cccvcc

Našou úlohou je z daného počtu znakov c a v poskladať reťazec znakov, ktorý bude mať určitý počet prechodov(miesto, kde sú vedľa seba dva rozdielne znaky). Kedže máme počty c a v zadané, tak našou úlohou je tieto znaky len vhodne preusporiadať.

Riešenie hrubou silou

Kedže hľadáme iba preusporiadanie, ktoré spĺňa určité podmienky, môžeme samozrejme vyskúšať všetky preusporiadania. Pri každom preusporiadaní skontrolujeme, či má požadovaný počet prechodov. V prípade, že áno, ho vypíšeme a skončíme. Pokiaľ chceme skúšať všetky možnosti, zväčša sú na výber dve možné cesty.

Prvá, implementačne možno jednoduchšia, je založená na metóde next_permutation. Táto funkcia v C++ vie vyrábať permutácie. Ako? Ako už názov napovedá, pokiaľ ju zavoláme na nejakú množinu prvkov vo vektore, vráti ďalšiu permutáciu. Ďalšiu v tomto prípade znamená v lexikografickom poradí. Ak teda túto funkciu zavoláme na vektor obsahujúci 0007, funkcia vráti true a obsah sa zmení na 0070. Pokiaľ však zavoláme túto funkciu na pole či vektor obsahujúci 7000, čo je zjavne lexikograficky posledná permutácia, vráti nám false a nič nespraví. To znamená, že pokiaľ jej na začiatku dáme utriedený vektor a budeme túto funkciu volať, pokým nevráti false, vygeneruje nám každú permutáciu. Užitočný je fakt, že permutácie, ktoré sa líšia iba v preusporiadaní rovnakých prvkov nám vráti iba raz. Kód by mohol vyzerať takto: (Upozorňujeme na celkom neštandardnú konštrukciu do-while, ktorá sa často s next_permutation používa. Tá zapríčiní, že pred prvým volaním next_permutation sa ešte preverí úplne prvá permutácia.)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int a, b, x;
    cin >> a >> b >> x;

    vector<int> prac(a+b, 1);

    for(int i=0; i<a; ++i)
        prac[i] = 0;

    do
    {
        int pocet_inverz = 0;
        
        for(int i=0; i+1<a+b; ++i)
            if(prac[i] != prac[i+1])
                ++pocet_inverz;

        if(pocet_inverz == x)
            break;

    } while(next_permutation(prac.begin(), prac.end()));
    
    for(int i=0; i<a+b; ++i)
    {
        if(prac[i] == 1) cout << 'v';
        else cout << 'c';
    }
    cout << endl;
    
    return 0;
}

Aká je časová zložitosť tohto riešenia? Mohlo by sa zdať, že permutácií je \(n!\). My však vieme, že niektoré permutácie sú totožné, pretože jednotlivé znaky c a v nerozlišujeme. Preto platí, že permutácií je \(\frac{(a+b)!}{a!b!}\). Vďaka použitu funkcie next_permutation platí, že časová zložitosť je totožná počtu permutácií, teda \(O(\frac{(a+b)!}{a!b!})\). Jedno volanie next_permutation síce môže trvať rádovo až \(O(n)\), potom však bude nasledovať viac rýchlych volaní. Toto sa volá amortizovaná časová zložitosť. Pamäťová zložitosť je \(O(a+b)\), pretože si musíme pamätať preverovaný reťazec dĺžky práve \(a+b\).

Druhá cesta, ktorou sa môžeme vydať, sú triky s bitmi. Pokiaľ chcete, môžete túto časť vzorového riešenia preskočiť, ide skôr o pekný bonus. Mohli by sme povedať, že je zbytočné hrať sa s bitmi, pokiaľ máme na permutovanie funkciu, ktorá je jednoduchá a funkčná. Fakt ale je, že bitové operácie sú na počítači rýchle a tento spôsob sa často dá použiť na výrazné urýchlenie bruteforcu. Predstavme si, že ideme riešiť túto úlohu znova generovaním všetkých preusporiadaní. Ukázali sme si, že máme nejakých \(n\) znakov. Čo je dôležité, tie sú iba dvoch typov, znak je teda buď c, alebo v. To je pri tejto technike veľmi dôležité. Veci, ktoré chceme odlíšiť, musia byť iba dvoch kategórií - to z dôvodu aby ich bolo možné reprezentovať ako 0 a 1. Ako teraz prísť na všetky preusporiadania? Pokiaľ je vecí \(n\), môžeme si túto situáciu predstaviť ako \(n\)-bitové číslo. Situáciu 10001 vieme teraz interpretovať ako cvvvc. Čo sme touto reprezentáciou získali? Odpoveď je, že teraz vieme jednoducho generovať všetky možnosti. Pokiaľ prejdeme čísla od \(0\) po \(2^n-1\), získame všetky možné \(n\)-tice c a v v každom možnom preusporiadaní, stačí sa nám teda len pozrieť na zápis týchto čísel v dvojkovej sústave. Vyskúšajme si to pre \(n=3\), \(c=2\), \(v=1\). Pomocou troch bitov vieme získať čísla 000, 001, 010, 011, 100, 101, 110, 111. Iste, niektoré čísla neodpovedajú počtami bitov rozumnému počtu c a v. To nám však nevadí, pretože tento spôsob bude veľmi rýchly, nakoľko nám stačí iba inkrementovať jednú premennú. Otázka ešte je, ako z čísla \(x\), vieme dostať hodnotu \(i\)-teho bitu… To už je miesto, kde prichádza k spomínanému triku. Na zistenie bitu nám stačí operácia shift, ktorá posunie bitovú reprezentáciu čísla doľava a nové miesto doplní nulou. Teda 1 << 2 = 4 pretože bitová reprezentácia 1 posunutá doľava a doplnená nulami nám dá 100, čo je v desiatkovej sústave 4. Teraz už len potrebujeme operáciu and, ktorá vezme dve bitové reprezentácie čísel a urobí po bitoch logický and. Teda 121 and 55 = 1111001 and 0110111 = 0110001. Teraz využijeme trik, ktorý spočíva v tom, že keď spravíme x and (1<<i), dostaneme kladné číslo práve vtedy, keď \(i\)-ty bit \(x\) sprava bol 1 a nulu ak bol 0. Pýtaním sa na jednotlivé bity vieme zistiť ich jednotlivé hodnoty. Napriek tomu, že to môže vyzerať ako zdĺhavý proces. Pre \(n=7\), teda \(2^n\) možností urobíme pri pýtaní sa na jednotlivé bity iba 14 operácií, ktoré sú pre procesor zo súdka najjednoduchších a najrýchlejších. Program by mohol vyzerať nejak takto:

#include <iostream>

using namespace std;

int main()
{
    int c, v, p;
    cin >> c >> v >> p;
    
    int n = c+v;
    
    for(int i=0; i<(1<<n); ++i)
    {
        int inver = 0, nc = 0, nv = 0;
        
        for(int j=n-1; j>=0; --j)
        {
            if(i & (1<<j))
                ++nc;
            else
                ++nv;
            
            if(j>0 && (bool)(i & (1<<(j-1))) != (bool)(i & (1<<(j))))
                ++inver;
        }
        
        if(nc == c && nv == v && inver == p)
        {
            for(int j=n-1; j>=0; --j)
            {
                if(i & (1<<j)) cout << 'c';
                else cout << 'v';
            }
            cout << endl;
            return 0;
        }
    }
    
    return 0;
}

Ak si nie ste istý, či ste porozmueli tomuto triku, môžete si ho vyskúšať napr. na úlohe vojaci.

Aká je časová zložitosť tohto riešenia? Všetkých vyskúšaných možností je zjavne \(2^{a+b}\). Overenie každého preusporadania trvá \(O(a+b)\). Dokopy to teda celé trvá \(O(2^{a+b}\cdot (a+b))\).

Obidve doterajšie riešenia fungujú na princípe, že si najprv vyberieme nejaké poradie a potom ho kontrolujeme. Nebolo by lepšie nájsť spôsob, akým vieme určiť správne usporiadanie bez toho, aby sme ho museli overovať?

Vzorové riešenie

Pokaždé budeme predpokladať, že počet v je väčší nanajvýš rovný počtu c. To samozrejme nemusí platiť. V tom prípade si na všetkých miestach, kde použijeme znak c môžeme predstaviť znak v a naopak. Predstavme si nachvíľu, že sme už všetky znaky v uložili, kedže na konci aj tak všetky skončia v koláči a všetky znaky c chceme nejako poukladať medzi nich. Na úlohu sa teraz môžeme teraz pozrieť ako na vkladanie c do niečoho tvaru XvXvX...XvXvX. Na každé miesto označené X(chlievik) môžeme dať nejaký, možno aj nulový počet c.

Prvá zaujímavá vec, ktorú by sme mohli zistiť je, aký najmenší a najväčší počet prechodov vieme dosiahnuť. Najmenší počet prechodov vieme zrejme dosiahnuť tak, že poukladáme jeden typ cesta za seba a potom ďalší. Dostaneme postupnosť tvaru c...cv...v s jedným prechodom. Rozoberme si ešte najväčší dosiahnuteľný počet prechodov. Uložením prvého c do chlievika, získame nejaký počet prechodov. Uložením ďalšieho c do chlievika, v ktorom sa už jedno c nachádza nové prechody nezískame. V krajných chlievikoch vložením získame 1 prechod. Uložením na ostatné X získame 2 prechody. Maximálny počet prechodov získame tak, že najskôr ukladáme c do vnútorných chlievikov a na koniec do dvoch krajných. Uvedomme si, že obidva krajné chlieviky nikdy nevyužijeme, nakoľko by to znamenalo, že počet c je väčší ako počet v(cvcvc). Rozlíšime teraz dva prípady. Pokiaľ je počet c rovný počtu v vieme získať \(c+v-1\) prechodov s tým, že využijeme práve jeden okrajový chlievik. Pokiaľ je počet \(c\) menší, vieme získať práve \(2c\) prechodov. Kedže máme garantované, že riešenie existuje, vieme skonštruovať vzorové riešenie.

Najprv si označíme znak, ktorého je menej \(m\) a toho, ktorého je viac \(v\). To, čo namiesto nich budeme vypisovať na výstup teda záleží na jednotlivých počtoch cesta. Uvedomme si, že pokiaľ je počet prechodov nepárny, vieme, že musíme využiť jeden z dvoch krajných chlievikov. Všetky ostatné nám totiž dajú párny počet prechodov. Dohodneme sa, že pokiaľ takéto niečo nastane, vždy umiestnime cesto farby m do prvého chlievika. Riešenie je teraz celkom priamočiare. Postupne plníme chlieviky zľava doprava, pokiaľ dosiahneme želaný počet prechodov, všetky ostávajúce cestá farby m vložíme do posledného použitého chlievika.

#include <iostream>

using namespace std;

int main()
{
    int a, b, x;
    cin >> a >> b >> x;
    
    char m = 'c', v = 'v';
    
    if(a > b)
    {
        swap(a, b);
        swap(m, v);
    }

    for(int i=0; i<b; ++i)
    {
        if(i == 0 && (x%2) == 1)
        {
            cout << m;
            --x;
            --a;
        }
        
        if(i != 0 && x != 0)
        {
            cout << m;
            x -= 2;
            --a;
        }
        
        if(x == 0) while(a-- > 0) cout << m;
        
        cout << v;
    }
    cout << endl;
    
    return 0;
}

Časová zložitosť tohto riešenia je \(O(a+b)\), kedže pri každej našej operácii trvajúcej konštantný čas sa zníži počet a alebo b, ktoré zároveň aj vypisujeme. Pamäťová zložitosť je \(O(1)\), keďže si výsledné poradie ciest nemusíme pamätať, lebo hneď vieme povedať, v akom poradí budú na torte.