• Lista de probleme
• Tequila
• Ultimul Cartus
• Prea Simplu!

Tequila

Firma este, de fapt, un arbore cu radacina. Vom calcula pentru fiecare nod , nivelul sau in arborele (radacina va avea nivelul ). Astfel, solutia va fi .
Pentru a intelege formula mai bine, sa consideram un nod si sa incercam sa calculam probabilitatea ca acesta sa fie ales de catre "Zetul". Cand Zetul va alege la intamplare un nod , vom avea 2 cazuri:

1. nu se afla pe drumul de la radacina la . In acest caz, vom sterge subarborele lui si Zetul va alege alt .
2. se afla pe drumul de la radacina la . In acest caz, probabilitatea ca nodul sa fie chiar nodul este (Exista noduri pe drumul ), deci Zetul va bea shot-uri de tequila cu probabilitatea .

O operatie de update se va rezolva in , deoarece la raspuns vom adauga , iar mai apoi vom actualiza cu .

Complexitate finala:

Ultimul Cartus

• Vom considera, in primul rand, ca cele dosare sunt numerotate de la la in locul variantei preferate in enunt pentru simplitate in explicarea solutiei. Sa notam cu permutarea solutie corespunzatoare unui .

Se observa printr-o cautare de tip brute-force a rapunsurilor pentru primele cateva cazuri (i.e. ) ca:

1. Solutia este unica (deci conditia de minim lexicografic nu mai reprezinta o dificultate);
2. se obtine din .

• Analizand cele doua jumatati ale lui , adica si, respectiv, observam ca ordinea relativa a elementelor este aceasi si, mai mult, este data de . Mult mai usor de observat, prima jumatate contine toate elementele impare, iar a doua toate elementele pare.

• Intuim astfel ca , lucru pe care il putem verifica foarte usor trimitand o sursa pentru subtaskul .

• Intr-adevar, este adevarat pe cazul general prin inductie ca .

• Generarea efectiv recursiva a permutarii dupa regula de mai sus si rularea functiei asupra ei pentru a-i calcula costul are complexitatea timp (desi la prima vedere ar putea parea ) si este suficienta pentru obtinerea a din punctaj.

Calcularea variabilei poate fi simplificata daca ne punem mai intai problema numarului de swap-uri facut de fiecare apel al functiei in parte. Pentru exemplificare vom lua cazul :

operatii

operatii

operatii

operatii

opearatii

operatii

Sirul diferentelor de ordin al sirului este , care este chiar sirul puterilor de .

• Variindu-l pe , observam ca in general primul termen al sirului valorilor este intotdeauna , iar sirul diferentelor de ordin este dat de sirul puterilor de , incepand cu (a nu se uita ca este putere de ). 

• Aceaste observatii ne sunt suficiente pentru a scrie o functie de calculare a costului pentru un dat ce ruleaza in timp :

//Returneaza log2(N) 
int GetBits(int N) {
    int bits = -1;
    while (N) {
        ++ bits;
        N /= 2
    }

    return bits;
}

//Returneaza costul permutarii optime de lungime N
long long int GetCost(int N) {
    int K = GetBits(N); //N = 2 ^ K

    long long int sum = N / 2; //Rapunsul curent
    long long int ops = N / 2; //Termenul curent din sirul ops
    long long int dif = N / 4; //Termenul curent din sirul diferentelor de ordin 1
    
    //Generam sirul ops si ii calculam suma elementelor
    for (int i = 2; i <= K; ++ i) {
        ops += dif;
        sum += ops;
        dif *= 2;
    }

    return sum;
}

• Combinand constructia recursiva a sirului cu functia anterior prezentata obtinem o solutie de complexitate totala , suficienta pentru obinerea a din punctaj.

• Pentru punctaj MAXIM ( de puncte) trebuie sa calculam doar cele pozitii cerute din . Putem scrie o functie recursiva ce returneaza elementul , bazandu-ne pe definitia recursiva a lui data mai sus, in timp .

• BONUS! Fie numarul obtinut prin inversarea ordinii bitilor numarului , atunci .

Complexitatea totala:

Prea Simplu!

• Aceasta problema se voia a fi cea mai grea din concurs si se pare ca si-a facut bine datoria in aceasta calitate.

• Primele doua subtaskuri se rezolva prin abordari de backtracking si, respectiv, dinamica pe stari. Nu vom insista foarte mult asupra acestor abordari.

• Pentru ultimele trei subtaskuri avem nevoie un algoritm de rezolvare polinomial. Mai exact, cautam o formula pentru rezultat.

• Incepem rezolvarea solutia propriu-zisa printr-o prin cea mai importanta observatie pentru rezolvarea problemei:

Sirurile binare ce se pot obtine folosind maxim operatii de sunt acelea si numai acelea ce au maxim intervale maximale de caractere neintrerupte.

• Demonstratie:

