Tmp 10

Probleme cu arbori de intervale

Subsecventa maximala cu elemente egale

Enunt

Se da un vector $v$ cu $n$ elemente. Asupra sirului efectuam urmatoarele operatii:

a) update: elementul de pe o anumita pozitie isi schimba valoarea

b) query: sa se afiseze lungimea maxima a unei subsecvente de elemente egale

Solutie

Aceasta problema poate fi rezolvata usor folosind arbori de intervale, intr-un mod asemanator problemei "subsecventa de suma maxima". Astfel, pentru fiecare nod din arborele de intervale tinem minte subsecventa de lungime maxima care are elemente egale, prefixul maximal, respectiv sufixul maximal. La combinarea a doua noduri din arbore, alegem ori subsecventa complet inclusa in unul din noduri, ori o comnbinatie dintre prefix si sufix, in cazul in care acestea se potrivesc.

Raspunsul la query-uri se va afla mereu in radacina arborelui de intervale.

Complexitatea algoritmului:

$O(logN)$ pentru fiecare update

$O(1)$ pentru fiecare query

Subsecventa maximala progresie aritmetica

Enunt

Se da un vector $v$ cu $n$ elemente. Asupra sirului efectuam urmatoarele operatii:

a) update: elementul de pe o anumita pozitie isi schimba valoarea

b) query: sa se afiseze lungimea maxima a unei subsecvente care este si progresie aritmetica

Solutie

Cum progresia aritmetica reprezinta o sebsecventa in care diferenta dintre oricare doua elemente consecutive este constanta, construim un vector auxiliar, vectorul $dist$ , unde tinem minte diferenta dintre elementele consecutive ale vectorului.

Acum problema se reduce la a gasi lungimea maxima a unei subsecvente care are toate elementele egale, ceea ce am rezolvat anterior.

Observatie: La update vom modifica doua valori din vectorul diferentelor

Complexitatea algoritmului:

$O(logN)$ pentru fiecare update

$O(1)$ pentru fiecare query

Lantul maximal progresie aritmetica

Enunt

Se da un arbore cu $n$ noduri. Fiecare nod are asociata o anumita valoare $v[i]$ .

Sa se calculeze lungimea maxima a unui lant progresie aritmetica si sa se afiseze capetele unuia.

Solutie

Consideram ca nodul 1 este radacina arborelui dat.

Atribuim fiecarei muchii o valoare C = v[tata] - v[fiu].

Fie (A, B) un lant oarecare, iar L lca-ul acestora. Observam ca (A, B) este o progresie aritmetica daca si numai daca:

a) (A, L) este o progresie aritmetica, iar toate valorile muchiilor din (A, L) sunt egale cu X.

b) (B, L) este o progresie aritmetica, iar toate valorile muchiilor din (B, L) sunt egale cu Y.

c) X = -Y

Printr-o parcurgere DFS construim urmatorul vector:

$d[i]=$ lungimea maxima a unui lant care incepe din nodul i si continua in subarborele sau, unde toate muchiile de pe lant au valoarea egala cu valoarea muchiei dintre nodul i si tatal sau.

Pentru a construi vectorul, la fiecare pas al dfs-ului aflam recursiv valorile din fii, apoi, daca muchia dintre nodul curent si fiu are valoarea egala cu cea dintre nodul curent si tata, d[i] = std::max(d[i], 1 + d[fiu]). Initial, toate elementele vectorului au valoarea egala cu 1.

Dupa ce am construit acest vector trebuie ca, pentru fiecare nod, sa aflam cum putem combina doua lanturi verticale in jos, unul cu ratia egala cu opusul ratiei celuilalt. Cazul in care ratia este egala cu 0 se va trata separat.

Parcurgem toti fiii nodului curent si, pentru fiecare valoare negativa, introducem intr-un hash perechi de tipul {valoare[muchie], d[fiu]}. Apoi, pentru fiecare valoare pozitiva, ii cautam in hash opusul si vedem care este lungimea maxima a unui lant care se poate obtine. La final, golim hash-ul folosind o stiva a operatiilor sau parcurgand intr-o anumita ordine elementele introduse.

Complexitate: $O(N)$

Cabana2

Enunt

https://infoarena.ro/problema/cabana2

Solutie

Sortam toate punctele crescator dupa x, iar la egalitate dupa y. Separam punctele in mai multe grupe dupa x. Observam ca punctele de pe latura dreapta a oricarui dreptunghi vor fi puncte consecutive dintr-o anumita grupa.

