036 Cutii

[•svalentin]

am submitat codul tau pe infoarena si uite ce primesti:

Cod:

TEST 1	...[0.01s]...	erai aproape.. dar ai gafat
TEST 2	...[0.01s]...	belea.. ai gresit la greu..
TEST 3	...[0.02s]...	belea.. ai gresit la greu..
TEST 4	...[0.01s]...	belea.. ai gresit la greu..
TEST 5	...[0.38s]...	belea.. ai gresit la greu..
TEST 6	...[0.38s]...	belea.. ai gresit la greu..
TEST 7	...[0.38s]...	belea.. ai gresit la greu..
TEST 8	...[0.39s]...	belea.. ai gresit la greu..
TEST 9	...[0.38s]...	belea.. ai gresit la greu..
TEST 10	...[0.38s]...	belea.. ai gresit la greu..

eu nu vad nici un "RUN ERROR - Invalid memory reference"  

[•tudalex]

acum doua zile dadea "RUN ERROR - Invalid memory reference" acum nu mai da. Poate a fost evaluatorul.

[tmac]

am cateva nelamuriri :

1. AIB(arbori indexati binar respectiv arbori de arbori indexati binar) nu se pot folosi pentru a determina maximul, din cate stiu eu.
2. La arborii de intervale bidimensionali cu pcte si valoare cum pot determina maximul ? stiu sa numar cate puncte sunt, ca e usor de cautat binar indicii in vectorul respectiv, dar cum aflu maximul portiunii aleia dintre indici ... ; cum ar trebui sa fac inserarea de exemplu ? ca este clar ca trebuie adaugate punctele in ordinea sortarii dupa o coordonata, nu toate de la inceput ....  .
 

[u-92]

AIB se pot folosi pentru a determina maximul, dar numai pt portiuni de genul 1->x respectiv (1,1) -> (x,y)

[tmac]

ah da asa e   ce n00b sunt. dar cum pot afla min/max in 2D cu arbori de intervale ? mar interesa si asta ... ms f mult

[•filipb]

Pentru arbori de intervale 2D, te gandesti pur si simplu ca in fiecare nod al arborelui cu o dimensiune ai un alt arbore de intervale. Parcurgerea acestui arbore se face in felul urmator: daca de exemplu vrei sa strabati regiunea [x1, y1, x2, y2], atunci parcurgi toate nodurile care alcatuiesc [x1, x2] ( fiecare astfel de nod fiind un alt arbore de intervale ) si in acesti noi arbori parcurgi informatia dorita pt. [y1, y2] ( in fiecare nod initial ). Deci poti avea maxim O(logM) intervale pt. [x1, x2] si pentru fiecare astfel de nod, alte maxim O(logN) intervale pe [y1, y2], deci o complexitate finala de O(logN * logM), pe query / update.

[tmac]

am inteles, ms mult. dar am o intrebare : cum pot sa fac o implementare eficienta ? adica si spatiu si timp, ca pare cam costisitoare construirea ...   ? poate nam inteles io bine daca ai putea sami dai detalii... ms f mult ;

[•wefgef]

eu cred ca te complici cam mult.

daca sortezi numerele in functie de o dimensiune, ai redus problema la aflarea celui mai lung subsir crescator maximal. doar ca in acest caz relatia "<" trebuie sa fie adevarata ptr amandoua dimensiunile care ti-au ramas. o implementare in O(n^2) cred ca stii si tu, insa aceasta nu e destul de buna. poti folosi in schimb un AIB bidimensional ptr a reduce complexitatea la O(n log^2 n).

[tmac]

am luat 100 p cu AIB ... mam prins ca poti calcula maxim pt (1.. x) credeam ca nu poti deloc. ma interesau si arborii de intervale 2D ca stiu doar reprezentarea aceea din ginfo, cu lista sortata dupa y in fiecare nod si e greu sa calculezi maxim pe ea.

[•Aymd]

eu ma refeream la faptul ca sortarea nu e buna (la inceput pune in v produsul dimensiunilor)

Nu am nimic impotriva ... doar sa fi spus si de ce ...

Sirul dimensiunilor L, l, h au o proprietate ... deci sirul poate fi citit direct sortat.

[•CezarMocan]

Se poate lua 100 daca se face subsir crescator maximal in n log n?? As vrea sa fac asa, dar adevarul e ca nu prea l-am inteles... 

[•cos_min]

subsirul crescator maximal se poate face si in n^2 si este mult mai usor de inteles 

l(i) cel mai lung subsir crescator care se termina cu a(i). Dupa ce vei avea pt fiecare i calculat => maximul ( l(i), i = 1..n ) este subsirul crescator maximal.

[•CezarMocan]

Da, pe ala il stiu, dar vreau sa invat ceva nou cu problema asta. (si in plus nu-mi intra in timp "bulaneala"). Si mi-e o lene sa ma apuc de AIB...  . De aia intrebam de el...

[•Marius]

Gaseste o motivatie daca iti este lene. 

Sa iti zic eu una: e mai usor si mai elegant cu AIB.

[•Tabara]

Da, pe ala il stiu, dar vreau sa invat ceva nou cu problema asta. (si in plus nu-mi intra in timp "bulaneala"). Si mi-e o lene sa ma apuc de AIB...  . De aia intrebam de el...

Daca ai manualul de clasa XI-A, de Dana Lica si Mircea Pasoi, cauta la pagina 240-241.E explicatie si implementare 

 

[later edit] Cred ca il gasesti si pe net 

[•CezarMocan]

Este si in GInfo, si mi l-a explicat un prieten, dar sunt asa de batut in cap ca nu l-am inteles...  . Vreau sa-l gasesc undeva explicat ca pentru prosti...
@Marius Stroe: Da, ai dreptate... Totusi eu zic ca e mai "prioritar" subsiru crescator maximal in n log n. Am mai facut AIB (la datorii de exemplu), dar niciodata in 2 dimensiuni... si totusi... zici ca e mai usor??

[•amadaeus]

Acum imi dau seama ca nu (cred ca) se poate aplica algoritmul in n log n pentru cel mai lung subsir crescator la problem asta, deoarece nu exista relatie de ordine totala pe multimea punctelor din plan (o astfel de relatie ar fi echivalenta cu o relatie de ordine pe multimea numerelor complexe...). Asadar, nu se poate face cautarea binara din algoritmul in n log n... curaj cu AIB

[zombie_tester_2]

nu exista cutii cu una dintre cele trei dimensiuni x ,y sau z egale nu ?

[•wefgef]

Nu.

[•Bogdan_tmm]

ìmi lasa si mie cineva niste teste mai mari?(si mijlocii dak se poate )

[•alex_mircescu]

http://infoarena.ro/job_detail/222530
iau 10 puncte si sunt la sfarsitul puterilor... habar n-am ce are...
si nu's din ala care cere mura'n gura... m-am chinuit... eh.. nu mai zic...
un test ceva... ca sa-mi busheasca programu' ?   

[•wefgef]

Programul nu buseste nimic. Pur si simplu algoritmul pe care il folosesti nu e corect. In plus are complexitatea O(N^2).

[•Bogdan_tmm]

Cu un quick sort si un scmax cu programare dinamica iei 0 puncte?

[•CezarMocan]

S'a discutat si inainte despre asta. Se ia 40, cu TLE. Complexitatea optima este alta.

[•Bogdan_tmm]

Mda ma apuc sa vad ce scrie p'aici.ms