O altă idee ar fi ca pentru fiecare pereche $(i{~1~}, i{~2~})$ fixată să determinăm perechea optimă $(j{~1~}, j{~2~})$. Dacă avem liniile $i{~1~}$ şi $i{~2~}$ fixate atunci problema se transformă din una bidimensională în una unidimensională. Astfel pentru fiecare coloană $j$ vom considera $b[j]$ ca sumă a elementelor $a[i][j]$ cu proprietatea că $i{~1~} <= i <= i{~2~}$. În exemplul nostru, dacă $i{~1~} = 2$ şi $i{~2~} = 3$, atunci avem $b{~1~} = 9 + (-4)$, $b{~2~} = 2 + 1$, $b{~3~} = (-6) + (-4)$ şi $b{~4~} = 2 + 1$. Pentru a rezolva problema unidimensională folosim unul din algoritmii liniari prezentaţi mai sus, astfel obţinându-se un algoritm de complexitate totală $O(N^3^)$. Acest truc de a fixa două linii pentru a transforma problema în una unidimensională este util în multe probleme pe matrice sau cu puncte în plan.
Cel mai bun algoritm cunoscut pentru această problemă are complexitatea <tex>O(N^{3\sqrt{\frac{\log \log N}{\log N}}})</tex> si este mai mult un algoritm teoretic decat unul practic, usor implementabil.
Cel mai bun algoritm cunoscut pentru această problemă are complexitatea <tex>O(N^{3\sqrt{\frac{\log \log N}{\log N}}})</tex> şi este mai mult un algoritm teoretic decât unul practic, uşor implementabil.
h2(#prob3). Problema 3 ({_Interogare_}) - Bursele Agora 2005/2006 Runda 1
h2(#prob3). Problema 3 ( _Interogare_ - Bursele Agora 2005/2006 Runda 1 )
Se considera un sir $A = (a{~1~}, a{~2~}, ..., a{~N~}) (-100.000 <= a{~i~} <= 100.000)$, format din $N$ numere intregi, precum si $M$ perechi de numere $(x, y) (1 <= N, M <= 100.000)$. Pentru fiecare pereche de indici $(x, y) (1 <= x <= y <= N)$ trebuie determinata subsecventa de suma maxima a subsirului $a{~x~}, a{~x+1~}, ..., a{~y~}$ , subsecventele alese trebuie ss contins cel putin un element.
Se consideră un şir $A = (a{~1~}, a{~2~}, ..., a{~N~})$, format din numere întregi $(-100.000 <= a{~i~} <= 100.000)$, şi $M$ perechi de numere $(x, y)$ $(1 <= N, M <= 100.000)$. Pentru fiecare pereche ordonată de indici $(x, y)$ trebuie determinată subsecvenţa de sumă maximă a subşirului $a{~x~}, a{~x+1~}, ..., a{~y~}$. Subsecvenţele alese trebuie să conţină cel puţin un element.
h4. Exemplu
Pentru sirul $(-1, 2, 3, -2, 4, -3, 8, -3, 1)$ si intervalele $[1, 5]$, $[4, 8]$ si $[6, 6]$ avem solutiile $7, 9, -3$, date de numerele ingrosate $([-1, *2*, *3*, *-2*, *4*], -3, 8, -3, 1, -1, 2, 3, [-2, *4*, *-3*, *8*, -3], 1, -1, 2, 3, -2, 4, [*-3*], 8, -3, 1)$.
Pentru sirul $(-1, 2, 3, -2, 4, -3, 8, -3, 1)$ si intervalele $[1, 5]$, $[4, 8]$ si $[6, 6]$ avem solutiile:
* $7$ pentru subsecvenţa $(-1, *2*, *3*, *-2*, *4*)$;
* $9$ pentru subsecvenţa $(-2, *4*, *-3*, *8*, -3)$;
* $-3$ pentru subsecvenţa $({*-3*})$.
h3. Rezolvare
Folosind algoritmii liniari din prima problema obtinem un algoritm de complexitate $O(MN)$. Sa vedem cum putem reduce complexitatea folosind alte abordari. Mai intai calculam sirul $sum$ al sumelor partiale. Apoi impartim sirul in $k$ subsecvente de lungimi egale $[n/k]$, pentru fiecare secventa pastrand urmatoarele informatii:
* $max[i]$ - cea mai mare valoare $sum[j]$, unde $n/k * (i-1) < j <= n/k * i$;
* $min[i]$ - cel mai mic $sum[j-1]$, unde $n/k * (i-1) < j <= n/k * i$;
* $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.
Acum, daca vrem sa aflam subsecventa de suma maxima a subsecventei $a[x..y]$, avem doua cazuri posibile:
1. Daca elementele de indice $x$ si $y$ apartin aceleiasi subsecvente din partitie, atunci putem gasi subsecventa de suma maxima folosind algoritmul liniar direct pe sirul $a[x..y]$ (complexitate $O(n/k)$).
2. Daca ele nu sunt in aceeasi secventa atunci vom imparti sirul $a[x..y]$ in un prefix de subsecventa din cele ce apartin partitionarii, in un sufix de subsecventa si in zero sau mai multe subsecvente complete ce apartin partitionarii. Acum vom rezolva problema pentru sufix si prefix metoda liniara ( {$O(n/k)$} ), iar apoi in $O(1)$ vom determina pentru fiecare bucata în care este spart sirul $a[x..y]$, subsecventa ei de suma maxima.
Mai ramane sa gasim subsecventa de suma maxima cu capatul in bucati diferite. Pentru doua bucati fixate $i <= j$, subsecventa de suma maxima ce are un capat apartinand primei bucati si $j$ apartinand celei de a doua bucati, subsecventa de suma maxima are valoarea $max[j] – min[i]$. Determinarea subsecventei de suma maxima cu capetele in bucati diferite devine astfel de complexitate $O(k)$. Deci pentru a rezolva o intrebare trebuie sa facem $O(n/k + k)$ calcule. Pentru a reduce complexitatea problemei obtinem pe $k = sqrt(n)$. Complexitatea totala a acestei solutii este $O(N + M sqrt(N))$.
Sa vedem ce se intampla pe exemplu:
a: $-1 2 3 -2 4 -3 8 -3 1$
sum: $0 -1 1 4 2 6 3 11 8 9$
Sirul e impartit in trei subsecvente $[-1, 2, 3], [-2, 4, -3], [8, -3, 1]$.
max: $ 4 6 11$
min: $-1 2 8$
best: $ 5 4 8$
Pentru a raspunde la intrebarea $[1, 5]$ vedem ca acest interval e inpartit in $[1..3]$ si $[4..5]$. Solutia optima pentru $[1..3]$ o avem deja in $best[1] = 5$. Solutia optima pentru $[4..5]$ o determinam folosind algoritmul liniar, ea fiind 4. Acum pentru a determina subsecventa de suma maxima cu un capat in intervalul $[1, 3]$ si celalalt in intervalul $[4, 5]$ folosim $max(sum[i]) - min(sum[j-1])$, unde $4 <= i <= 5$ si $1 <= j <= 3$. Valoarea $max(sum[i])$ o gasim ca fiind $6$ parcurgand intervalul $[4, 5]$, iar valoarea $min(sum[j-1])$ o avem deja calculata in $min[1]$. De aici obtinem rezultatul $7$.
Putem obţine un algoritm de complexitate $O(MN)$ folosind algoritmii liniari din prima problemă, dar să vedem cum putem reduce complexitatea folosind alte abordări. Mai întâi calculăm şirul $sum$ al sumelor parţiale, după care împărţim şirul în $k$ subsecvenţe de lungimi egale $[n/k]$, şi păstrăm următoarele informaţii pentru fiecare din ele:
1. $max[i]$ - cea mai mare valoare $sum[j]$, unde $n/k * (i-1) < j <= n/k * i$;
2. $min[i]$ - cel mai mic $sum[j-1]$, unde $n/k * (i-1) < j <= n/k * i$;
3. $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.
O solutie similara poate fi realizata cu ajutorul arborilor de intervale. Mai intai cream arborele de intervale. Pentru fiecare interval aflam elementele $min$, $max$ si $best$ astfel $min[x..y] = minim(min[x..(x+y)/2], min[(x+y)/2 + 1 .. y])$, $max[x..y] = maxim(max[x..(x+y)/2], max[(x+y)/2 + 1 .. y])$, $best[x..y] = maxim(best[x..(x+y)/2], maxim(best[(x+y)/2 + 1 .. y], max[(x+y)/2 + 1 .. y] - min[x..(x+y)/2]))$. Acum pentru a raspunde la intrebarile din problema fiecare interval va fi impartit in $O(log N)$ subintervale canonice care apar in arborele de intervale. Apoi printr-o parcurgere asemanatoare celei din rezolvarea anterioara se poate obtine rezultatul pentru fiecare intrebare in $O(log N)$. Solutia va avea complexitatea $O(N + M log N)$.
In urmatorul desen observam structura unui arbore de intervale pentru un sir cu $16$ elemente. Daca se pune intrebarea $[2, 11]$ acest interval va fi spart in intervalele $[2, 2], [3, 4], [5, 8], [9, 10], [11, 11]$.
Acum, pentru a afla subsecvenţa de sumă maximă a subsecvenţei $a[x..y]$ studiem cele două cazuri posibile:
Prezentam procedura de construire a arborelui, implementata in _java_:
1. Dacă elementele de indice $x$ şi $y$ aparţin aceleiaşi subsecvenţe, atunci putem găsi ceea ce căutăm folosind algoritmul liniar direct pe şirul $a[x..y]$ (complexitate $O(n/k)$).
2. Dacă nu sunt în aceeaşi secvenţă, atunci vom împărţi şirul $a[x..y]$ în:
a) un prefix de subsecvenţă din cele ce aparţin partiţionării,
b) un sufix de subsecvenţă,
c) zero sau mai multe subsecvenţe complete ce aparţin partiţionării,
după care rezolvăm problema pentru sufix şi prefix prin metoda liniară ( {$O(n/k)$} ), şi determinăm în $O(1)$ pentru fiecare bucată în care este spart şirul $a[x..y]$ subsecvenţa ei de sumă maximă.
Mai rămâne să găsim subsecvenţa de sumă maximă cu capătul în bucăţi diferite. Pentru două bucăţi fixate $i <= j$, subsecvenţa de sumă maximă ce are câte un capăt în fiecare bucatăm are valoarea $max[j] - min[i]$. Determinarea subsecvenţei de sumă maximă cu capetele în bucăţi diferite devine astfel de complexitate $O(k)$. Deci pentru a rezolva o întrebare trebuie să facem $O(n/k + k)$ calcule. Pentru a reduce complexitatea problemei considerăm pe $k = sqrt(n)$. Complexitatea totală a acestei soluţii este $O(N + M sqrt(N))$.
Să vedem ce se întâmplă pe exemplu:
|_. $a$ | - | $-1$ | $2$ | $3$ | $-2$ | $4$ | $-3$ | $8$ | $-3$ | $1$ |
|_. $sum$ | $0$ | $-1$ | $1$ | $4$ | $2$ | $6$ | $3$ | $11$ | $8$ | $9$ |
Şirul e împărţit în trei subsecvenţe $[-1, 2, 3], [-2, 4, -3], [8, -3, 1]$:
|_. $max$ | $4$ | $6$ | $11$ |
|_. $min$ | $-1$ | $2$ | $8$ |
|_. $best$ | $5$ | $4$ | $8$ |
Pentru a răspunde la întrebarea $[1, 5]$ trebuie să răspundem la cele două subsecvenţe componente $[1..3]$ şi $[4..5]$. Soluţia optimă pentru $[1..3]$ este $best[1] = 5$. Soluţia optimă pentru $[4..5]$ o determinăm folosind algoritmul liniar, ea fiind $4$. Acum, pentru a determina subsecvenţa de sumă maximă cu câte un capăt în fiecare interval folosim formula $max(sum[i]) - min(sum[j-1])$, unde $4 <= i <= 5$ şi $1 <= j <= 3$. Valoarea $max(sum[i])$ o găsim parcurgând intervalul $[4, 5]$ ca fiind $6$, iar valoarea $min(sum[j-1])$ o avem deja calculată în $min[1]$. De aici obţinem rezultatul $7$.
O soluţie similară poate fi obţinută cu ajutorul arborilor de intervale. Mai întâi creăm arborele de intervale. Pentru fiecare interval aflăm elementele $min$, $max$ şi $best$ astfel:
1. $min[x..y] = minim(min[x..(x+y)/2], min[(x+y)/2 + 1 .. y])$;
2. $max[x..y] = maxim(max[x..(x+y)/2], max[(x+y)/2 + 1 .. y])$;
3. $best[x..y] = maxim(best[x..(x+y)/2], maxim(best[(x+y)/2 + 1 .. y], max[(x+y)/2 + 1 .. y] - min[x..(x+y)/2]))$.
Acum pentru a răspunde la întrebările din problemă fiecare interval va fi împărţit în $O(log N)$ subintervale canonice care apar în arborele de intervale. Apoi printr-o parcurgere asemănătoare celei din rezolvarea anterioară se poate obţine rezultatul pentru fiecare întrebare în $O(log N)$. Soluţia va avea complexitatea $O(N + M log N)$.
În următorul desen observăm structura unui arbore de intervale pentru un şir cu $16$ elemente. Daca se pune întrebarea $[2, 11]$ acest interval va fi spart în intervalele $[2, 2], [3, 4], [5, 8], [9, 10], [11, 11]$.
Prezentăm procedura de construire a arborelui, implementată în _java_:
== code(java) |
public void build_tree(int index, int low, int high) {
}
==
h2(#prob4). Problema 4 - ACM ICPC NWERC 97, olimpiada online 2000, campion 2001
h2(#prob4). Problema 4 ( ACM ICPC NWERC 97, olimpiada online 2000, campion 2001 )
Se da un sir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N$ numere intregi. Se cere sa se determine subsecventa $a[i..j]$ care are modulul sumei elementelor minim.
Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din numere întregi. Se cere să se determine subsecvenţa $a[i..j]$ care are modulul sumei elementelor minim.
h4. Exemplu
Pentru sirul $(2, 8, -6, -6, 9, 4, -3)$, subsecventa este $(4, -3)$, avand suma in modul $1 = |4 - 3|$.
Pentru şirul $(2, 8, -6, -6, 9, 4, -3)$, subsecvenţa este $(4, -3)$, având suma în modul $1 = |4 - 3|$.
h3. Rezolvare
Facem mai intai sirul sumelor partiale. Pentru oricare doua elemente $sum[i]$ si $sum[j]$ ($i != j$) modulul sumei unei subsecvente din sir va fi $|sum[i] - sum[j]|$. Daca $i < j$ atunci secventa va fi $a[i+1..j]$, iar daca $j < i$ atunci secventa va fi $a[j+1 .. i]$. Astfel, pentru a gasi subsecventa de modul minim trebuie de fapt sa gasim perechea de indici $i$ si $j$ astfel ca $|sum[i] - sum[j]|$ sa fie minim. Sortand sirul sumelor partiale si luand o pereche de indici $i < j$, atunci $sum[i] < sum[j]$, iar $|sum[j] - sum[i]| = sum[j] - sum[i]$. Pentru a gasi perechea $(i, j)$ pentru care $i < j$ si $sum[j] - sum[i]$ este minim, trebuie ca $i$ sa fie egal cu $j + 1$. Astfel obtinem un algoritm de complexitate $O(N log N)$.
Facem mai întâi şirul sumelor parţiale. Pentru oricare două elemente $sum[i]$ şi $sum[j]$ ($i != j$) modulul sumei unei subsecvenţe din şir va fi $|sum[i] - sum[j]|$. Dacă $i < j$, atunci secvenţa va fi $a[i+1..j]$, iar dacă $j < i$, atunci secvenţa va fi $a[j+1 .. i]$. Astfel, pentru a găsi subsecvenţa de modul minim trebuie, de fapt, să găsim perechea de indici $i$ şi $j$ astfel ca $|sum[i] - sum[j]|$ să fie minim. Sortând şirul sumelor parţiale şi luând o pereche de indici $i < j$, atunci $sum[i] < sum[j]$, iar $|sum[j] - sum[i]| = sum[j] - sum[i]$. Pentru a găsi perechea $(i, j)$ pentru care $i < j$ şi $sum[j] - sum[i]$ este minim, trebuie ca $i$ să fie egal cu $j + 1$. Astfel obţinem un algoritm de complexitate $O(N log N)$.
Să vedem cum merge pe exemplul prezentat:
|_. $a$ | - | $2$ | $8$ | $-6$ | $-6$ | $9$ | $4$ | $-3$ |
|_. $sum$ | $0$ | $2$ | $10$ | $4$ | $-2$ | $7$ | $11$ | $8$ |
|_. $ind$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
În şirul $ind$ vom păstra indicii reali ai sumelor parţiale. După sortare avem:
|_. $sum$ | $-2$ | $0$ | $2$ | $4$ | $7$ | $8$ | $10$ | $11$ |
|_. $ind$ | $4$ | $0$ | $1$ | $4$ | $5$ | $7$ | $2$ | $6$ |
Sa vedem cum merge pe exemplul prezentat:
a: $2 8 -6 -6 9 4 -3$
sum: $0 2 10 4 -2 7 11 8$
ind: $0 1 2 3 4 5 6 7$
In sirul $ind$ vom pastra indicii reali ai sumelor parţiale.
Dupa sortare avem:
sum: $ -2 0 2 4 7 8 10 11$
ind: $ 4 0 1 4 5 7 2 6$
O secventa de modul $2$ ar fi cea reprezentata de sumele $8$ si $10$ cu indicii $7$ si $2$. Aceasta secventa este $(-6, -6, 9, 4, -3)$.
Observam ca cea mai mica diferenta intre termeni consecutivi e cea dintre $8$ si $7$ care au indicii $7$ si $5$, de unde obtinem ca subsecventa de modul minim este $(4, -3)$.
O secvenţă de modul $2$ ar fi cea reprezentată de sumele $8$ şi $10$, cu indicii $7$ şi $2$. Această secvenţă este $(-6, -6, 9, 4, -3)$. Observăm ca cea mai mică diferenţă între termeni consecutivi e cea dintre $8$ şi $7$, care au indicii $7$ şi $5$, de unde obţinem că subsecvenţa de modul minim este $(4, -3)$.
h2(#prob5). Problema 5 - USACO