Prin urmare, pentru fiecare astfel de pereche de puncte $(O(n)perechi)$ , dorim sa determinam daca exista un dreptunghi care sa aiba latura dreapta formata din ele.

Daca parcurgem grupele crescator dupa x, se observa ca varful stanga-sus al dreptunghiului va fi ultimul punct care a aparut pe acelasi y ca si coltul dreapta-sus. Analog, coltul stanga-jos este ultimul punct care a aparut pe acelasi y ca si coltul dreapta-jos. Pentru ca cele 4 puncte astfel obtinute sa fie valide, trebuie ca cele doua puncte din stanga sa aiba acelasi x, iar pentru fiecare y intre y-urile varfurilor, ultima aparitie a unui punct sa fie inainte de x-ul laturii stanga. Cu alte cuvinte, maximul aparitiilor dintre y-urile varfurilor sa fie mai mic decat x-ul laturii stanga.

Astfel, vom tine minte un arbore de intervale in care sa tinem minte ultima aparitie a unui punct cu un anumit y. Pentru fiecare grupa, pentru fiecare pereche de varfuri consecutive, determinam ultimele puncte aparute la aceleasi y-uri. Daca x-urile lor coincid, dorim ca minimul din aint dintre y-ul varfurilor sa fie mai mic strict decat acest x.

#include <bits/stdc++.h>
#define MAXN 50000
 
const long long INF = 1000000000;
int y[1 + MAXN];
int num;
int aint[4 * MAXN];
int pos, val;
inline void update(int p, int st, int dr){
    if(st == dr)
        aint[p] = val;
    else{
        int m = (st + dr) / 2;
        if(pos <= m) update(2 * p, st, m);
        else update(2 * p + 1, m + 1, dr);
        aint[p] = std::max(aint[2 * p], aint[2 * p + 1]);
    }
}
int left, right, ans;
inline int query(int p, int st, int dr){
    if(left <= st && dr <= right)
        ans = std::max(ans, aint[p]);
    else{
        int m = (st + dr) / 2;
        if(left <= m) query(2 * p, st, m);
        if(m + 1 <= right) query(2 * p + 1, m + 1, dr);
    }
}
 
struct Point{
    int x, y, ind;
} v[1 + MAXN];
bool cmpx(Point A, Point B){
    return A.x < B.x || (A.x == B.x && A.y < B.y);
}
bool cmpy(Point A, Point B){
    return A.y < B.y || (A.y == B.y && A.x < B.x);
}
 
int main(){
    FILE*fi,*fo;
    fi = fopen("cabana2.in","r");
    fo = fopen("cabana2.out","w");
 
    int n;
    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++) fscanf(fi,"%d%d", &v[i].x, &v[i].y);
    std::sort(v + 1, v + n + 1, cmpy);
    for(int i = 1; i <= n; i++){
        if(i == 1) v[i].ind = 1;
        else if(v[i].y == v[i - 1].y) v[i].ind = v[i - 1].ind;
        else v[i].ind = v[i - 1].ind + 1;
        y[v[i].ind] = v[i].y;
    }
    num = v[n].ind;
    for(int i = 1; i <= n; i++){
        pos = i, val = - INF - i;
        update(1, 1, num);
    }
 
    std::sort(v + 1, v + n + 1, cmpx);
    long long Smax = 0LL;
    for(int i = 1; i <= n;){
        int p = i, u = i;
        while(u <= n && v[u].x == v[p].x) u++;
        u--;
        for(int a = p + 1; a <= u; a++){
            left = v[a - 1].ind, right = v[a - 1].ind, ans = - 2 * INF;
            query(1, 1, num);
            int x1 = ans;
            left = v[a].ind, right = v[a].ind, ans = - 2 * INF;
            query(1, 1, num);
            int y1 = ans;
            if(x1 == y1){
                if(v[a].ind == v[a - 1].ind + 1) Smax = std::max(Smax, 1LL * (v[a].x - x1) * (y[v[a].ind] - y[v[a - 1].ind]));
                else{
                    left = v[a - 1].ind + 1, right = v[a].ind - 1, ans = - 2 * INF;
                    query(1, 1, num);
                    if(ans < x1) Smax = std::max(Smax, 1LL * (v[a].x - x1) * (y[v[a].ind] - y[v[a - 1].ind]));
                }
            }
        }
        for(int a = p; a <= u; a++){
            pos = v[a].ind, val = v[a].x;
            update(1, 1, num);
        }
        i = u + 1;
    }
    fprintf(fo,"%lld", Smax);
 
    fclose(fi);
    fclose(fo);
    return 0;
}

