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;
}