7. Novodobý farmár vzorové riešenie

2 2
R LL
RR RLR
LLL RLR
RRL RLR

4
2

0 1
LLR LR

3

Keďže sa na vstupe dokopy nachádza \(O((n+q)D)\) znakov, tak časová zložitosť načítavania vstupu bude pri všetkých riešeniach \(O((n+q)D)\), preto ju už ďalej pri odhade časovej zložitosti nebudeme spomínať.

Ako si to vôbec vieme predstaviť?

Celú úlohy si vieme reprezentovať ako hľadanie najkratšej cesty v nejakom neorientovanom grafe. Vrcholy tohto grafu budú jednotlivé odrody a hrany budú medzi odrodami \(a\) a \(b\) práve vtedy, ak sa dá zmeniť odroda \(a\) za odrodu \(b\) zaplatením \(1\) trojkenu. Hrany v tomto grafe si vieme rozdeliť na \(2\) skupiny: hrany, ktoré vznikli kvôli barterovým ponukám a hrany, ktoré vznikli kvôli laboratóriu.

Hrany, ktoré vznikli kvôli laboratóriu (označme si ich stromové) sa v rôznych vstupoch nelíšia. A čo viac, keď sa pozrieme na graf, ktorý obsahuje len tieto hrany, tak dostaneme binárny strom, ktorý je zakorenený vo vrchole reprezentujúcom prázdny genóm. Ľavý syn nejakého vrchola reprezentuje genóm, ktorý vznikol pridaním L na koniec aktuálneho genómu a pravý syn reprezentuje genóm, ktorý vznikol pridaním R.

BFS

Najprv si môžeme všimnúť, že sa nikdy neoplatí mať odrodu, ktorej genóm má dĺžku väčšiu ako \(D\). Teda nám stačí vygenerovať graf obsahujúci všetkých \(O(2^D)\) vrcholov. Keďže je najdlhšia dĺžka reťazca v prvej podúlohe pomerne malá, tak nám stačí si ho celý zapamätať a pre každú otázku pomocou prehľadávania do šírky nájsť najkratšiu cestu.

Náš graf má \(O(2^D)\) vrcholov a dokopy \(O(2^D + n)\) hrán, teda celková časová zložitosť pre jednu otázku bude \(O(2^D + n)\).

Časová zložitosť predpočitania bude \(O(nD \log{n})\) alebo \(O(2^D)\) v závislosti od implementácie.

Zbytočné a zaujímavé vrcholy

Ak by sa v úlohe nenachádzali žiadne barterové ponuky, tak cesta medzi ľubovoľnými vrcholmi \(a\) a \(b\) by vyzerala pomerne jednoducho. Najprv pôjdeme z vrcholu \(a\) smerom hore do ich najnižšieho spoločného predka (alebo aj v skratke LCA) a potom z tohto predka smerom dole do vrcholu \(b\).

Ako bude vyzerať nejaká cesta z vrcholu \(a\) do vrcholu \(b\) v grafe, kde sú aj hrany reprezentujúce barterové ponuky? Povedzme, že postupne použijeme barterové hrany \(b_1, b_2, ..., b_k\). Potom medzi koncom jednej a začiatkom ďalšej hrany bude cesta prechádzať len cez stromové hrany, teda pôjde hore do ich najnižšieho spoločného predka a potom dole.

Označme si teda vrcholy, ktoré sú konce nejakej barterovej hrany alebo sú súčasťou nejakej otázky ako zaujímavé. Ako sme si vyššie ukázali, tak nám stačí medzi každou dvojicou zaujímavých vrcholov vedieť zistiť najkratšiu cestu, ktorá prechádza len cez stromové hrany. Táto cesta pôjde cez ich najmenšieho spoločného predka. Keďže najnižší spoločný predok dvoch zaujímavých vrcholov sa nachádza niekde na ceste z jedného vrchola do koreňa, tak optimálna cesta medzi zaujímavými vrcholmi bude určite prechádzať len cez vrcholy, ktoré sú predkami aspoň jedného z nich.

Tu sa nám črtá trošku lepšie riešenie. Budeme sa pozerať na graf, ktorý obsahuje len zaujímavé vrcholy a vrcholy, ktoré sú predkami nejakého zaujímavého vrchola. Koľko ich bude? Každý vrchol je v hĺbke najviac \(D\), teda má nad sebou najviac \(D\) vrcholov. Takýto graf teda bude mať \(O((n + q)D)\) vrcholov a \(O((n + q)D)\) hrán. Ak v ňom budeme zas hľadať cesty pomocou prehľadávania do šírky, tak na jednu otázku vieme odpovedať v čase \(O((n + q)D)\) s predpočítaním v čase \(O(nD)\).

Ešte ich vieme nejaké odstrániť