1. "Sirul are maxim intervale neintrerupte de Sirul se poate obtine"
   • Putem folosi cate un pentru fiecare dintre cele maxim intervale maximale de .
2. "Sirul are maxim intervale neintrerupte de Sirul se poate obtine"
   • Fie o succesiune arbitrara de operatii de . Sa ne imaginam ca dupa fiecare operatie vom insera separatori, reprezentati prin caracterul intre elementele si si, respectiv, intre elementele si . Sa luam un exemplu cu si :
     Sirul initial este: 0 0 0 0 0 0 0 0 0 0
     Dupa operatia sirul este:  0|1 1 1|0 0 0 0 0 0
     Dupa operatia sirul este: 0|1|0 0|1 1 1 1 1 1| 
     Dupa operatia sirul este: |1|0|1 1|1 1 1 1 1 1|
     Dupa operatia sirul este: |1|0|1 1|1 1 1|0|1 1|
   • A se observa ca pot exista separatori atat intre elementele sirului, cat si la capetele sale (in total exista pozitii unde pot fi pusi separatori). Daca consideram toate intervalele de elemente ale sirului situate intre separatori consecutivi, observam ca valoarea sirului este constanta pe fiecare interval in parte (o variatie in valoare ar implica existenta unui separator inauntru - acel separator ce creeaza discrepanta, deci cei separatori nu ar mai fi consecutivi).
   • Cum dupa operatii de flip pot exista maxim separatori unici, inseamna ca numarul total de intervale cuprinse intre 2 separatori consecutivi poate fi maxim . Numarul maxim de intervale neintrerupte de se obtine daca dintre intervalele dintre 2 separatori consecutivi incepand cu primul contin valoarea , iar restul valorilor sirului sunt setate pe (nu avem cum sa alegem dintre intervalele dintre separatori consecutivi astfel incat nicicare 2 sa nu fie adiacente). A se preciza ca am omis tratarea cazului cand primul si / sau ultimul separator nu sunt la inceputul / sfarsitul sirului - in acest caz va exista un prefix si / sau sufix implicit plin cu valori de , care nu prezinta interes deosebit.

• Urmatorul pas este reducerea lui "fix operatii de " la "cel mult operatii de ". In acest sens sunt instrumentale tipuri de secvente de operatii de "asteptare":
  1. Dublarea unei operatii de forma , efectiv anuland-o (astfel putem transforma problema intr-una de paritate)
  2. Transformarea unei operatii de forma , unde in
  3. Transformarea unei operatii de forma , unde in

• Cu toate acestea si sunt particulare si trebuie tratate ca atare!

• Tot ce mai ramane de facut este calcularea numarului de siruri cu maxim intervale neintrerupte de . Sa presupunem ca vom itera valoarea lui prin toate valorile naturale nenule mai mici sau egale cu - asa ca ne intereseaza numarul de siruri cu fix intervale de . Pentru a le numara pe acestea, vom apela din nou la analogia cu separatorii (de data aceasta vom considera toti cei separatori)- un interval de valori poate fi reprezentat bijectiv printr-un interval de separatori (pentru o mai buna intelegere, daca numerotam separatorii cu numere naturale consecutive de la la , sirul 0001111001001101, este reprezentat de intervalele de separatori , , , ).

• Fie cele intervale de separatori si sirul . Contitiile necesare si suficiente pentru ca S sa reprezinte un sir binar de interes sunt date de sirul de inecuatii . Pentru a numara toate sirurile S trebuie sa numaram toate felurile de a alege numere naturale distincte cuprinse intre si . Prin definitie, vorbim despre .

• Asadar, toata problema se reduce la a calcula .

• Pentru din punctaj putem calcula combinarile folosind Triunghiul lui Pascal, generat de identitatea . Pentru a ne incadra in memorie si timp, va trebui sa alocam dinamic cate o matrice de pentru fiecare test si sa-i calculam elementele in timp proportional cu marimea ei.

• Pentru din punctaj ne vom folosi de identitatea pentru a parcurge randul din Triunghiul lui Pascal element cu element si a aduna fiecare al doilea element la suma actuala, totul in timp . Cea mai dificila parte a acestui procedeu este impartirea modulara prin - acest lucru se poate face calculand inversul multiplicativ al lui la fiecare pas folosindu-ne de faptul ca este atat prim cat si foarte mare, deci mereu prim cu . Mai exact, din Mica Teorema a lui Fermat stim ca , deci , adica este, prin definitie, inversul modular al lui . In particular, pentru o valoare fixata, inversul ei modulo este dat de , expresie ce se poate calcula prin exeponentiere rapida in timp .