Siruri cu recurenta liniara de ordin k

Fie $(a_{n})_{n}$ un sir de numere reale, cu urmatoarea recurenta: $a_{n}=x_{1}a_{n-1}+x_{2}a_{n-2}+\cdots +x_{k}a_{n-k}$ .

Dorim sa determinam al n-lea termen al sirului.

O prima solutie este cea banala, si anume sa calculam pe rand toate elementele sirului pana la n, folosind recurenta din enunt. Astfel, obtinem o complexitate de $O(n)$

Raspunsul poate fi aflat insa mult mai repede, folosind exponentierea rapida de matrice dupa cum urmeaza.

Inmultirea matricelor

Pentru inceput, definim ${\mathcal {M}}_{m,n}(\mathbb {C} )$ ca fiind multimea matricelor cu m linii si n coloane. O matrice $A\in {\mathcal {M}}_{m,n}(\mathbb {C} )$ arata in felul urmator: $A={\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots &a_{1,n}\\a_{2,1}&a_{2,2}&\cdots &a_{2,n}\\\cdots \\a_{m,1}&a_{m,2}&\cdots &a_{m,n}\\\end{pmatrix}}$

Definim operatia de inmultire a doua matrice in felul urmator:

Fie $A\in {\mathcal {M}}_{m,n}(\mathbb {C} )$ si $B\in {\mathcal {M}}_{n,p}(\mathbb {C} )$ . Atunci, matricea $C\in {\mathcal {M}}_{m,p}(\mathbb {C} )$ calculata astfel: $C_{i,j}=\sum _{i=1}^{n}A_{i,k}B_{k,j}$ reprezinta produsul matricelor A si B.

Aflarea termenilor unui sir cu recurenta liniara

Consideram matricea coloana $C_{n}={\begin{pmatrix}a_{n}\\a_{n-1}\\\cdots \\a_{n-k+1}\\\end{pmatrix}}$

Observam urmatoarea relatie de recurenta intre $C_{n}$ si $C_{n-1}$ : $C_{n}={\begin{pmatrix}x_{1}&x_{2}&\cdots &x_{k}\\1&0&\cdots &0\\0&1&\cdots &0\\\cdots \\0&\cdots &1&0\\\end{pmatrix}}C_{n-1}$

Astfel, prin inductie, obtinem urmatoarea relatie de recurenta: $C_{n}={\begin{pmatrix}x_{1}&x_{2}&\cdots &x_{k}\\1&0&\cdots &0\\0&1&\cdots &0\\\cdots \\0&\cdots &1&0\\\end{pmatrix}}^{n-k}C_{k}$

Prin urmare, daca putem calcula intr-un timp cat mai bun puterea a n-a a matricei, putem afla al n-lea termen al sirului.

Observatie: $C_{k}$ trebuie calculat manual.

Exponentierea matricelor in timp logaritmic

Inmultirea matricelor in timp logaritmic se bazeaza pe aceeasi idee ca exponentierea numerelor in timp logaritmic. Acesta este codul pentru problema kfib de pe infoarena.

#include <bits/stdc++.h>
#define MOD 666013

long long F[2][2]={{1,1}, {1,0}};
long long fib(int n){
    if(n == 0) return 0;
    power(n-1);
    return F[0][0];
}
 
void power(int n){
    if(n != 0 && n != 1){
        long long M[2][2] = {{1,1}, {1,0}};
        power(n / 2);
        multiply(F);
        if(n % 2 != 0)
            multiply(M);
    }
}
 
