Diferente pentru probleme-cu-secvente intre reviziile #26 si #56

Diferente intre titluri:

Probleme cu secvente
Probleme cu secvențe important

Diferente intre continut:

h1. Probleme cu secvenţe
(Categoria _Diverse_, autor _Cosmin Negruşeri_)
== include(page="template/implica-te/scrie-articole" user_id="alecman") ==
(toc){width: 30em}*{text-align:center} *Cuprins*
* 'Introducere ':probleme-cu-secvente#intro
* 'Problema 1 (Subsecvenţa de sumă maximă) ':probleme-cu-secvente#prob1
* 'Problema 2 (Maximum Sum) ':probleme-cu-secvente#prob2
* 'Problema 3 (SequenceQuery) ':probleme-cu-secvente#prob3
* 'Problema 4 ':probleme-cu-secvente#prob4
* 'Problema 5 ':probleme-cu-secvente#prob5
* 'Problema 6 (Secvenţă) ':probleme-cu-secvente#prob6
* 'Problema 7 (Agricultura) ':probleme-cu-secvente#prob7
* 'Problema 8 (Secvenţa 2) ':probleme-cu-secvente#prob8
* 'Problema 9 (Sum) ':probleme-cu-secvente#prob9
* 'Problema 10 (Secvenţa 3) ':probleme-cu-secvente#prob10
* 'Problema 11 (XorMax) ':probleme-cu-secvente#prob11
* 'Probleme propuse':probleme-cu-secvente#probp
(Categoria _Algoritmi şi tehnici de programare_, Autor _Cosmin Negruşeri_)
 
