infoarena

Aici puteţi discuta despre problema Regiuni (http://infoarena.ro/problema/regiuni).

un O(n*m) intra in timp?

Intra si O(N * M * log M)

clar ma arunc de pe bloc  ](*,), si sper ca data viitoare sa gandesc si sa nu mai incerc cu structuri de date sinucigase

eu am luat 70 cu o(m*log m * (n/30)). (am comprimat niste numere folosind baza 2)

si io tot folosind baza 2 am incercat...exprimam unicitatea unei regiuni in functie de cum era localizata fata de o dreapta.....da nu m-am gandit sa fac cu o matrice de char-uri si am transformat din nou in baza 10....(2.000.000.000 < 1<<1000 ) :P
LE: asta pe langa faptul k puteam doar pana la 1 mil k aveam vectoru in care notam regiunile un int de 1 mil

nu prea aveai nevoie de asa ceva. Eu am folosit o matrice A[ i ][j] - semiplanul in care se afla punctul i fata de dreapta j.

[Later edit] am luat 100 in arhiva  ](*,) trebuia sa construiesc matricea invers. In concurs am mers in principal pe coloane si apoi pe linii, akuma am inversat si am luat 100  ](*,) ](*,) ](*,) ](*,) ](*,)

poi km asa m-am gandit si eu da..... fara matrice :fool:

Da, cred ca mergea fara matrice... Eu de fapt retineam doar linia curenta A[j] = de ce parte a semiplanului e pct j fata de dreapta i... apoi parcurgeam grupurile actuale si pt fiecare daca aveam si pct de o parte si pct de alta, atunci inseamna ca imparteam grupul in doua, si parcurgeam iar lista de pucnte ca sa ii atribui noul grup fiecarui punct "mutat"... iese O(N*M), in concurs am bagat g[ j ][...] in loc de g[ b [j] ][...] si s-a dus toata, ca luam 80 (2 wa) si prindeam finala  :aha:

Aia e, poate la anu...

[LE] acu iau 100... mai gresisem si o limita a unui for  :-'

DP[ i ][ j ] = semnul pe care il are expresia a[ j ]*x[ i ]+b[ j ]*y[ i ]+c[ j ]. (a[ j ], b[ j ], c[ j ] coeficentii dreptei j).
Cu liniile acestei matrici se construia un trie. Raspusul cautat era numarul de frunze pe care il are arborele respectiv. Complexitate O(N*M), memorie O(N*M).

Ideea comprimarii acestei matrici (informatiile de pe linia i pentru primele 31 de drepte erau tinute pe primii 31 de biti ai lui DP[ i ][ 1 ], urmatoarele 31 de drepte pe bitii lui DP[ i ][ 2 ], etc.) si verificand in O( N*(N-1)/2 * M/31 ) daca oricare doua puncte au aceleasi semne fata de drepte, aducea tot 100 de puncte. Acest lucru se intampla din cauza faptului ca este destul de grea generarea unor teste care sa determinie algoritmul tau sa faca acel numar de operatii.

Anul trecut, la barajul pentru selectia lotului largit, problema 'Cifru' a intampinat aceesi dificultate in departajarea unor solutii optime de altele neoptime (neoptime cel putin teoretic).

eu nu verificam in n^2, le sortam in n log n (bineinteles inmultite cu m/31 toate) si verificam numarul de secvente egale. Daca (,) calculezi complexitate pe testul maxim (n=1000, m=1000) vei vedea ca e mai mica decat n*m. 1000*10*35 < 1000*1000 :P
Oricum poate ca e doar parerea mea, dar cred ca la clasa a X-a e cam mult trie. :oops:

Cel mai simplu poti sa consideri semnele ca fiind cifre iar sirul un numar in baza 2 (de exemplu semnul -1 corespunde lui 0 si +1 lui 1) si acum nu ai decat de facut un hash (rabin-karp), adica calculezi numarul asta % un numar prim mare. Daca esti paranoic poti considera mai multe numere prime mari si calculezi restul pentru toate :)

