|
Titlul: 220 SequenceQuery Scris de: Tiberiu-Lucian Florea din Aprilie 02, 2006, 01:42:35 Aici puteţi discuta despre problema SequenceQuery (http://infoarena.ro/problema/sequencequery).
Titlul: Răspuns: 220 SequenceQuery Scris de: Andrei Grigorean din Aprilie 02, 2006, 22:01:41 a facut cineva in O(N + M * sqrt(N)) ? intra in timp?
Titlul: Răspuns: 220 SequenceQuery Scris de: Florian Marcu din Mai 25, 2007, 13:30:59 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?
Titlul: Răspuns: 220 SequenceQuery Scris de: Florin P din Mai 25, 2007, 13:37:57 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 .
Titlul: Răspuns: 220 SequenceQuery Scris de: Marius Stroe din Mai 26, 2007, 10:01:36 Cauta la ONI 2007.
Titlul: Răspuns: 220 SequenceQuery Scris de: Andrei Grigorean din Mai 26, 2007, 11:40:33 Cauta la ONI 2007. Problema Maxq http://infoarena.ro/problema/maxq Este exact aceeasi problema, doar ca ai si update-uri de facut. Titlul: Răspuns: 220 SequenceQuery Scris de: Ionescu Vlad din Iunie 02, 2007, 21:03:36 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. Titlul: Răspuns: 220 SequenceQuery Scris de: Airinei Adrian din Iunie 02, 2007, 23:05:48 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).
Titlul: Răspuns: 220 SequenceQuery Scris de: Ionescu Vlad din Iunie 03, 2007, 11:52:02 Multumesc... o sa incerc sa vad daca-mi iese ceva..
|