6. Objednaná elektronika vzorové riešenie

5
1 12 3 4 3

2

6
1 1 1 1 1 1

15

10
1 2 3 4 5 6 7 8 9 10

0

Hrubá sila

Máme zistiť, koľko rôznych kombinácií štyroch čisel zo vstupu je dobrých. Teda, koľko je štvoríc \((A, B, C, D)\) takých, že \(x_A \cdot x_B = x_C \cdot x_D\) a \(1 \leq A < B < C < D \leq n\). Spravíme to teda prvým spôsobom, ktorý nás napadne – vyskúšame všetky štvorice. Tento bruteforce spravíme vnorením štyroch for-cyklov a jeho časová zložitosť je \(O(n^4)\).

Nepočítajme nič dvakrát

Problém s naším riešením je, že veľa vecí v ňom počítame stále dookola. Pre každú kombináciu indexov \(A, B\) totiž raz prejdeme celý zvyšok poľa, kde kontrolujeme súčin čísel na pozíciách \(C, D\). Ak by sme vedeli využiť informáciu o súčinoch \(C, D\) viackrát, bez prechádzania poľa, mohli by sme náš algoritmus výrazne zrýchliť.

Rovnako dobré by bolo, keby sme vedeli rýchlo nájsť počet dvojíc indexov \(A, B\) pre konkrétne \(C, D\).

Vezmime si nasledujúce riešenie hrubou silou: postupne vyberáme dvojice \(C, D\), a pre ne počítame výskyty dvojíc \(A, B\) s rovnakým súčinom.

Zo zadania vieme, že \(A, B\) sú vždy naľavo od \(C, D\). Náš algoritmus teda prejde všetky dvojice čísel naľavo od \(C\) a porovná ich súčin s \(x_C \cdot x_D\). Keď prejde všetky, tak si posunie \(D\) doprava a začne počítať od začiatku. Keď program doráta všetky \(D\), tak si posunie \(C\), nastaví nové \(D\) na \(C+1\) a znova prezerá dvojice \(A, B\) a posúva \(D\), kým skontroluje všetky.

Pozrime sa na výpočet pre konkrétne \(C\). Všimnime si, že pre každé \(D\) hľadáme jemu príslušné \(A, B\) medzi tými istými číslami. Nám však stačí, ak si na začiatku raz predrátame počet výskytov súčinov \(x_A \cdot x_B\). Potom už pre jednotlivé \(D\) vieme rýchlo zistiť, koľko dvojíc \(A, B\) má súčin \(x_C \cdot x_D\).

Takto si pre každé \(C\) najprv spočítame počty dvojíc \(A, B\) s rôznymi súčinmi, uložíme si počty do nejakej dátovej štruktúry a potom stačí posúvať \(D\) a rýchlo vyberať z dátovej štruktúry počty dvojíc s daným súčinom \(x_C \cdot x_D\). Ak by sme odhadli čas vkladania/výberu z dátovej štruktúry ako \(O(t)\), mohli by sme odhadnúť čas potrebný pre tento algoritmus ako \(O\left(n \cdot (tn^2 + tn)\right) = O(tn^3)\).

Keď už sme zrýchlili výpočet pri posúvaní \(D\), pozrime sa, čo vieme zlepšiť na posúvaní \(C\). Tu si môžeme všimnúť, že po posunutí \(C\) sú počty súčinov vľavo od neho skoro také isté, ako pri starom \(C\). Všetko, čo sa stalo je, že sme pridali súčiny so starým \(C\) – možnosti, kde sa vybrané \(B\) rovná starému \(C\). Teda keď si posunieme \(C\), tak nemusíme zahodiť všetky predpočítané súčiny, ale stačí k nim pridať tieto nové.

Pre každé \(C\) si teda do dátovej štruktúry najprv pridáme súčiny dvojíc prvkov na pozíciách \(A\) a starého \(C\) a potom opäť posúvame \(D\) a vyberáme záznamy o počtoch dvojíc s požadovaným súčinom, čo trvá \(O(tn + tn)\). Čas tohto algoritmu vieme odhadnúť ako \(O\left(n \cdot (tn + tn)\right) = O(tn^2)\).

Ako si pamätať počty dvojíc s rovnakými súčinmi?

Už len zostáva vymyslieť, ako si počet súčinov zapamätáme – akú dátovú štruktúru použijeme. Najjednoduchšie by bolo ukladať si počty do poľa, kde index bude hodnota súčinu. Avšak súčiny môžu nadobúdať hodnoty až \(10^{18}\), a pole s takouto veľkosťou sa nám do pamäte nezmestí. Čísel na vstupe je ale najviac \(1\,000\), čiže rôznych súčinov bude najviac \(10^6\). Ak by sme použili pole, väčšina indexov by teda mala hodnotou \(0\), a sem-tam by sa nám tam objavila iná hodnota.

Našťastie, problém, ako si zapamätať a rýchlo pracovať s rozumne malým počtom (\(10^6\)) veľkých záznamov, už niekto vyriešil. Použijeme dátovú štruktúru map, ktorá nám dovolí ukladať si dvojice <súčin, počet dvojíc indexov A, B s daným súčinom> tak, ako budeme potrebovať, ale nebude si zbytočne ukladať hodnoty, ktoré nepotrebujeme.

Zložitosť

Podľa toho, či si zvolíme implementáciu mapy ako binárneho vyhľadávacieho stromu (map) alebo ako hashovacej tabuľky (unordered_map) dostaneme časovú zložitosť vkladania/upravovania/čítania \(t = O(\log n)\) alebo \(t=O(1)\), teda celkovo \(O(n^2 \log n)\) alebo \(O(n^2)\), keď použijeme predošlé odhady.

Pre pamäť si zoberieme najhorší prípad. Ak sú súčiny čísel na vstupe rôzne, tak si musíme do mapy uložiť \(n(n-1)\) čísel. Pamäťová zložitosť bude teda \(O(n^2)\)

#include <iostream>
#include <vector>
#include <map>

using namespace std;

// vyrobime si mapu na suciny
map<long long, long long> suciny;

// pridavanie sucinu do mapy
void pridaj_sucin(long long key){
    if(suciny.find(key)==suciny.end()){
        suciny[key]=1;
    }else{
        suciny[key]++;
    }
}

// hladanie poctu vyskytov sucinu v mape
long long najdi_pocet(long long key){
    if(suciny.find(key)!=suciny.end()){
        return suciny[key];
    }else{
        // ak sucin nie je v mape, tak sme ho este nikde nevideli
        return 0;
    }
}

int main(){
    // nacitame vstup
    int n;
    cin >> n;
    vector<long long> vstup(n);
    for (int i=0; i<n; i++){
        cin >> vstup[i];
    }

    long long result = 0;

    // postupne prejdeme vsetky C
    for (int c=0; c<n; c++){

        // postupne prejdeme D a najdeme pocet sucinov C*D v mape
        for (int d=c+1; d<n; d++){
            result += najdi_pocet(vstup[c]*vstup[d]);
        }

        // pridame nove suciny do mapy
        for (int d = 0; d<c; d++){
            pridaj_sucin(vstup[c]*vstup[d]);
        }
    }

    //vypiseme vysledok
    cout << result << endl;
    return 0;
}