|
Titlul: 713 Curent Scris de: Adrian Diaconu din Mai 24, 2008, 12:31:57 Aici puteţi discuta despre problema Curent (http://infoarena.ro/problema/curent).
Titlul: Răspuns: 713 Curent Scris de: Paul-Dan Baltescu din Iunie 08, 2008, 17:26:02 In timpul concursului, am primit instiintare ca nu exista zile in care apar si update-uri si query-uri. Cred ca ar trebui completat enuntul problemei.
Titlul: Răspuns: 713 Curent Scris de: Adrian Diaconu din Iunie 08, 2008, 18:30:31 Am modificat un pic o restrictie. Cred ca este ok asa.
Titlul: Răspuns: 713 Curent Scris de: Paduraru Ciprian - Ionut din Februarie 26, 2009, 15:49:48 Legat de aceasta problema...am si eu o mare nedumerire in legatura cu solutia oficiala. In aceasta solutie se face un arbore de intervale pentru Arsi pentru a vedea daca exista sau nu noduri arse pentru fiecare subarbore insa ce nu pricep eu este ce e cu acel "S". Este tot arbore de intervale ? pentru ca daca e tot arbore de intervale, nu pricep cum ai putea pleca de la un nod si actualiza pana la radacina... Desigur foarte simplu este sa parcurgi arborele dintr-un nod in radacina dar astfel nu se obtine log N in cel mai prost caz....poate cineva sa ma lamureasca si pe mine sa dea un detaliu ceva despre acest "S" ? :'(
PS: In solutie apare urmatoarea exprimare: ": pentru fiecare interval retinem numarul de noduri accesibile din nodul radacina corespunzator intervalului S[nod](dupa cum am precizat mai sus un interval din secventa este echivalent cu un subarbore din arborele dat la intrare) " . Daca facem un arbore de intervale obisnuit ( [1...mij....N] ) , nu ai de unde sa stii pentru anumite intervale ce nod radacina au, pentru ca evident pot avea mai multe noduri radacina... Titlul: Răspuns: 713 Curent Scris de: Mihai Jiplea din Martie 24, 2010, 14:50:26 Se pare că nu trec de 35 de puncte din cauza unui "Memory limit exceeded". Am încercat să fac tot felul de optimizări și degeaba..Am înlocuit mergesort-ul cu quciksort, am renunțat la vectorul de tați, la vectorul de vizite ptr. parcurgerea dfs, am reținut arborele ca graf orientat, dar se pare că tot nu e de ajuns.
Probabil problema stă în modul în care țin arborele de intervale. Folosesc o alocare dinamică iar fiecare nod are 2 int-uri și 2 pointeri spre arborii din st și din dreapta. Mă poate lămuri cineva? Titlul: Răspuns: 713 Curent Scris de: Andrei Misarca din Martie 24, 2010, 15:01:35 Aloca arborele de intervale static. Dacă îl dai de 4*dimensiunea maximă ar trebui să fie suficient.
Titlul: Răspuns: 713 Curent Scris de: Petru Trimbitas din Martie 25, 2011, 19:56:10 Cei care luati incorect pe testul 13 incercati sa mariti dimensiunile vectorilor :D
|