(toc){width: 27em}*{text-align:center} *Conţinut*
* 'Introducere ':probleme-cu-secvente#introducere
* 'Problema 1: Subsecvenţa de sumă maximă ':probleme-cu-secvente#problema-1
* 'Problema 2: Maximum Sum ':probleme-cu-secvente#problema-2
* 'Problema 3: SequenceQuery ':probleme-cu-secvente#problema-3
* 'Problema 4 ':probleme-cu-secvente#problema-4
* 'Problema 5 ':probleme-cu-secvente#problema-5
* 'Problema 6: Secvenţă ':probleme-cu-secvente#problema-6
* 'Problema 7: Agricultura ':probleme-cu-secvente#problema-7
* 'Problema 8: Secvenţa 2 ':probleme-cu-secvente#problema-8
* 'Problema 9: Sum ':probleme-cu-secvente#problema-9
* 'Problema 10: Secvenţa 3 ':probleme-cu-secvente#problema-10
* 'Problema 11: XorMax ':probleme-cu-secvente#problema-11
* 'Probleme propuse':probleme-cu-secvente#probleme-propuse
* 'Bibliografie':probleme-cu-secvente#bibliografie
h2(#intro). Introducere
h2(#introducere). Introducere
Acest articol prezintă o serie de probleme înrudite cu problema subsecvenţei de sumă maximă, însoţite de rezolvări eficiente. Problemele prezentate pot apărea oricând ca subprobleme în concursurile de programare, studierea lor mărind în mod util bagajul de cunoştinţe al unui elev pasionat de algoritmică.
h2(#prob1). Problema 1 (Subsecvenţa de sumă maximă)
h2(#problema-1). Problema 1: 'Subsecvenţa de sumă maximă':problema/ssm
bq. Se dă un şir de $N$ numere întregi $(a{~1~}, a{~2~}, ..., a{~N~})$. Să se determine o subsecvenţă $(a{~i~}, a{~i+1~}, ..., a{~j~})$ care să aibă suma maximă.
Prima rezolvare care ne vine în minte are complexitatea $O(N^3^)$ şi constă în determinarea sumei fiecărei subsecvenţe posibile şi reţinerea maximului acestor sume. Este evident că anumite sume parţiale sunt calculate de mai multe ori.
Putem reduce complexitatea la $O(N^2^)$ ţinând cont de faptul că suma subsecvenţei $a[i..j]$ este egală cu suma subsecvenţei $a[i..j-1]$, la care se adună $a[j]$. Păstrăm într-un şir $sum[i]$ suma elementelor din subsecvenţa $a[1..i]$. Pentru a determina suma elementelor din subsecvenţa $a[i..j]$ facem diferenţa: $sum[i] - sum[j-1]$.
Putem reduce complexitatea la $O(N^2^)$ ţinând cont de faptul că suma subsecvenţei $a[j..i]$ este egală cu suma subsecvenţei $a[j..i-1]$, la care se adună $a[i]$. Păstrăm într-un şir $sum[i]$ suma elementelor din subsecvenţa $a[1..i]$. Pentru a determina suma elementelor din subsecvenţa $a[j..i]$ facem diferenţa: $sum[i] - sum[j-1]$.
Ideea poate fi rafinată calculând pentru fiecare indice $i$ numărul $best[i]$, reprezentând subsecvenţa de sumă maximă cu capătul drept în $i$. Este uşor de observat că $best[i] = max(sum[i] - sum[j-1])$, unde $j$ ia valori de la $1$ la $i$. Relaţia anterioară se mai poate scrie: $best[i] = sum[i] - min(sum[j-1])$. Obţinem astfel un algoritm liniar care ne determină subsecvenţa de sumă maximă cerută.
}
==
O altă metodă de calcul poate fi dedusă folosind paradigma _Divide Et Impera_. La fiecare pas împărţim şirul în jumătate şi aflăm subsecvenţele de sumă maximă din cele două jumătăţi. După aceea trebuie să găsim subsecvenţa de sumă maximă ce are un capăt în fiecare din cele două jumătăţi ale sirului. Pentru aceasta alipim sufixul de sumă maximă a primei jumătăţi cu prefixul de sumă maximă a celei de a doua.
O altă metodă de calcul poate fi dedusă folosind paradigma _Divide et Impera_. La fiecare pas împărţim şirul în jumătate şi aflăm subsecvenţele de sumă maximă din cele două jumătăţi. După aceea trebuie să găsim subsecvenţa de sumă maximă ce are un capăt în fiecare din cele două jumătăţi ale sirului. Pentru aceasta alipim sufixul de sumă maximă a primei jumătăţi cu prefixul de sumă maximă a celei de a doua.
== code(cpp) |
int getMaxSubsequence(int l, int r) {
O idee bazată pe paradigma programării dinamice ar fi să folosim un şir $best[i]$, reprezentând suma maximă a unei subsecvenţe ce se termină în $a[i]$. Problema se rezolvă cu următoarea formulă de recurenţă: $best[i] = max(a[i], best[i-1] + a[i])$. Formula poate fi demonstrată prin inducţie matematică.
O ultimă idee ar fi să partiţionăm şirul în subsecvenţe încât fiecare să aibă ambele capete cât mai mici posibile şi suma elementelor subsecvenţei să fie negativă. Pentru exemplul dat avem următoarea partiţionare: $[-1], [2, 3, -4, -2], [2, 1, -3, -2], [-3], [-4], [9, -2, 1, 7, 8, -19, -7], [2, 4, 3]$. O subsecvenţă de sumă maximă va avea primul capăt la începutul unei astfel de subsecvenţe, acest lucru explicându-se prin faptul că în caz contrar secvenţa poate fi mărită în stânga (orice secvenţă din cele alese pentru partiţionare are toate prefixele de sumă pozitivă, în afară de prefixul ce reprezintă întreaga subsecvenţă). De asemenea, orice subsecvenţă de sumă maximă nu va conţine elemente din altă parte a partiţiei, pentru că dacă subsecvenţa se întinde pe mai multe părţi, atunci putem elimina prefixul subsecvenţei care reprezintă o parte a partiţiei, acea parte având suma negativă.
== code(cpp) |
bestSum = a[1];
for (i = 1; i <= N; ++ i) {
    best[i] = a[i];
    if (best[i] < best[i-1] + a[i])
        best[i] = best[i-1] + a[i];
    if (bestSum < best[i])
        bestSum = best[i];
}
==
 
O ultimă idee, dacă se garantează că există cel puţin un număr pozitiv, ar fi să partiţionăm şirul în subsecvenţe încât fiecare să aibă ambele capete cât mai mici posibile şi suma elementelor subsecvenţei să fie negativă. Pentru exemplul dat avem următoarea partiţionare: $[-1], [2, 3, -4, -2], [2, 1, -3, -2], [-3], [-4], [9, -2, 1, 7, 8, -19, -7], [2, 4, 3]$. O subsecvenţă de sumă maximă va avea primul capăt la începutul unei astfel de subsecvenţe, acest lucru explicându-se prin faptul că în caz contrar secvenţa poate fi mărită în stânga (orice secvenţă din cele alese pentru partiţionare are toate prefixele de sumă pozitivă, în afară de prefixul ce reprezintă întreaga subsecvenţă). De asemenea, orice subsecvenţă de sumă maximă nu va conţine elemente din altă parte a partiţiei, pentru că dacă subsecvenţa se întinde pe mai multe părţi, atunci putem elimina prefixul subsecvenţei care reprezintă o parte a partiţiei, acea parte având suma negativă.
== code(cpp) |
sum = -INFINIT;
sum = 0;
bestSum = -INFINIT;
for (i = 1; i <= N; i++) {
    sum += a[i];
    if (sum < 0)
        sum = 0;
    else if (sum >= bestSum)
    else if (sum > bestSum)
        bestSum = sum;
}
==
h2(#prob2). Problema 2 ('Maximum Sum':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44, UVa)
h2(#problema-2). Problema 2: 'Maximum Sum':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&amp;page=show_problem&amp;problem=44 (UVa)
bq. Se dă o matrice de dimensiuni $N x N$ cu elemente întregi. Se cere determinarea unei submatrici a cărei elemente au suma maximă.
h3. Rezolvare:
Putem folosi trucul construirii sumelor parţiale din rezolvarea anterioară, pentru cazul $2D$. Păstrăm în $sum[i][j]$ suma tuturor elementelor $a[i{~1~}][j{~1~}]$ cu proprietatea că $1 <= i{~1~} <= i$, şi $1 <= j{~1~} <= j$. Putem calcula sumele prin metoda programării dinamice în complexitate $O(N^2^)$ folosind formula: $sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]$. Acum, pentru a calcula suma elementelor din matricea cu colţurile $(i{~1~}, j{~1~})$ şi $(i{~2~}, j{~2~})$, unde $i{~1~} <= i{~2~}$ şi $j{~1~} <= j{~2~}$, este suficient să facem calculul $sum[i{~2~}][j{~2~}] - sum[i{~1~}-1][j{~2~}] - sum[i{~2~}][j{~1~}-1] + sum[i{~1~}-1][j{~1~}-1]$. Astfel putem evalua suma din fiecare submatrice în timp constant, deci rezolvarea are ordinul de complexitate $O(N^4^)$.
Putem folosi trucul construirii sumelor parţiale din rezolvarea anterioară, pentru cazul $2D$. Păstrăm în $sum[i][j]$ suma tuturor elementelor $a[i{~1~}][j{~1~}]$ cu proprietatea că $1 &le; i{~1~} &le; i$, şi $1 &le; j{~1~} &le; j$. Putem calcula sumele prin metoda programării dinamice în complexitate $O(N^2^)$ folosind formula: $sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]$. Acum, pentru a calcula suma elementelor din matricea cu colţurile $(i{~1~}, j{~1~})$ şi $(i{~2~}, j{~2~})$, unde $i{~1~} &le; i{~2~}$ şi $j{~1~} &le; j{~2~}$, este suficient să facem calculul $sum[i{~2~}][j{~2~}] - sum[i{~1~}-1][j{~2~}] - sum[i{~2~}][j{~1~}-1] + sum[i{~1~}-1][j{~1~}-1]$. Astfel putem evalua suma din fiecare submatrice în timp constant, deci rezolvarea are ordinul de complexitate $O(N^4^)$.
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.
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~} &le; i &le; 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> şi este mai mult un algoritm teoretic decât unul practic, uşor implementabil. Pentru detalii puteti consulta lucrarea [3].
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. Pentru detalii puteti consulta lucrarea [3].
h2(#prob3). Problema 3 ('SequenceQuery':problema/sequencequery, Bursele Agora 2005/2006 Runda 1)
h2(#problema-3). Problema 3: 'SequenceQuery':problema/sequencequery (Bursele Agora 2006)
bq. 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.
bq. Se consideră un şir $A = (a{~1~}, a{~2~}, ..., a{~N~})$, format din numere întregi $(-100.000 &le; a{~i~} &le; 100.000)$, şi $M$ perechi de numere $(x, y)$ $(1 &le; N, M &le; 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.
h3. Exemplu:
Putem obţine un algoritm de complexitate $O(M * N)$ 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:
* $max[i]$ - cea mai mare valoare $sum[j]$, unde: $N/K * (i - 1) < j <= N/K * i$;
* $max[i]$ - cea mai mare valoare $sum[j]$, unde: $N / K * (i - 1) < j &le; N / K * i$;
* $min[i]$ - cel mai mic $sum[j - 1]$, unde: $N/K * (i - 1) < j <= N/K * i$;
* $min[i]$ - cel mai mic $sum[j - 1]$, unde: $N / K * (i - 1) < j &le; N / K * i$;
* $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.
Acum, pentru a afla subsecvenţa de sumă maximă a subsecvenţei $a[x..y]$ studiem cele două cazuri posibile:
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)$.
# 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:
# Dacă nu sunt în aceeaşi secvenţă, atunci vom împărţi şirul $a[x..y]$ în:
* un prefix de subsecvenţă din cele ce aparţin partiţionării,
* 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ă în $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ă.
după care rezolvăm problema pentru sufix şi prefix prin metoda liniară în $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ă 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))$.
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ă 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:
table{width:300px; text-align:right;}.
|_. $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]$:
şirul e împărţit în trei subsecvenţe $[-1, 2, 3], [-2, 4, -3], [8, -3, 1]$:
table{width:100px; text-align:right;}.
|_. $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[&#49;] = 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[&#49;]$. De aici obţinem rezultatul $7$.
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[&#49;] = 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 &le; i &le; 5$ şi $1 &le; j &le; 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[&#49;]$. 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:
* $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)$.
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]$.
!probleme-cu-secvente?numere2.png!
p=. !probleme-cu-secvente?numere2.png!
Prezentăm procedura de construire a arborelui, implementată în _java_:
        int mid = (low + high) / 2;
        build_tree(2 * index, low, mid);
        build_tree(2 * index + 1, mid + 1, high);
        aint[index].maxS = Math.max(aint[2 * index].maxS,Math.max(aint[2 * index + 1].maxS,aint[2 * index + 1].max - aint[2 * index].min));
        aint[index].max = Math.max(aint[2 * index].max,aint[2 * index + 1].max);
        aint[index].min = Math.min(aint[2 * index].min,aint[2 * index + 1].min);
        aint[index].maxS = Math.max(aint[2 * index].maxS,
                Math.max(aint[2 * index + 1].maxS, aint[2 * index + 1].max - aint[2 * index].min));
        aint[index].max = Math.max(aint[2 * index].max, aint[2 * index + 1].max);
        aint[index].min = Math.min(aint[2 * index].min, aint[2 * index + 1].min);
    }
}
==
Şi procedura care răspunde la întrebări tot în _java_:
şi procedura care răspunde la întrebări tot în _java_:
== code(java) |
long minPrefix;
long minPrefix;
int x, y;
public long queryTree(int index, int low, int high) {
    if (x <= low && high <= y) {
        long maxRet = aint[index].maxS;
        if (minPrefix != infinity) {
        if (minPrefix != INFINIT) {
            maxRet = Math.max(maxRet, aint[index].max - minPrefix);
        }
        minPrefix = Math.min(minPrefix, aint[index].min);
    }
    else {
        int mid = (low + high) / 2;
        if (x <= mid && mid < y) return  Math.max(queryTree(2 * index, low, mid), queryTree(2 * index + 1, mid + 1, high));
        else if (x > mid) return queryTree(2 * index + 1, mid + 1, high);
            else return queryTree(2 * index, low, mid);
        if (x <= mid && mid < y)
            return Math.max(queryTree(2 * index, low, mid), queryTree(2 * index + 1, mid + 1, high));
        else if (x > mid)
            return queryTree(2 * index + 1, mid + 1, high);
        else
            return queryTree(2 * index, low, mid);
    }
}
==
Autorul vă recomandă articolele [1] şi [2] pentru o înţelegere mai profundă a structurii de date numită arbori de intervale. Problema poate fi soluţionată şi în $O(N + M)$, dar algoritmul este mult prea complicat pentru un concurs de programare; cei interesaţi pot să îl găsească în [4].
h2(#prob4). Problema 4 (ACM ICPC NWERC 97, olimpiada online 2000, campion 2001)
h2(#problema-4). Problema 4 (ACM ICPC NWERC 97, olimpiada online 2000, .campion 2001)
bq. 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.
h3. Rezolvare:
Construim întâi şirul sumelor parţiale. Pentru oricare două elemente $sum[i]$ şi $sum[j]$ cu $(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)$.
Construim întâi şirul sumelor parţiale. Pentru oricare două elemente $sum[i]$ şi $sum[j]$ cu $(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:
table{width:300px; text-align:right;}.
|_. $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:
table{width:300px; text-align:right;}.
|_. $sum$ | $-2$ | $0$ | $2$ | $4$ | $7$ | $8$ | $10$ | $11$ |
|_. $ind$ | $4$ | $0$ | $1$ | $4$ | $5$ | $7$ | $2$ | $6$ |
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)
h2(#problema-5). Problema 5 (USACO)
bq. Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N (1 <= N <= 100 000)$ numere întregi $(1 <= a{~i~} <= 2 000)$ si un numar natural $F$. Se cere să se determine subsecvenţa $a[i..i + K - 1]$ cu media aritmetică a elementelor maximă, unde $K$ are proprietatea $K >= F$.
bq. Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din $N (1 &le; N &le; 100 000)$ numere întregi $(1 &le; a{~i~} &le; 2 000)$ si un numar natural $F$. Se cere să se determine subsecvenţa $a[i..i + K - 1]$ cu media aritmetică a elementelor maximă, unde $K$ are proprietatea $K &ge; F$.
h3. Exemplu:
* În cazul în care subsecvenţa de sumă maximă a şirului $b$ are valoarea egală cu zero, atunci subsecvenţa de medie maximă a şirului $a$ are media $X$.
Astfel putem face o căutare binară pentru a determina valoarea $X$ a mediei maxime. Ne mai rămâne să determinăm un algoritm eficient pentru găsirea subsecvenţei de sumă maximă de lungime cel puţin $F$. O asemenea soluţie urmăreşte una din ideile din prima problemă: fie $best[i]$ subsecvenţa de sumă maximă ce se termină în $a[i]$. Evident $best[i] = max(a[i], best[i - 1] + a[i])$. Acum secvenţa de sumă maximă ce se termină în $a[i]$, de lungime cel puţin $F$ se găseşte ca $a[i] + a[i - 1] + .. + a[i - F + 2] + best[i - F + 1]$. Această relaţie poate fi calculată în $O(1)$ dacă ne folosim de trucul sumelor parţiale. Complexitatea finală este $O(N log C)$, unde $C$ e valoarea maximă a lui $a{~i~}$.
Astfel putem face o căutare binară pentru a determina valoarea $X$ a mediei maxime. Ne mai rămâne să determinăm un algoritm eficient pentru găsirea subsecvenţei de sumă maximă de lungime cel puţin $F$. O asemenea soluţie urmăreşte una din ideile din prima problemă: fie $best[i]$ subsecvenţa de sumă maximă ce se termină în $a[i]$. Evident $best[i] = max(a[i], best[i - 1] + a[i])$. Acum secvenţa de sumă maximă ce se termină în $a[i]$, de lungime cel puţin $F$ se găseşte ca $a[i] + a[i - 1] + .. + a[i - F + 2] + best[i - F + 1]$. Această relaţie poate fi calculată în $O(1)$ dacă ne folosim de trucul sumelor parţiale. Complexitatea finală este $O(N * log C)$, unde $C$ e valoarea maximă a lui $a{~i~}$.
h2(#prob6). Problema 6 ('Secvenţă':problema/secventa)
h2(#problema-6). Problema 6: 'Secvenţă':problema/secventa
bq. Se da un şir de $N$ numere întregi. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Definim baza unei secvenţe ca fiind minimul valorilor elementelor din secvenţa respectivă. Fiind dat un număr natural $K$, determinaţi o secvenţă de lungime cel puţin $K$, cu baza maximă. Restrictii: $1 <= K <= N <= 500 000$.
bq. Se da un şir de $N$ numere întregi. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Definim baza unei secvenţe ca fiind minimul valorilor elementelor din secvenţa respectivă. Fiind dat un număr natural $K$, determinaţi o secvenţă de lungime cel puţin $K$, cu baza maximă. Restrictii: $1 &le; K &le; N &le; 500 000$.
h3. Exemplu:
Presupunem că orice secvenţă optimă ar avea lungimea mai mare decât $K$. Atunci putem obţine o secvenţă mai mică, cu aceeaşi bază eliminând unul din capetele unei secvenţe optime. Deci este de ajuns să cautăm secvenţele optime de lungime exact $K$.
Acum putem face o parcurgere a şirului pentru a rezolva problema. Mai întâi punem într-un $min-heap$ $K$ elemente, verificăm vârful heapului şi obţinem astfel minimul secvenţei $a[1..k]$. Apoi eliminăm elementul $a[&#49;]$ din heap şi inserăm elementul $a[K+1]$. Prin verificarea vârfului heapului obţinem minimul secvenţei $a[2..K+1]$. Continuăm procedeul până aflăm elementul minim pentru fiecare subsecvenţă de lungime $K$ a şirului $a$ (complexitate $O(N log N)$). Există şi alte soluţii pentru găsirea elementului minim al unei subsecvenţe, precum folosirea unui arbore de intervale sau folosirea tehnicii $O(N log N)/O(1)$ pentru problema _RMQ_, dar obţinem tot soluţii de complexitate $O(N log N)$.
Acum putem face o parcurgere a şirului pentru a rezolva problema. Mai întâi punem într-un $min-heap$ $K$ elemente, verificăm vârful heapului şi obţinem astfel minimul secvenţei $a[1..K]$. Apoi eliminăm elementul $a[&#49;]$ din heap şi inserăm elementul $a[K + 1]$. Prin verificarea vârfului heapului obţinem minimul secvenţei $a[2..K + 1]$. Continuăm procedeul până aflăm elementul minim pentru fiecare subsecvenţă de lungime $K$ a şirului $a$ (complexitate $O(N * log K)$). Există şi alte soluţii pentru găsirea elementului minim al unei subsecvenţe, precum folosirea unui arbore de intervale sau folosirea tehnicii $O(N * log N) / O(1)$ pentru problema _RMQ_.
O observaţie importantă este aceea că dacă vrem să vedem minimul secvenţei ce se termină în $i$ şi avem $j{~1~} < j{~2~} <= i$ şi $a[j{~1~}] >= a[j{~2~}]$, atunci evident $a[j{~1~}]$ nu va fi minimul secvenţei ce se termină în $i$. Folosim o structură de date ca la soluţia cu heapuri, care adaugă elemente noi şi şterge elemente vechi, dar pe lângă elementele ce au fost inserate acum $k$ paşi şi trebuie şterse, mai ştergem şi elementele mai noi care nu ne vor mai fi utile, după cum este $a[j{~2~}]$ mai sus. Ca structură de date folosim o listă în care putem insera şi şterge de la ambele capete, un _deque_. Fiecare element inserat în deque va fi o pereche de valori, valoarea din şir şi indexul din şir $(a[i], i)$. Când o valoare este inserată în şir, ea este pusă la capătul din dreapta al şirului, dar înainte de inserare cât timp elementul din capătul şirului are valoarea mai mare decât $a[i]$ el este eliminat. La fiecare pas după o inserţie se verifică dacă elementul din capătul din stânga este mai bătrân de $K$ iteraţii.
O observaţie importantă este aceea că dacă vrem să vedem minimul secvenţei ce se termină în $i$ şi avem $j{~1~} < j{~2~} &le; i$ şi $a[j{~1~}] &ge; a[j{~2~}]$, atunci evident $a[j{~1~}]$ nu va fi minimul secvenţei ce se termină în $i$. Folosim o structură de date ca la soluţia cu heapuri, care adaugă elemente noi şi şterge elemente vechi, dar pe lângă elementele ce au fost inserate acum $K$ paşi şi trebuie şterse, mai ştergem şi elementele mai noi care nu ne vor mai fi utile, după cum este $a[j{~2~}]$ mai sus. Ca structură de date folosim o listă în care putem insera şi şterge de la ambele capete, un _deque_. Fiecare element inserat în deque va fi o pereche de valori, valoarea din şir şi indexul din şir $(a[i], i)$. Când o valoare este inserată în şir, ea este pusă la capătul din dreapta al şirului, dar înainte de inserare cât timp elementul din capătul şirului are valoarea mai mare decât $a[i]$ el este eliminat. La fiecare pas după o inserţie se verifică dacă elementul din capătul din stânga este mai bătrân de $K$ iteraţii.
Din cauza modului în care se fac inserţiile şi ştergerile, şirul va fi sortat totdeauna crescător după indecşi şi crescător după valori. Tot timpul ultimul element din stivă va conţine valoarea bazei. Acest algoritm are complexitatea $O(N)$ pentru că fiecare element este inserat şi şters din deque cel mult o dată.
lista devine: $(4, 6) (6, 8)$
elementul minim al secvenţei $a[6..8]$ este $4$
h2(#prob7). Problema 7 (Agricultura, Algoritmus)
h2(#problema-7). Problema 7: Agricultura (Algoritmus)
Vasilica vrea să se apuce de agricultură şi, prin urmare, să cumpere o parcelă de teren. Harta pusă la dispoziţie de către primăria oraşului în care locuieşte Vasilică se poate reprezenta sub forma unei matrice de dimensiuni $N x M (2 <= N, M <= 150)$, fiecare $m^2^$ de teren fiind reprezentat printr-un element din matrice. Pentru fiecare $m^2^$ de pământ se cunoaşte altitudinea (faţă de nivelul mării) la care se află acesta. Agricultorul nostru doreşte să cumpere o parcelă de formă dreptunghiulară dar, deoarece are de gând să se ocupe de culturi foarte pretenţioase la modificări de nivel, diferenţa dintre valorile care indică altitudinea maximă şi cea minimă din parcelă trebuie să fie mai mică decât o valoare dată $K (1 <= K <= 1 000)$. Mai mult, suprafaţa pe care Vasilică o va achiziţiona trebuie  fie cât mai mare posibil.
bq. Se dă o matrice de dimensiuni $N x M$ de numere naturale. Se cere determinarea unei submatrici cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât o valoare dată $K$. Restrictii: $2 &le; N, M &le; 150$, $1 &le; K &le; 1 000$.
h3. Exemplu:
h3. Rezolvare:
Problema constă în determinarea submatricei cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât $K$. Vom folosi ideea de la problema cu subsecvenţa de sumă maximă pe matrice, adică vom fixa două linii $i{~1~}$ şi $i{~2~}$. Acum pentru fiecare coloană $j$ păstrăm în $m[j]$ elementul minim şi în $M[j]$ elementul maxim $a[i][j]$ cu $i{~1~} <= i <= i{~2~}$. Astfel la fiecare pas trebuie acum să rezolvăm problema determinării unei subsecvenţe de lungime maximă pentru care diferenţa între elementul maxim şi minim este mai mică decât $K$. Folosind un _max-heap_ şi un _min-heap_ putem parcurge elementele şirurilor $M$ şi $m$ în ordine inserând la fiecare pas elemente în heap şi determinând cea mai lungă secvenţă ce se termină în $i$ cu proprietatea dată. Vom ţine un al 2-lea indice $j$, iniţial $0$, care atâta timp cât diferenţa între elementul maxim din max-heap cu elementul minim din min-heap este mai mare sau egală cu $K$, vom scoate din heapuri elementele $M[j]$, respectiv $m[j]$ şi îl vom incrementa pe $j$ ( complexitate $O(N^3^ log N)$ ). Dacă în loc de heapuri folosim deque-uri, atunci acest algoritm va avea complexitatea $O(N^3^)$.
Problema constă în determinarea submatricei cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât $K$. Vom folosi ideea de la problema cu subsecvenţa de sumă maximă pe matrice, adică vom fixa două linii $i{~1~}$ şi $i{~2~}$. Acum pentru fiecare coloană $j$ păstrăm în $m[j]$ elementul minim şi în $M[j]$ elementul maxim $a[i][j]$ cu $i{~1~} &le; i &le; i{~2~}$. Astfel la fiecare pas trebuie acum să rezolvăm problema determinării unei subsecvenţe de lungime maximă pentru care diferenţa între elementul maxim şi minim este mai mică decât $K$. Folosind un _max-heap_ şi un _min-heap_ putem parcurge elementele şirurilor $M$ şi $m$ în ordine inserând la fiecare pas elemente în heap şi determinând cea mai lungă secvenţă ce se termină în $i$ cu proprietatea dată. Vom ţine un al $2$-lea indice $j$, iniţial $0$, care atâta timp cât diferenţa între elementul maxim din max-heap cu elementul minim din min-heap este mai mare sau egală cu $K$, vom scoate din heapuri elementele $M[j]$, respectiv $m[j]$ şi îl vom incrementa pe $j$. Complexitate: $O(N^3^ log N)$. Dacă în loc de heapuri folosim deque-uri, atunci acest algoritm va avea complexitatea $O(N^3^)$.
h2(#prob8). Problema 8 ('Secvenţa 2':problema/secv2)
h2(#problema-8). Problema 8: 'Secvenţa 2':problema/secv2
Gigel s-a decis să devină olimpic la informatică, poate aşa va reuşi să-şi rezolve singur problemele, şi nu va mai cere ajutorul vostru! La ora de informatică, profesoara lui i-a dat să rezolve problema secvenţei de sumă maximă: "Gigele, eu iţi dau un şir de $N$ numere întregi, iar tu trebuie să găseşti o secvenţă ( adică un subşir de numere care apar pe poziţii consecutive în şirul iniţial ) cu suma elementelor maximă!". După vreo $30$ de minute, Gigel s-a ridicat mândru şi a zis: "Am găsit algoritmul de complexitate optimă, doamna profesoară!". Ca temă pentru acaGigel are de rezolvat aproape aceeaşi problemă: trebuie să găsească secvenţa de sumă maximă de lungime cel puţin $K (1 <= k <= N <= 50 000)$. Gigel încă nu ştie destul de multă informatică ca să poata rezolva această problemă, dar poate îl ajutaţi voi! Scrieţi un program care rezolvă problema din tema lui Gigel.
bq. Se da un şir de $N$ numere întregi şi un număr natural $K$. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Se cere să se găsească secvenţa de sumă maximă de lungime cel puţin $K$. Restrictii: $1 &le; K &le; N &le; 50 000$.
h3. Exemplu:
h3. Rezolvare:
Putem folosi rezolvarea liniară bazată pe programare dinamică prezentată ca subalgoritm în soluţia problemei $5$, dar putem simplifica logica din acea rezolvare. Vom folosi şirul sumelor parţiale $sum$, iar pentru a determina subsecvenţa de sumă maximă ce se termină în $i$ şi are lungimea cel puţin $K$ trebuie să găsim $sum[j]$ minim astfel ca $j < i - K$. Parcurgem lista, şi la pasul $i$ determinăm $best[i] = sum[i] - min(sum[j])$, $j < i - K$. Comparăm minimul curent cu $sum[i-K]$ şi trecem la pasul următor. Complexitate: $O(N)$.
Putem folosi rezolvarea liniară bazată pe programare dinamică prezentată ca subalgoritm în soluţia 'problemei $5$':probleme-cu-secvente#problema-5, dar putem simplifica logica din acea rezolvare. Vom folosi şirul sumelor parţiale $sum[]$, iar pentru a determina subsecvenţa de sumă maximă ce se termină în $i$ şi are lungimea cel puţin $K$ trebuie să găsim $sum[j]$ minim astfel ca $j < i - K$. Parcurgem lista, şi la pasul $i$ determinăm $best[i] = sum[i] - min(sum[j])$, $j < i - K$. Comparăm minimul curent cu $sum[i - K]$ şi trecem la pasul următor. Complexitate: $O(N)$.
h2(#prob9). Problema 9 ('Sum':problema/sum2, Stelele Informaticii 2003 )
h2(#problema-9). Problema 9: 'Sum':problema/sum2 (Stelele Informaticii 2003)
Se dă un şir de numere întregi. Se caută un subşir cu lungimea cuprinsă între $L$ şi $U$, format din elemente consecutive ale şirului iniţial, cu suma elementelor maximă $(1 <= L <= U <= N <= 100 000)$.
bq. Se dă un şir de $N$ numere întregi. Se caută un subşir cu lungimea cuprinsă între $L$ şi $U$, format din elemente consecutive ale şirului iniţial, cu suma elementelor maximă. Restrictii: $1 &le; L &le; U &le; N &le; 100 000$.
h3. Rezolvare:
Pentru fiecare $i$ este de ajuns să aflăm valoarea expresiei $sum[i] - sum[j]$, unde $i - L > j >= i - U$. Pentru a determina valoarea optimă pentru $sum[j]$ putem folosi un heap de dimensiune $U - L$, sau putem folosi tehnici de determinare a valorii minime într-un interval dat ( complexitate $O(N log (U - L)$ ) ).
Pentru fiecare $i$ este de ajuns să aflăm valoarea expresiei $sum[i] - sum[j]$, unde $i - L > j &ge; i - U$. Pentru a determina valoarea optimă pentru $sum[j]$ putem folosi un heap de dimensiune $U - L$, sau putem folosi tehnici de determinare a valorii minime într-un interval dat. Complexitate: $O(N * log(U - L))$.
Altă abordare de aflare a minimelor unor secvenţe de lungime dată (în cazul acesta lungimea este $U - L$ ) a fost prezentată în rezolvarea 'problemei $6$':probleme-cu-secvente@prob6. Folosind acea tehnică obţinem o rezolvare de complexitate liniară.
Altă abordare de aflare a minimelor unor secvenţe de lungime dată (în cazul acesta lungimea este $U - L$ ) a fost prezentată în rezolvarea 'problemei $6$':probleme-cu-secvente#problema-6. Folosind acea tehnică obţinem o rezolvare de complexitate liniară.
O altă rezolvare frumoasă prezentată în [4] este următoarea: spunem că o secvenţă este negativă spre stânga dacă suma oricărui prefix ( în afară de secvenţa în sine ) al secvenţei este negativ sau zero. O partiţie a secvenţei $A = (A{~1~}, A{~2~}, ..., A{~k~})$ este minimală negativă spre stânga dacă fiecare $A{~i~}$ este negativă spre stânga, iar suma elementelor lui $A{~i~}$ este strict pozitivă dacă $i != k$. De exemplu secvenţa $(-4, 1, -2, 3)$ este negativă la stânga, pe când secvenţa $(5, -3, 4, -1, 2, -6)$ nu este. Partiţia $(5) (-3, 4) (-1, 2) (-6)$ este minimală negativă la stânga.
Pentru fiecare element din partiţie ţinem minte un pointer $p[i]$ spre ultimul element din subsecvenţa din care face parte. Fiecare interval $[i, p[i]]$ va corespunde celei mai scurte subsecvenţe care începe în $i$ şi are suma pozitivă. Pentru a determina o soluţie a problemei pentru fiecare $i$ din care poate începe o subsecvenţă de sumă maximă, ne vom plimba cu un pointer $j$ astfel ca $j$ să fie cât mai depărtat de $i$ şi $j - i + 1 <= U$. Obţinem astfel de fiecare dată o subsecvenţă de sumă maximă ce începe în $i$, cu lungimea mai mică sau egală cu $U$. Indicele $j$ va fi întotdeauna un capăt de secvenţă negativă la stânga şi la fiecare mărire a lui $i$ verificăm dacă lui $j$ îi putem atribui valoarea $p[j + 1]$ ( adică dacă $p[j + 1] - i + 1 <= U$ ). Dacă secvenţa de sumă maximă de lungime cel mult $U$ ce începe în $i$ are lungimea mai mică decât $L$, atunci secvenţa de sumă maximă cu lungimea cuprinsă între $L$ şi $U$ are lungimea exact $L$. Complexitate: $O(N)$.
Pentru fiecare element din partiţie ţinem minte un pointer $p[i]$ spre ultimul element din subsecvenţa din care face parte. Fiecare interval $[i, p[i]]$ va corespunde celei mai scurte subsecvenţe care începe în $i$ şi are suma pozitivă. Pentru a determina o soluţie a problemei pentru fiecare $i$ din care poate începe o subsecvenţă de sumă maximă, ne vom plimba cu un pointer $j$ astfel ca $j$ să fie cât mai depărtat de $i$ şi $j - i + 1 &le; U$. Obţinem astfel de fiecare dată o subsecvenţă de sumă maximă ce începe în $i$, cu lungimea mai mică sau egală cu $U$. Indicele $j$ va fi întotdeauna un capăt de secvenţă negativă la stânga şi la fiecare mărire a lui $i$ verificăm dacă lui $j$ îi putem atribui valoarea $p[j + 1]$ ( adică dacă $p[j + 1] - i + 1 &le; U$ ). Dacă secvenţa de sumă maximă de lungime cel mult $U$ ce începe în $i$ are lungimea mai mică decât $L$, atunci secvenţa de sumă maximă cu lungimea cuprinsă între $L$ şi $U$ are lungimea exact $L$. Complexitate: $O(N)$.
h2(#prob10). Problema 10 ('Secvenţa 3':problema/secv3)
h2(#problema-10). Problema 10: 'Secvenţa 3':problema/secv3
Gigel este o persoană cu o imaginaţie foarte bogată, mai ales când doarme! Într-o noapte a visat că are de îndeplinit o sarcină foarte biza: trebuie  aleagă o secvenţă (adica un subşir de elemente care apar pe poziţii consecutive în şirul iniţial) din $N$ elemente pentru care se cunosc costul şi timpul. Secvenţa aleasă trebuia să fie de lungime minim $L$ şi maxim $U$, iar suma costurilor elementelor secvenţei împărţiţă la suma timpurilor elementelor secvenţei să fie maximă $(1 <= L <= U <= N <= 30 000)$.
bq. Se dă un şir de $N$ elemente pentru care se cunosc două informaţii: costul şi timpul. O secvenţă este un subşir de numere care apar pe poziţii consecutive în şirul iniţial. Se caută o secvenţă din cele $N$ elemente care să fie de lungime minim $L$ şi maxim $U$, iar suma costurilor elementelor secvenţei împărţiţă la suma timpurilor elementelor secvenţei să fie maximă. Restrictii: $1 &le; L &le; U &le; N &le; 30 000$.
h3. Exemplu:
h3. Rezolvare:
Procedăm ca la problema $5$ şi căutăm binar valoarea optimă. Şirul va fi transformat în $b[i] = c[i] - t[i] * X$. Acum trebuie să mai rezolvăm subproblema care cere să determinăm o subsecvenţă de sumă maximă pentru care lungimea se află între $L$ şi $U$. Această subproblemă a fost soluţionată în problema anterioară, unde s-a găsit un algoritm liniar. Astfel soluţia acestei probleme are complexitatea $O(N log C)$.
Procedăm ca la 'problema $5$':probleme-cu-secvente#problema-5 şi căutăm binar valoarea optimă. şirul va fi transformat în: $b[i] = c[i] - t[i] * X$, $i = 1..N$. Acum trebuie să mai rezolvăm subproblema care cere să determinăm o subsecvenţă de sumă maximă pentru care lungimea se află între $L$ şi $U$. Această subproblemă a fost soluţionată în 'problema anterioară':probleme-cu-secvente#problema-9, unde s-a găsit un algoritm liniar. Astfel soluţia acestei probleme are complexitatea $O(N * log C)$.
h2(#prob11). Problema 11 ('XorMax':problema/xormax)
h2(#problema-11). Problema 11: 'XorMax':problema/xormax
Paftenie este un elev eminent. De multe ori îşi pune întrebări care au sau nu răspunsuri. De data aceasta i-a venit o idee nouă. El are un şir de $N$ numere întregi nenegative şi vrea să aleagă o secvenţă a şirului $(a{~i~}, a{~i+1~}, ..., a{~j~})$ astfel încât $a{~i~} xor a{~i+1~} xor ... xor a{~j~}$ să fie maxim ({$1 <= N <= 100 000$}, numerele şirului sunt strict mai mici decât $221$ ).
bq. Se dă un şir de $N$ numere întregi nenegative.  se aleagă o secvenţă a şirului, $(a{~i~}, a{~i+1~}, ..., a{~j~})$, astfel încât $a{~i~} xor a{~i+1~} xor ... xor a{~j~}$ să fie maxim. Restrictii: $1 &le; N &le; 100 000$ si $a{~i~} < 221$ cu $i = 1..N$.
h3. Exemplu:
h3. Rezolvare:
Suma _xor_ a două numere este de fapt adunare binară fără transport, fapt care o face similară operaţiei _modulo_. Problema e asemănătoare cu cea a subsecvenţei de modul maxim. Vom obţine toate sumele _xor_ parţiale şi pentru a vedea pentru $sum[i]$ perechea optimă cu care crează o sumă cât mai mare trebuie să găsim acea sumă $sum[j]$ astfel că fiecare bit al lui $sum[i]$ să fie diferit de fiecare bit al lui $sum[j]$, dacă acest lucru este posibil. Pentru a face această căutare cât mai eficientă, putem menţine sumele $sum[i]$ ca şiruri de caractere $0$ sau $1$ într-un _trie_ [5]. Structura de trie pentru cazul când alfabetul are dimensiunea $2$ este identică cu cea de heap. Această soluţie are complexitatea $O(N log C)$.
Suma _xor_ a două numere este de fapt adunare binară fără transport, fapt care o face similară operaţiei _modulo_. Problema e asemănătoare cu cea a subsecvenţei de modul minim. Vom obţine toate sumele _xor_ parţiale şi pentru a vedea pentru $sum[i]$ perechea optimă cu care crează o sumă cât mai mare trebuie să găsim acea sumă $sum[j]$ astfel că fiecare bit al lui $sum[i]$ să fie diferit de fiecare bit al lui $sum[j]$, dacă acest lucru este posibil. Pentru a face această căutare cât mai eficientă, putem menţine sumele $sum[i]$ ca şiruri de caractere $0$ sau $1$ într-un _trie_ [5]. Structura de trie pentru cazul când alfabetul are dimensiunea $2$ este identică cu cea de heap. Această soluţie are complexitatea $O(N * log C)$.
h2(#probp). Probleme propuse
h2(#probleme-propuse). Probleme propuse
Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, autorul vă sugerează rezolvaţi următoarele două probleme:
Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, puteţi rezolva următoarele probleme:
* 'Balans':problema/balans
* 'Struţi':problema/struti
* 'Deque':problema/deque
* 'Trie':problema/trie
* 'Maxq':problema/maxq
h2(#bibliografie). Bibliografie
1. Lica Dana, _Arbori de intervale (Segment Trees)_, GInfo 15/4
2. Negruşeri Cosmin, _Căutări Ortogonale, Structuri de date şi aplicaţii_, GInfo 15/5
3. Takaoka T., _Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication_
4. Kuan Yu Chen, Kun Mao Chao, _On the Range Maximum-Sum Segment Query_
5. Yaw Ling Liu, Tao Jiang, Kun Mao Chao, _Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecolar Sequence Analysis_
6. Vladu Adrian, Negruşeri Cosmin, Ginfo Noiembrie 2005
7. T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm
 
# Dana Lica - '_Arbori de intervale şi aplicaţii în geometria computaţională_':arbori-de-intervale
# Cosmin Negruşeri - '_Căutări Ortogonale: Structuri de date şi aplicaţii_':cautari-ortogonale
# Takaoka T. - '_Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication_':http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf
# Kuan Yu Chen, Kun Mao Chao - '_On the Range Maximum-Sum Segment Query_':http://www.csie.ntu.edu.tw/~kmchao/papers/2007_DAM_RMSQ.pdf
# Yaw Ling Liu, Tao Jiang, Kun Mao Chao - '_Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecolar Sequence Analysis_':http://www.csie.ntu.edu.tw/~kmchao/seq2003/mslc.pdf
# T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3553