Povedzme, že si medzi zaujímavé vrcholy pridáme LCA všetkých dvojíc na začiatku zaujímavých vrcholov. Keďže najkratšie cesty po stromových hranách idú len hore po LCA, tak pre každý zaujímavý vrchol nám stačí len pridať hranu medzi ním a prvým zaujímavým vrcholom, ktorý je nad ním. Takto sa vieme dostať z jedného zaujímavého vrcholu do druhého po stromových hranách rovnakou cestou, ako predtým, teda sme týmto nič nepokazili.

Koľko vrcholov ale musíme pridať? Predstavme si, že máme na začiatku v poli \(k\) zaujímavých vrcholov. Zoberme si teraz \(2\) vrcholy \(a\) a \(b\), ktorých LCA (označme si ho \(L\)) sa nachádza najhlbšie v strome. V podstrome vrcholu \(L\) sa nemôže nachádzať žiaden iný vrchol (okrem \(a\) a $b) z nášho poľa, lebo by to bolo v spore s tým, že \(L\) je najhlbšie LCA vrcholov z poľa. Preto pre ľubovoľný iný vrchol \(c\) bude platiť, že \(LCA(c,a) = LCA(c,b) = LCA(c,L)\). Preto môžeme \(a\) a \(b\) z poľa vymazať a vložiť tam \(L\). V každom takomto kroku sa zníži počet prvkov v poli o \(1\), teda nových zaujímavých vrcholov môžeme pridať najviac \(O(k)\). V asymptotickej časovej zložitosti sa nám teda nič nezhorší tým, keď tieto vrcholy pridáme medzi zaujímavé!