• Partea cu adevarat grea a problemei se voia a fi trecerea de la puncte la puncte. Se va merge pe aceeasi idee ca la solutia de , doar ca se va evita aducerea in discutie a numerelor care nu au invers modular (i.e. adica acele numere care nu sunt prime cu ). Astfel exista doua solutii:
  1. Mentinem numarul curent (adica ) intr-un arbore de intervale cu factorii sai primi, implementand operatorii * si / adaugand factori si, respectiv, eliminand factori prin operatii de update (fiecare nod mentine numarul modulo in conditiile in care consideram doar factorii primi din intervalul nodului curent). Nu vom insista foarte mult asupra acestei solutii deoarece este intrinsec mai lenta decat a doua. Se pot lua de puncte cu aceasta abordare daca o optimizam foarte mult: implementam iterativ arborele de intervale, precalculam puterile factorilor primi si facem diverse optimizari de constanta.
  2. Vom incerca sa nu ne departam chiar atat de mult de ideea de invers modular. Stim ca un numar cu proprietatea ca are invers modular; ceea ce ne deranjeaza pe noi sunt factorii primi comuni cu modulul - daca pe acestia i-am trata separat problema ar fi rezolvata. Prin urmare vom mentine un numar ca pe o pereche , unde facts[] contine puterile factorilor primi din ce se gasesc in descompunerea lui , iar reprezinta valoarea modulo a celorlalti factori primi, combinati intr-un singur numar (acest numar are cu siguranta invers modular, deci nu ne intereseaza prea mult valorile fiecarui factor prim in parte, ci doar produsul lor). Noua implementare de invers modular se va face pe aceeasi idee ca pentru un modul prim, doar ca se va folosi Teorema lui Euler - astfel, inversul modular al unui numar este (alternativ se poate folosi si Algoritmul Extins al lui Euclid).

• Prezentam mai jos o implementare a clasei Integer suficienta pentru punctaj MAXIM, ce mentine un numar sub forma explicata mai sus. Mentionam ca smenul este reutilizabil in multe cazuri in care se doreste impartirea cu numere in contextul aritmeticii modulare cu modul neprim.

class Integer {
public:
    //Pregateste clasa pentru interactiunea cu un modul - ii calculeaza phi-ul si descompunerea in factori primi
    static void prepare_MOD(int mod) {
        MOD = mod;
        phi = MOD;
        p_sz = 0;
        memset(p, 0, sizeof p);
        for (int i = 2; i * i <= mod; ++ i)
            if (mod % i == 0) {
                p[p_sz ++] = i;
                phi /= i;
                phi *= (i - 1);
 
                while (mod % i == 0)
                    mod /= i;
            }
 
        if (mod > 1) {
            p[p_sz ++] = mod;
            phi /= mod;
            phi *= (mod - 1);
            mod = 1;
        }
    }
 
    Integer() {
        memset(k, 0, sizeof k);
        val = 1;
    }
 
    Integer(const int &arg) {
        memset(k, 0, sizeof k);
        val = arg;
        for (int i = 0; i < p_sz; ++ i) {
            while (val % p[i] == 0) {
                val /= p[i];
                ++ k[i];
            }
        }
        val %= MOD;
    }
 
    Integer operator*(const Integer &arg) const {
        Integer ans;
        for (int i = 0; i < p_sz; ++ i)
            ans.k[i] = k[i] + arg.k[i];
        ans.val = (1LL * val * arg.val) % MOD;
        return ans;
    }
 
    Integer operator/(const Integer &arg) const {
        Integer ans;
        for (int i = 0; i < p_sz; ++ i)
            ans.k[i] = k[i] - arg.k[i];
        ans.val = (1LL * val * inv(arg.val)) % MOD;
        return ans;
    }
    
    //Returneaza numarul complet - cu tot cu factorii primi tinuti separat
    int to_int() {
        int ans = val;
        for (int i = 0; i < p_sz; ++ i)
            ans = (1LL * ans * expo(p[i], k[i])) % MOD;
        return ans;
    }
private:
    static const int FACTMAX = 9;
    static int MOD;
    static int phi;
    static int p[FACTMAX];
    static int p_sz;
    
    //Returneaza a ^ b prin exponentiere rapida
    static int expo(int a, int b) {
        if (!b)
            return 1 % MOD;
        else if (b & 1)
            return (1LL * expo(a, b - 1) * a) % MOD;
        else {
            int aux = expo(a, b >> 1);
            return (1LL * aux * aux) % MOD;
        }
    }
    
    //Returneaza inversul modular al lui x
    static int inv(int x) {
        return expo(x, phi - 1);
    }
 
    //X = (facts, val) 
    int k[FACTMAX]; // = facts
    int val;
};
 
int Integer :: MOD;
int Integer :: phi;
int Integer :: p[FACTMAX];
int Integer :: p_sz;

• Optimizari posibile: precalcularea puterilor tuturor factorilor primi din descompunerea lui , precalcularea inverselor modulare in timp liniar. Cu aceste optimizari viteza aproape ca se dubleaza.

Complexitate totala: