258 Alpin

[•filipb]

Aici puteţi discuta despre problema Alpin.

[•tm_radu]

Care ii complexitatea oficiala? ca iau tle pe 2 teste....

[•filipb]

Teoretic pe lista de probleme e O(N^2 log N), se poate insa si O(N^2 + HMAX), unde HMAX e altitudinea maxima.

[•tm_radu]

Banuiesc ca O(n^2+HMAX) se scoate folosind alt tip de sortare....am scos O(N^2) acum insa tot iau TLE pe ultimul test...sa fie oare de la faptul ca declar siruri de 1000000 de int-uri?

[•filipb]

O(N^2+HMAX) folosind radixsort, in loc de quicksort. Eu am optimizat citirea si am incercat sa folosesc cat mai putina memorie ( doar 2 matrici 1024 x 1024 ). E adevarat, limita de timp e un pic cam stransa ( ca si la struti de altfel ), dar mie imi intra destul de bine in timp. E mai bine sa fie limita cat mai mica pentru o programare mai ingrijita.

[•tm_radu]

Eu n-am folosit radisort, ci numsort, care foloseste un pic mai multa memorie....probabil de acolo ii TLE-ul. O sa incerc si cu radix sort sa vad daca reusesc. mersi de sfaturi

[u-92]

incearca O(N^2) fara nicio sortare.. asa sigur iti va intra in timp

[•tm_radu]

Si cum pot sa o fac fara sortare? 

[u-92]

faci ceva de genul C[ i ][ j ]  = lg. maxima pana in (i, j) cu memoizare.. nu ai nevoie de sortare

[•tm_radu]

Ce-i memoizarea? 

[•filipb]

http://www.dcs.ed.ac.uk/home/stg/NOTES/node92.html, poate o sa te lamureasca, macar in mare ( nu e mare lucru memoizarea asta ).

[•tm_radu]

Ok, mersi de sfat.... o sa caut mai mult despre asta

[•Marius]

Ok, mersi de sfat.... o sa caut mai mult despre asta

Sa nu uiti sa te uiti si in Introducere in Algoritmi.

[•cristy]

are ceva special testul 4?...adica...am TLE pe el, restu imi intra lejer in timp...dar pe asta iau TLE...si vad ca altii scot 0.15s pe el...fac o lista cu toate nodurile din care nu se mai poate cobori...dupa care fac un fel de parcurgere...ideea e buna...nu am nici un fel de sortare...cu sortare cum se face?...ca nu imi trece prin minte nimic...

[•Marius]

Folosind sortare poti sa faci in urmatorul hal: sortezi crescator in timp liniar toate altitudinile, dupa care pornesti de la cea mai mica altitudinea catre cea mai mare si actualizezi vecinii casutei.

[•cristy]

asta inseamna ca faci in N log N sortarea si N^2 parcurgerea finala...hmm...traba sa mai gandesc putin problema asta...ca pur si simplu...iau TLE pe 2 teste...cand cum...

[vladut.forum]

N^2 cu meimoizare is the best!!!

[•pauldb]

asta inseamna ca faci in N log N sortarea si N^2 parcurgerea finala...hmm...traba sa mai gandesc putin problema asta...ca pur si simplu...iau TLE pe 2 teste...cand cum...

Incearca sa nu faci sortarea in N log N, ci in O(MaxVal) [cum se si precizeaza mai sus] ca merge mai repede si incearca sa folosesti cat mai putina memorie...pe mine m-a ajutat 

[Tabara Mihai]

Eu iau 60 de puncte cu 2 matrici 1024*2024 si una de 1024*1024*2 pentru reconstituirea drumului.

Am folosit QuickSort-ul pentru sortare si apoi pentru fiecare element din vectorul sortat ii compar vecinii si etc..

 

E ciudat fiindca iau WA pe testele 1,3,4 si TLE pe ultimul binenteles.In mod normal ar trebui sa mearga de 90...

[Later Edit] Am reparat greseala.In conditia de mentinere in interiorul matricii pusesem un "||" in loc de "&&" ...

Acuma merge de 90. 

[Tabara Mihai]

http://www.dcs.ed.ac.uk/home/stg/NOTES/node92.html, poate o sa te lamureasca, macar in mare ( nu e mare lucru memoizarea asta ).

As incerca si eu cum spuneti voi insa nu imi merge link-ul de la "memoizare".

[u-92]

da un search pe google la "memoization"

[Tabara Mihai]

100.       
Multumesc tuturor pentru ajutor.
(*In special lui Marius  ).Raman dator.

 

[•Binary_Fire]

Hmm , ciudata problema ( sau mai bine zis implementarea mea o fi devina ). Am folosit radix sort pentru sortare, dar cam multa memorie am utilizat : 2 matrici de 1024x1024 si 2 vectori cu 2 campuri de 1024x1024 lungime. Pentru radix sort folosesc ca sortare intermediara a cifrelor count sort, si am optimizat citirea folosind fgetc(). Si totusi am luat numai 70 pct restu tle ( cu qsort luam 80  ) .
Pana la urma am folosit memoizarea. Totusi is curios ce ar fi trebuit sa fac sa iau 100 cu prima metoda.

[•filipb]

Memoria e mare consumatoare de timp! Doi vectori suplimentari de 1024x1024 deja inseamna o incetinire semnificativa.

[•Binary_Fire]

Interesant, mi se pare destul de greu sa implementezi de 100 pct problema folosind metoda asta.
Oricum thanks pentru reply.