void multiply(long long M[2][2]){
    long long x, y, z, w;
    x = (F[0][0]*M[0][0] + F[0][1]*M[1][0])%MOD;
    y = (F[0][0]*M[0][1] + F[0][1]*M[1][1])%MOD;
    z = (F[1][0]*M[0][0] + F[1][1]*M[1][0])%MOD;
    w = (F[1][0]*M[0][1] + F[1][1]*M[1][1])%MOD;
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
 
int main(){
    FILE*fi,*fo;
    fi = fopen("kfib.in","r");
    fo = fopen("kfib.out","w");

    int k;
    fscanf(fi,"%d", &k);
    fprintf(fo,"%lld", fib(k));
 
    fclose(fi);
    fclose(fo);
    return 0;
}

Range Minimum Query

Enunt

https://infoarena.ro/problema/rmq

Solutie

Pentru fiecare element, vrem sa precalculam valoarea minima aflata intr-o subsecventa care incepe cu elementul respectiv si are lungimea $2^{j}$ , pentru fiecare j posibil. Apoi, cand dorim sa afisam valoarea minima aflata intr-un interval, luam doua subsecvente de aceeasi lungime, putere de 2, maximale pe care le suprapunem astfel incat prima sa inceapa la inceputul intervalului, iar cea de-a doua sa se termine la finalul intervalului (se poate demonstra ca aceste doua subsecvente acopera complet intervalul).

#include <bits/stdc++.h>
#define MAXN 100000
#define MAXLOG 20
 
int v[1 + MAXN];
int rmq[1 + MAXLOG][1 + MAXN];
int lg[1 + MAXN];
int main(){
    FILE*fi,*fo;
    fi = fopen("rmq.in","r");
    fo = fopen("rmq.out","w");
 
    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    for(int i = 1; i <= n; i++) fscanf(fi,"%d", &v[i]);
 
    lg[1] = 0;
    for(int i = 2; i <= n; i++) lg[i] = 1 + lg[i / 2]; //logaritmul in baza 2 al numerelor de la 1 la n
 
    for(int i = 1; i <= n; i++) rmq[0][i] = v[i]; //subsecvente de lungime 1
    for(int i = 1; (1 << i) <= n; i++)
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
            rmq[i][j] = std::min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]); //calculam o subsecventa in functie de prima si de a doua jumatate
 
    for(int i = 1; i <= m; i++){
        int a, b;
        fscanf(fi,"%d%d", &a, &b);
        fprintf(fo,"%d\n", std::min(rmq[lg[b - a + 1]][a], rmq[lg[b - a + 1]][b - (1 << lg[b - a + 1]) + 1])); //comparam cele doua intervale suprapuse
    }
 
    return 0;
}

Ciurul liniar si problema Matrita

Ciurul liniar ne permite sa determinam pentru fiecare numar de la 1 la n daca este prim, cel mai mic divizor prim al sau, precum si indicatorul lui euler (numarul de numere prime mai mici sau egale cu numarul dat care sunt relativ prime cu el).

Algoritmul este urmatorul:

(01) pentru fiecare i de la 2 la n
(02)      daca divprim[i] nu a fost gasit
(03)           prime.push_back(i)
(04)           divprim[i] = i
(05)           phi[i] = i - 1
(06)      pentru fiecare j cu prime[j] < divprim[i]
(07)           divprim[prime[j] * i] = prime[j]
(08)           phi[prime[j] * i] = prime[j] * i * (phi[i] / i) * (1 - 1 / prime[j]) = (prime[j] - 1) * phi[i]
(09)      divprim[divprim[i] * i] = divprim[i]
(10)      phi[divprim[i] * i] = divprim[i] * phi[i]

Complexitatea acestui algoritm este $O(n)$ amortizat pentru ca fiecare numar este parcurs o singura data.

Enunt

https://infoarena.ro/problema/matrita

Solutie

https://infoarena.ro/jc2018/solutii/matrita

///solutie oficiala O(N + sqrt(N) * log(N))
#include <bits/stdc++.h>
#define MAXN 12000000
 
long long MOD;
int ciur[1 + MAXN / 2 + 1];
int phi[1 + MAXN];
int prime[800000], ind;
 
inline int logpow(int a, long long n){
    int p = 1;
    while(n){
        if(n % 2) p = (1LL * p * a) % MOD;
        a = (1LL * a * a) % MOD;
        n /= 2;
    }
    return p;
}
 
