376 Regiuni

[•Bluedrop_demon]

Imi bat capul de cateva zile cu problema asta si nu-mi vine nici o idee pentru O(n*m). Am facut O(n*m*log m) si imi sare din timp pe toate testele. Imi dati si mie un hint mai explicit pls?

[•devilkind]

http://infoarena.ro/preoni-2007/runda-4/solutii  <-- vezi dak gasesti aici vreo ceva util

[•Bluedrop_demon]

Am facut la fel Doar ca eu am folosit DEI si din cate stiu recursivitatea e mai inceata  dar totusi... o data ce s-au format doua grupuri, trebuie sa vezi daca le imparti iar...

Cum se poate face altfel ?

[•devilkind]

nu vad la ce ai avea nevoie asa mare de recursivitate. Pur si simplu parcurgi dreptele si imparti grupurile care le ai deja in functie de acea dreapta.

[•Bluedrop_demon]

Pai daca tin minte grupurile ca vectori, ori trebuie sa elimin un element o data ce il pun in alt vector, ceea ce inseamna ca imi iese din timp, ori ii mai adaug o variabila care imi spune daca mai apartine vectorului respectiv sau nu, caz in care sare din memorie.

So... banuiesc ca sunt foarte batut in cap  dar tot as vrea sa ma ajute cineva....

[•devilkind]

pai un vector sa zice pct in care retii punctele si ink un vector gr in care retii grupul din care face parte punctul respectiv. La fiecare pas parcurgi vectorul, imparti grupurile, si sortezi punctele dupa grup. Toate astea se fac in o(n) sau n log n depinzand de sortarea care o aplici.

[•Cosmin]

Nu sortezi nimic ... pur si simplu ai niste liste de puncte pe care le imparti dupa drepte si gata.

[•Bluedrop_demon]

Sunt perfect de acord. Este chiar solutia care am trimis-o la in timpul concursului. Numai ca acuma iese din memorie si ia numai 10 puncte. Sau poate am gresit eu undeva. Desi nu cred fiindca am scris-o de la capat de doua ori...

[•Cosmin]

Pai sunt destui care au rezolvat-o de 100 ...

[•devilkind]

Cosmin, tu listele alea le tii alocate dinamic banuiesc?? dak am inteles eu cum trebuie algoritmu tau la tine fiecare grup reprezinta o lista alocata dinamic iar la fiecare pas scoti din lista aia anumite elemente pe care le bagi intro lista noua???
Dak asta e ideea pe care ai mers si tu Pandia Gheorghe incearca sa aloci dinamic acele liste, ptr ca altfel nu va intra in memorie.
Sper ca am inteles eu cum trebuie.

[•Bluedrop_demon]

Listele sunt alocate dinamic (simplu inlantuite). Asa a fost de prima data. Ultima sursa pe care am trimis-o (care are tot 10p ) nici macar nu mai retine dreptele intr-un vector, ci deschide din nou fisierul de intrare citind cate o dreapta la fiecare pas. Toate testele pe care i le-am dat eu functioneaza perfect.... dar eu nu stiu sa masor memoria. Daca poate cineva sa se uite pe sursa mea pls sa lase un mail unde sa o trimit, sa-mi spuna unde ma poticnesc  .

Va multumesc...

P.S. Imi puteti spune Geo

[•Cosmin]

m-am uitat. s-ar putea sa fie prea putina memorie pentru pascal ... ai putea sa nu folosesti liste deloc ci 2 vectori de dimensiune 100, si inca 2 vectori care spune unde incepe un grup si unde se termina.

[•Bluedrop_demon]

Multumesc mult! Implementarea s-a dovedit de 100p. De altfel, m-am tot gandit cum sa tranform DEI-ul recursiv intr-un algoritm iterativ si nu stiu de ce nu mi-a venit ideea sa tin minte in alti doi vectori unde incepe si unde se termina un grup! Dar oricum, bine ca e ok - invatatura de minte pentru mine sa ma "lafaiesc" in mai putina memorie!
 

[•sima_cotizo]

Am trimis o sursa care are doar declararile, citirea... si include <list> <cstdio> si <utility> ... la mine acasa executabilul are vreo 1.1MB(compilat in linux cu aceleasi flaguri ca si voi), dar evaluatorul il lasa sa ruleze... pana la urma dimensiunea executabilului se ia in calcul?

[•Florian]

Rezolv in O(N*M) cu hash. Iua 90 de puncte, cu WA. Banuiesc ca e de la coliziuni [ pe care nu le tratez in niciun fel ]. Codul meu e cam asa:

             hash = 0; P = 1;
      for(j=1;j<=n;++j)
      {
         pz = a[j]*x[ i ] + b[j]*y[ i ] + c[j];
         if(pz<0) hash = (hash + P*'a') % Mod;
         else hash = (hash + P*'b') % Mod;
         P = (P*B)%Mod;
      }
      h[ i ] = hash;

Fac asta pt fiecare punct i. Sortez apoi h[] si numar platourile. Mod = 666013 si B = 26. Imi puteti propune o fctie hash mai buna?  Multumesc!

LE: Am luat 100, facand cate doua functii hash diferite pt fiecare vector. Cred totusi ca asta e bulaneala. Cum se trateaza coliziunile ? [renuntand la bulaneli de genul celei curente ]

[•retrograd]

Solutia mea are 4 vectori de 1001 componente, plus cateva variabile. Am primit MLE pe toate testele. Schimb din citirea cu stream-uri in citirea standard, MLE pe 9 teste. Poate sa imi explice cineva de ce se intampla asta?

P.S: Matematica de liceu imi spune ca 4*1000 = 4000 var = 16000 bytes = 16 kb. Limita este de 256kb.

[•klamathix]

Matematica de liceu, deși impecabilă, nu ia în calcul faptul că programul mai folosește memorie pe lângă ce declari tu pentru librării și alte lucruri de genul ăsta. S-a mai scris asta pe topic-ul ăsta. Am schimbat oricum limita fiindcă nu cred că mai sunt de actualitate constrângeri din astea obscene la memorie.

Off-topic: Învață STL și folosește containerii de acolo, nu te agita să aloci dinamic.

[•retrograd]

Vectorii aia de care ziceam eu intr-un final i-am alocat dinamic (n+1 componente) si tot acelasi rezultat. Am incercat si stl pentru memorie, initial folosisem map pentru a stoca valorile distince, dar dupa ce am vazut MLE, m-am gandit ca e din cauza campurilor suplimentare pe care le aloca de regula containerii stl. Chiar si asa, 4 vectori mi se pare rezonabil, dpdv al memoriei.

[•retrograd]

Update: Am reuploadat sursa si memoria e in jur de 260-270kb / test. Am citit in sectiunea de comentarii ca si headerele consuma memorie. Ce altceva imi provoaca asa un memory leak? Daca e codul, de ce anume depinde consumul asta? (linii de cod, atribuiri...)

[•depevlad]

Eu am facut cu vectori pentru grupele de puncte. Memoria este clar O(n) - am 3000 de shorturi pentru linii, si inca aprox. 3000 pentru puncte. De fiecare data cand introduc un punct intr-o grupa, il scot din alta, deci nu se pot sa se umfle vectorii aia. Totusi, iau MLE pe testul 9.

http://www.infoarena.ro/job_detail/1474698 - aici e borderoul de evaluare.

Poate sa imi spuna cineva de ce iau MLE si ce pot sa fac sa scap de el?

Multumesc anticipat.