m-am gandit si la asta dar nu am vrut sa ma mai complic cu alocare dinamica (nush hashing static) si mi s-a parut destul de usor de implementat asa, si dupa calculele mele intra in timp. De fapt a si intrat doar ca in concurs am spart linia de cache de prea multe ori (mergeam invers si nu mi-am dat seama :( si am pierdut 30 de pct din cauza asta). Oricum misto problema.

La hash static aloci la inceput un tablou
(cel putin asa inteleg eu sa faci hash static)
Dar ce spuneam eu aici e ca nu ai nevoie de chestia asta, daca 2 elemente au aceleasi chei le consideri egale, adica consideri ca nu apar deloc coliziuni.

nush mi se pare destul de riscant sa nu tratezi coliziunile. Adik dak ai o singura coliziune se duce tot rezultatu ptr ca ai vrut sa optimizezi o operatie acolo. Oricum cred ca mi-am dat seama cum as putea face hashing static cu probabilitate f mica de coliziune, dar nu cred ca poate fi redusa total acea probabilitate. Cred ca singura modalitate de a trata coliziunile 100% corect e cu alocare dinamica.

Tocmai asta e principiul pe care se bazeaza rabin-karp, daca tu tot timpul o sa compari 2 siruri care au chei egale te duci in O(N^3).

Am pus o sursa care zic eu ca e super-ok si ar merita 100 de puncte. In afara de 30 de p nu pot insa obtine. La testele pe care nu le iau primesc "Non-zero exit status" (sursa e in free pascal) :annoyed:. In afara de faptul ca asta inseamna ca programul da eroare undeva, imi puteti spune mai multe detalii despre cum as putea afla de ce se intampla de fapt cand primesc un astfel de mesaj ?

In caz ca ar fi o posibilitate, am verificat sa nu am nicaieri impartire la 0, deci nu e de aici.

la regiuni nu era limita de memorie mai mare ?? (acu e    Limita de memorie   128 kbytes)

s-a schimbat deoarece intrau niste bulaneli. Insa oricum mi se pare cam drastic ptr ca multe solutii corecte au luat 0 (inclusiv a mea). Cred ca ar trebui facuta o alta schimbare ptr ca o solutie care este mentionata in articol ca fiind corecta nu ar trebui sa ia 0.

Pai a fost corecta pentru concurs :P in arhiva e altceva :).

eu am o(n) memorie si nu intra... intr-adevar constanta e cam de 9... dar totusi.... 128...

am un vector pe care vreau sa il sortez in N^2
Daca pun in comentariu cele 2 foruri care imi sorteaza vectorul memoria folosita maxim pe un test este 12kb. Daca trimit sursa cu tot cu for-uri iau memory limit exceeded pe 9 teste. Nu e totusi cam drastica limita?

eu am calculat ca (9 * 1010 * 4 + (ce o mai fi pe acolo)) / 1024 < 40... sigur e 128 kbytes memoria?

eu am 11*1024 * 4 / 1024 = 44 KB si eu MLE pe 9 teste :(

intelegem k in arhiva e altceva da chiar sa nu aiba nimeni mai mult de 10 puncte :-'

:) ne uitam imediat si modificam.

Eu am 100 de puncte cu memoria 128 kb :D :oops:

LE: (Da ... si eu am scris in pascal)

Nu prea am vazut sursa in C cu 100.. Desi sunt deja cateva care ar trebui sa intre... sunt doar 3 surse cu 100 toate in pascal..

It's all good now.

eu pana acuma luam numai signal 11(cu toate k am verificat si pentru un caz de 1000/1000 la mine p calc si nu avea nici o prob), si acum iau MLE si sunt 100% sigur k nu depasesc 256....
LE: sau cel putin nu ar trebui

http://infoarena.ro/job_detail/36450

...sursa in C++...

S-a reevaluat de cand am postat ... Inainte nu era.. si tu folosesti mai mult de 128 K :)

Si sa inteleg ca acum nu mai merge sa faci N*M*logM... nu prea intra matricea pe biti... :)