int main(){
    FILE*fi,*fo;
    fi = fopen("matrita.in","r");
    fo = fopen("matrita.out","w");
 
    int n;
    fscanf(fi,"%d%lld", &n, &MOD);
 
    int val = n + 1, lim = 1;
    long long exp = 0, ans = 1;
    phi[2] = 1, prime[++ind] = 2;
    for(int i = 2; i <= n; i++){
        if(i % 2){
            if(!ciur[i / 2 + 1]){
                prime[++ind] = i;
                ciur[i / 2 + 1] = i;
                phi[i] = i - 1;
            }
 
            int j;
            for(j = 1; j <= ind && i * prime[j] <= n && prime[j] < ciur[i / 2 + 1]; j++){
                if(prime[j] != 2) ciur[i * prime[j] / 2 + 1] = prime[j];
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
            if(j <= ind && i * prime[j] <= n && prime[j] == ciur[i / 2 + 1]){
                ciur[i * prime[j] / 2 + 1] = prime[j];
                phi[i * prime[j]] = phi[i] * prime[j];
            }
        }
        else if(2 * i <= n)
            phi[i * 2] = phi[i] * 2;
 
        if(i > lim){
            ans = (ans * logpow(val, exp)) % MOD;
            val = n / i, lim = n / val;
            val++, exp = 0;
        }
        exp += phi[i];
    }
    ans = (ans * logpow(val, exp)) % MOD;
    fprintf(fo,"%lld", ((ans * ans) % MOD * (n + 1) % MOD - 1 + MOD) % MOD);
 
    return 0;
}

Problema turelor

Enunt

Se da o tabla de sah cu n linii si n coloane pe care sunt asezate n ture. Sa se determine numarul minim de mutari (miscarea unei ture intr-o pozitie adiacenta) pentru a obtine o configuratie in care sa nu existe doua ture pe aceeasi linie sau aceeasi coloana.

Solutie

Pentru fiecare configuratie posibila de ture fixate, putem determina in timp liniar unde trebuie sa mutam turele ramase pentru a obtine o configuratie buna. Mutarile se vor face independent pe linie si pe coloana deoarece cele doua directii nu se afecteaza reciproc.

Problema Prea Simplu!

Enunt

https://www.infoarena.ro/problema/preasimplu

Solutie

https://www.infoarena.ro/jc2016/runda-2/solutii

#include <bits/stdc++.h>
#define MAXN 300000
 
void gcd(long long &x, long long &y, long long a, long long b){
    if(!b)
        x = 1, y = 0;
    else{
        gcd(x, y, b, a % b);
        long long aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}
 
long long f[2 + MAXN];
int v[2 + MAXN][20];
long long prime[20];
int main(){
    FILE*fi,*fo;
    fi = fopen("preasimplu.in","r");
    fo = fopen("preasimplu.out","w");
 
    int t;
    fscanf(fi,"%d", &t);
    for(int z = 1; z <= t; z++){
        long long n, k, MOD, ans;
        fscanf(fi,"%lld%lld%lld", &n, &k, &MOD);
        if(k == 1)
            fprintf(fo,"%lld\n", (n * (n + 1) / 2) % MOD);
        else if(n == 1)
            fprintf(fo,"%lld\n", 1LL);
        else{
            long long cpy = MOD, cnt = 0;
            for(int d = 2; d * d <= cpy; d++)
                if(cpy % d == 0){
                    prime[++cnt] = d;
                    while(cpy % d == 0) cpy /= d;
                }
            if(cpy != 1)
                prime[++cnt] = cpy;
 
            ans = 0LL;
            f[0] = 1LL;
            for(int i = 1; i <= n + 1; i++){
                long long x = i;
                for(int j = 1; j <= cnt; j++){
                    int e = 0;
                    while(x % prime[j] == 0) x /= prime[j], e++;
                    v[i][j] = e;
                }
                f[i] = (f[i - 1] * x) % MOD;
            }
            for(int i = 1; i <= n + 1; i++)
                for(int j = 1; j <= cnt; j++)
                    v[i][j] += v[i - 1][j];
 
            for(int i = 0; i <= 2 * k && i <= n + 1; i += 2){
                long long tmp = f[n + 1];
 
                long long inv = 0, ins;
                gcd(inv, ins, f[i], MOD);
                if(inv < 0) inv = MOD + inv % MOD;
                tmp = (tmp * inv) % MOD;
 
                inv = 0;
                gcd(inv, ins, f[n + 1 - i], MOD);
                if(inv < 0) inv = MOD + inv % MOD;
                tmp = (tmp * inv) % MOD;
                for(int j = 1; j <= cnt; j++)
                    for(int a = 1; a <= v[n + 1][j] - v[i][j] - v[n + 1 - i][j]; a++)
                        tmp = (tmp * prime[j]) % MOD;
                ans = (ans + tmp) % MOD;
            }
            fprintf(fo,"%lld\n", ans);
        }
    }
 
    return 0;
}

Tema

Tmp 10

Contents

Probleme cu arbori de intervale

Subsecventa maximala cu elemente egale

Enunt

Solutie

Subsecventa maximala progresie aritmetica

Enunt

Solutie

Lantul maximal progresie aritmetica

Enunt

Solutie

Cabana2

Enunt

Solutie

Siruri cu recurenta liniara de ordin k

Inmultirea matricelor

Aflarea termenilor unui sir cu recurenta liniara

Exponentierea matricelor in timp logaritmic

Range Minimum Query

Enunt

Solutie

Ciurul liniar si problema Matrita

Enunt

Solutie

Problema turelor

Enunt

Solutie

Problema Prea Simplu!

Enunt

Solutie

Tema

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools