220 SequenceQuery

[•greco]

Aici puteţi discuta despre problema SequenceQuery.

[•wefgef]

a facut cineva in O(N + M * sqrt(N)) ?  intra in timp?

[•Florian]

Cum pot face la problema asta k sa nu caut de mai multe ori in aceleasi secvente? Am facut o rezolvare in care cautam secventa de suma maxima in mod liniar pentru fiecare pereche de indici, insa iau doar 60, cu tle pe celelalte. Care este ideea de baza a rezolvarii?

[•Binary_Fire]

Trebuie sa folosesti un arbore de intervale pentru a raspunde in O(logN) fiecarei intrebari . In numarul de ianuarie 2006 Ginfo gasesti doua metode de rezolvare a problemei .

[•Marius]

Cauta la ONI 2007.

[•wefgef]

Cauta la ONI 2007.

Problema Maxq http://infoarena.ro/problema/maxq

Este exact aceeasi problema, doar ca ai si update-uri de facut.

[•Dastas]

Trebuie sa folosesti un arbore de intervale pentru a raspunde in O(logN) fiecarei intrebari . In numarul de ianuarie 2006 Ginfo gasesti doua metode de rezolvare a problemei .

Ai putea da un link catre articol, ca nu-l gasesc nicaieri. Am gasit unul despre arbori de intervale si aplicatii in geometrie (am inteles ce e un astfel de arbore din el), dar sincer nu stiu cum l-as putea aplica in problema... iar solutia de la oni nu prea e explicata, si as vrea si eu sa inteleg cum se poate face, daca poate cineva explica sau da un link..

Am vazut ce se retine in fiecare nod in solutia de la maxq, dar in rest nu prea e explicat...

Multumesc.

[•astronomy]

Citeste intai articolul http://infoarena.ro/arbori-de-intervale, dar pe larg. E foarte bine explicat acolo, sunt si implementari la probleme. Legat de ce retii intr-un nod la problema asta, sa spunem ca ai intervalul [st,dr] si ai vrea sa-ti calculezi secventa de suma maxima si mai ai [st,mid], [mid+1,dr] pentru care deja ai procesat informatiile. Ai niste cazuri acum: maximul e ori cel din dreapta ori cel din stanga, sau poate o secventa cu elemente si din dreapta si din stanga. Daca e o secventa cu elemente si din stanga si din dreapta e clar ca e urmatoarea secventa: A[mid], A[mid-1]... A[mid-k] (astfel incat A[mid]+A[mid-1]+..+A[mid-k] = maxim si mid-k >= st) A[mid+1], A[mid+2], .. A[mid+p] (astfel incat A[mid+1]+A[mid+2]..+A[mid+p] = maxim si mid+p <= dr).

[•Dastas]

Multumesc... o sa incerc sa vad daca-mi iese ceva..