Vieme teda, že zaujímavých vrcholov bude spolu najviac \(O(n+q)\) a hrán medzi nimi tiež \(O(n+q)\). Keď sa nám už nejak podarí vytvoriť tento graf, tak pre každú otázku len stačí pomocou Dijkstry (lebo hrany teraz nemajú všetky dĺžku \(1\)) zistiť vzdialenosť konca a začiatku v čase \(O((n+q) \log{(n+q)}\).

Predpočítanie

Vrcholy budeme vkladať do písmenkového stromu (trie). Začneme so všetkými genómami v koreni. Keď sme v nejakom vrchole trie s nejakou množinou genómov, tak si ju vieme rozdeliť v lineárnom čase od ich počtu na tie, ktoré končia v tomto vrchole, ktoré idú do ľavého podstromu a ktoré do pravého. Kedy je vrchol trie zaujímavý? Ak sa vo vrchole končí nejaký genóm, tak určite je zaujímavý, lebo je to koniec nejakej hrany alebo súvisí z nejakou otázkou. Ak nejaké vrcholy patria do jeho ľavého aj pravého podstromu, tak bude tiež zaujímavý, keďže bude LCA nejakej dvojice vrcholov. Inak je nezaujímavý. Keď si takto rekurzívne spočítame všetky zaujímavé vrcholy, tak sa dá aj jednoducho zistiť, ako vyzerajú hrany medzi nimi. Vždy si len stačí do rekurzívneho volania posielať aj rodiča aktuálneho vrchola a jeho hĺbku.

Toto celé vieme predpočítať v čase \(O((n+q)D)\), lebo v každej z \(D\) vrstiev trie sa nachádza v súčte najviac \(n+q\) prvkov a v každej úrovni vykonáme prácu priamo úmernú počtu prvkov v nej.

Rýchlejšie otázky

V predošlom riešení sme si medzi zaujímavé vrcholy pridali všetkých \(O(q)\) vrcholov, ktoré sa vzťahujú na otázky. Každý z nich ale využijeme len v tej jednej otázke, ku ktorej sa vzťahujú a inak sú zbytočné. Skúsme teda vrcholy \(z_i\) a \(k_i\) pridať medzi zaujímavé len počas danej otázky a potom ich odstrániť.

Ako teraz zistiť odpovede na jednotlivé otázky? Keď budeme hľadať nejaký genóm \(x\) v našej trie zaujímavých vrcholov, tak niekedy narazíme na hranu, na ktorej sa prestane v nejakom znaku zhodovať (ak taká neexistuje, tak to znamená, že \(x\) je v trii a netreba riešiť žiadne špeciálne prípady). Nech táto hrana ide z vrcholu \(a\) do vrcholu \(b\). Teraz nám stačí pridať hrany z \(x\) do \(a\) a z \(x\) do \(b\) so správnou dĺžkou a máme graf, ktorý správne reprezentuje aktuálnu situáciu. Keď toto spravíme pre \(z_i\) a \(k_i\), tak len znova stačí pomocou Dijkstry zistiť ich vzdialenosť.

Keďže graf zaujímavých vrcholov teraz bude mať len \(O(n)\) vrcholov, tak odpovedať na otázku vieme v čase \(O(n \log{n})\). Predpočítanie sa nám nijak nezhoršilo. Finálna časová zložitosť je teda \(O(nD)\) na predpočítanie a \(O(n \log{n})\) na otázku.

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

vector<string> zaujimave;           // zoznam povodnych zaujimavych genomov
vector<vector<pair<int, int>>> sus; // zoznam susedov vrchola v tvare dvojica {id, dlzka}
                                    // nove vrcholy dostanu id postupne pocas behu programu

struct node {
    node *L, *R;
    string L_edge = "L", R_edge = "R";
    int id;
    node(int ID = -1) {
        L = R = nullptr;
        id = ID;
    }
};

// Funkcia, ktora spocita vzdialenost genomov A a B
// |A| + |B| - 2 LCP(A,B)
int tree_dist(string& a, string& b) {
    int ans = a.size() + b.size();
    int i = 0;
    while (i < a.size() && i < b.size() && a[i] == b[i++])
        ans -= 2;
    return ans;
}

// Bucket sort
// Roztriedi vrcholy z pola cur podla toho, ci maju na dalsom mieste 'L', 'R' alebo uz koncia
void b_sort(vector<int>& cur, int d, vector<int>& L, vector<int>& R, vector<int>& koniec) {
    for (int i : cur) {
        if (zaujimave[i].size() <= d)
            koniec.push_back(i);
        else if (zaujimave[i][d] == 'L')
            L.push_back(i);
        else
            R.push_back(i);
    }
}

// Zisti, ktore treba pridat navyse a vytvory z nich ohodnoteny graf
// cur su indexy aktualnych zaujimavych genomov, ktore sa nachadzaju v podstrome aktualneho vrchola
// edge je postupnost L/R, ktore su na hrane z aktualneho vrchola do jeho otca
// d je aktualna hlbka
// par je index otca
// d_par je hlbka otca
node* generate_graph(vector<int>& cur, string& edge, int d, int par, int d_par) {
    // ak sa v podstrome aktualneho vrchola nenachadzaju ziadne zaujimave genomy,
    // tak tento vrchol nepotrebujeme
    if (cur.size() == 0) {
        edge = "";
        return nullptr;
    }

    node* ret = new node();

    // Budeme prechadzat po strome az kym nenarazime na zaujimavy vrchol
    while (1) {
        vector<int> L, R, koniec;

        // Rozdelime si zaujimave vrcholy podla toho, do ktoreho podstromu patria
        b_sort(cur, d, L, R, koniec);

        // Pridame nulove hrany medzi rovnake koncove vrcholy
        for (int i = 1; i < koniec.size(); i++) {
            sus[koniec[i - 1]].push_back({koniec[i], 0});
            sus[koniec[i]].push_back({koniec[i - 1], 0});
        }

        // Ak sa niektory zo zaujimavych vrcholov konci v tomto vrchole alebo je tento
        // vrchol LCA nejakej dvojice, tak je zaujimavy
        if ((L.size() && R.size()) || koniec.size()) {
            // spocitame si index aktualneho vrchola
            int moj_ind = koniec.size() ? koniec[0] : sus.size();
            ret->id = moj_ind;

            // Ak pridavame novy vrchol
            if (koniec.size() == 0)
                sus.push_back({});

            // Pridame hranu medzi aktualnym vrcholom a otcom s dlzkou d - d_par
            sus[moj_ind].push_back({par, d - d_par});
            sus[par].push_back({moj_ind, d - d_par});

            // Rekurzivne vytvorime pravy a lavy podstrom aktualneho vrchola
            ret->L = generate_graph(L, ret->L_edge, d + 1, moj_ind, d);
            ret->R = generate_graph(R, ret->R_edge, d + 1, moj_ind, d);
            return ret;
        }

        // Aktualny vrchol nie je zaujimavy, teda treba zvysit hlbku a pridat na koniec hrany do
        // otca spravny znak
        if (L.size())
            edge += 'L';
        else
            edge += 'R';
        d++;
    }
}

// Funkcia, ktora najde hranu, na ktorej sa genom s oddeluje z trie. Vracia
// dvojicu {{id vrchneho, vzdialenost k vrchnemu}, {id spodneho, vzdialenost k spodnemu}}
pair<pair<int, int>, pair<int, int>> find(string& s, node* cur, int d = 0) {
    string match;
    node* next;

    // Zistime, do ktoreho podstromu patri genom s
    if (s[d] == 'L') {
        next = cur->L;
        match = cur->L_edge;
    } else {
        next = cur->R;
        match = cur->R_edge;
    }

    // Postupne skontrolujeme znaky na hrane do tohto podstromu
    for (int i = 0; i < match.size(); i++) {
        // Genom s moze skoncit niekde v strede tejto hrany
        if (s.size() <= d + i) {
            // Vzdialenost k vrchnemu vrcholu je pocet prejdenych znakov (i)
            // Vzdialenost k spodnemu vrcholu je dlzka hrany - pocet prejdenych znakov
            return {{cur->id, i}, {next->id, match.size() - i}};
        }
        // Genom sa moze prestat zhodovat niekde v strede hrany
        if (match[i] != s[d + i]) {
            // Vzdialenost od konca genomu s k vrcholu, v ktorom sa prestane zhodovat s triou
            int dist = s.size() - d - i;
            // Vzdialenosti k vrchnemu a spodnemu vrcholu spocitame rovnako, len pridame
            // vzdialenost k vrcholu, kde sa s oddeluje od trie
            return {{cur->id, dist + i}, {next->id, dist + match.size() - i}};
        }
    }

    // Neexistuje dalsi vrchol, genom s sa teda prestal zhodovat s triou v nejakom liste
    if (next == nullptr)
        return {{cur->id, s.size() - d - match.size()}, {0, 1 << 30}};

    // Rekurzivne sa zavolame na dalsi vrchol
    return find(s, next, d + match.size());
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    sus.resize(2 * n);
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        zaujimave.push_back(a);
        zaujimave.push_back(b);

        // Pridame barterove hrany
        sus[2 * i].push_back({2 * i + 1, 1});
        sus[2 * i + 1].push_back({2 * i, 1});
    }

    vector<int> cur(2 * n);
    // iota naplni vektor cur postupne cislami 0, 1, 2, ...
    iota(cur.begin(), cur.end(), 0);

    // Vytvorime si koren trie
    node* tr = new node();

    vector<int> R, L, koniec;
    b_sort(cur, 0, L, R, koniec);
    tr->id = sus.size();
    sus.push_back({});

    // Vytvorime lavy a pravy podstrom korena
    tr->L = generate_graph(L, tr->L_edge, 1, tr->id, 0);
    tr->R = generate_graph(R, tr->R_edge, 1, tr->id, 0);

    // Pre kazdu otazku spustime Dijkstru na vytvorenom grafe
    for (int i = 0; i < q; i++) {
        string a, b;
        cin >> a >> b;
        // Najdeme hranu, kde hrany, kde sa a a b v trii prestavaju zhodovat
        auto a_edge = find(a, tr), b_edge = find(b, tr);

        // Pole vzdialenosti, -1 znamena, ze sme este vrchol nepreskumali
        vector<int> dist(sus.size(), -1);

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;

        // Do prioritnej fronty pridame horny aj spodny vrchol hrany, v ktorom
        // sa vrchol a prestava zhodovat
        que.push({a_edge.f.s, a_edge.f.f});
        que.push({a_edge.s.s, a_edge.s.f});

        // Obycajny Dijkstrov algoritmus
        while (!que.empty()) {
            int d, a;
            tie(d, a) = que.top();
            que.pop();
            if (dist[a] != -1)
                continue;
            dist[a] = d;
            for (auto u : sus[a]) {
                if (dist[u.f] == -1)
                    que.push({u.s + d, u.f});
            }
        }

        // Odpoved je minimum zo vzdialenosti a, b a najkratsej cestu v strome
        int ans = tree_dist(a, b);

        // Skusime najprv horny vrchol hrany, kde sa odpaja b a potom spodny vrchol tejto hrany
        ans = min(ans, dist[b_edge.f.f] + b_edge.f.s);
        ans = min(ans, dist[b_edge.s.f] + b_edge.s.s);

        cout << ans << "\n";
    }
}

Ešte rýchlejšie otázky

K zrýchleniu otázok nám stačí jednoduché pozorovanie. Keďže náš strom genómov má hĺbku najviac \(D\), tak maximálna možná vzdialenosť dvoch vrcholov bude \(2D\). Pri Dijkstre teda nemusíme používať prioritnú frontu, stačí nám pole obyčajných front veľkosti \(2D\). Vrcholy budeme vyberať zo začiatku prvej neprázdnej fronty a keď vkladáme nový vrchol vzdialený od počiatočného \(i\), tak ho vložíme do \(i\)-tej fronty. Takýmto spôsobom prejdeme vrcholy od najbližších po najvzdialenejšie (teda rovnako, ako pri použití prioritnej fronty). Navyše vkladať aj vyberať¹ z tejto dátovej štruktúry vieme v konštantnom čase.

Pomocou tejto optimalizácie vieme odpovedať na otázky v čase \(O(n)\) a časová zložitosť predpočítania sa nijak nezhoršila. Výsledná časová zložitosť je teda \(O((n + q)D + qn)\).