in mod normal al treb sa intre.... 1024*1024*4/(1024*log1024)=128....

de unde log 1024??
o matrice de 1024x1024 ocupa cam 4 mb. Dak faci comprimarea aia pe biti mai reduci oleaka dar nu cred ca e destul incat sa iti intre.

poi daca faci comprimarea nu mai ai nevoie de 1024 pe 1024 ai nevoie doar de 1024 pe 32, pt ca o linie nu poate sa mai depaseasca 32 de elemente
LE: acuma observai, nu vroiam sa scriu log 1024, treb 32, da ma grabeam ca treb sa ajung la sc  :D
LLE: ok....this might sound weird dar eu fara matrice am memorie folosita de 400kb.....

Imparti la 8, nu la log n .... pt ca memoria se calculeaza in bytes nu in long-i

stiu k e in bytes da ideea era k sizeof(long)=4 bytes, o matrice de 1024/32 are 1024*32*4 bytes adik 32*4=128kb... asta dak nu cumva gresesc eu pe undeva :-'
LE: oricum ce vreau eu sa zic e k daca doar citesc variabilele din fisier in vector imi depaseste memoria(si nu am nici cea mai vaga idee de ce)

intr-adevar matricea aia are 128 de kilo FIX. Dar ce faci cu vectori si cu codul :-'

codul.....poi cred k e esential deci il las asa, iar vectorii sunt 5 integeri de 1024 care au 10 kilo :-'

Nu prea are legatura cu problema, dar e un lucru care mi se pare ciudat la aceasta pb ...
Eu folosesc exact 9 vectori de 1001 elemente (de tip int) si 7 variabile (tot de tip int)
Asta inseamna ca am (7+9*1001) * 4 bytes = 36064, iar in kilobytes ar veni 36064 / 1024 = 35.21 kilobytes
Totusi brderoul de evaluare este urmatorul:

1   24ms   212kb   OK   10
2   0ms   12kb   OK   10
3   8ms   232kb   OK   10
4   4ms   8kb   OK   10
5   8ms   212kb   OK   10
6   12ms   208kb   OK   10
7   16ms   204kb   OK   10
8   20ms   216kb   OK   10
9   28ms   216kb   OK   10
10   32ms   212kb   OK   10
Punctaj total:   100

Poate sa ma lamureasca si pe mine cineva de ce programul meu foloseste asa multa memorie ??
P.S. nu fac nimic recursiv in algoritmul meu ...

La dimensiunea totala a variabilelor se adauga si dimensiunile header-elor folosite.

Ok, ms, nu shtiam asta, desi singurul header care il folosesc e stdio.h care are aprox 16 kb :-?

  deja devine enervanta pb asta
Cam asta am inclus
170 kb+ headerul fstream (10 Kb la mine pe disc ) si iau la toate memory limit exceed   ](*,)

Intr-adevar, deja se cam exagereaza cu limita de memorie. Jumatate din solutiile oferite in articolul de la preONI nu mai sunt bune de nimic. Eu zic ca ar fi mai bine sa se mareasca N-ul si M-ul pentru a opri bulanelile in loc sa se limiteze memoria, chiar daca e mai putin artistic asa.

Unele bulaneli nu le poti limita daca sunt mai rapide ca solutia comisiei :)

[edit] daca e asa enervant, pot sterge solutiile ce folosesc multa memorie din articolul cu solutii :)

   Da totusi cum de iau memory limit exceed cand folosesc 170 KB si limita de 256 ?

Pai s-a zis mai sus ca folosesti ceva memorie in care se tine codul ce se executa ...

nu prea vad cum ar putea rula mai repede o solutie n^2*m mai repede decat una n log n *m :-/.

Nah ce sa zic ... optimizata :)
Oricum solutia in O(n*m) nu are mai mult de 25 de linii ...

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?

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

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

Cum se poate face altfel ?

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.

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....

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.

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

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...

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

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.

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

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.

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!
 :ok:

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?

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:


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?  :-k 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 ]

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.

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.

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.

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...)

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.