|
Titlul: 1408 Calancea Scris de: Heidelbacher Andrei din Iulie 29, 2013, 19:15:02 Aici puteti discuta despre problema Calancea (http://infoarena.ro/problema/calancea).
Multumim lui Eugenie Daniel Posdarascu (http://infoarena.ro/utilizator/eudanip) pentru adaugarea problemei. Titlul: Răspuns: 1408 Calancea Scris de: UAIC.VlasCatalin din August 11, 2013, 09:57:40 Mai dati inca putina memorie ( macar 4 Mb ) ca nu ma pot incadra nicidecum in limita curenta. ](*,)
Titlul: Răspuns: 1408 Calancea Scris de: Heidelbacher Andrei din August 11, 2013, 14:58:13 Aceasta este limita de memorie din timpul concursului. Tu nu ai solutia optima (ai complexitate N * logN). Foloseste un deque pentru a obtine complexitate O(N) si atunci vei consuma mai putina memorie.
De exemplu, solutia mea cu un deque se incadreaza in 4 Mb. Spor! Titlul: Răspuns: 1408 Calancea Scris de: Salajan Razvan din August 12, 2013, 12:33:00 Cum pot scapa de MLE ?
Titlul: Răspuns: 1408 Calancea Scris de: Heidelbacher Andrei din August 12, 2013, 15:11:58 In solutia mea am parcurs sirul de la dreapta la stanga, iar in deque tineam doua informatii: i, pozitia elementului, si next, pozitia primului element din dreapta care e mai mare (in cazul in care nu exista un element mai mare ca el in secventa curenta, retin capatul din dreapta al secventei). Astfel, nu mai am nevoie sa folosesc sume partiale sau alte precalculari care consuma multa memorie.
Totusi, acum am observat ca in concurs, limita de memorie era de 64 MB. Cand a fost adaugata problema la lot nu am observat ca nu corespunde limita de memorie si am presupus ca este corecta. Ne cerem scuze. |