481 Flori

[•DITzoneC]

Aici puteţi discuta despre problema Flori.

[•bogdanhm999]

1)e o problema la lista  de surse trimise la problema asta, adika nu apare
2) ce complexitate ar trebui ? eu am (n*(n/1)*1024/64)=n*(n-1)*16 si iau
TLE ba pe 1 test ba pe 2 la aceiasi sursa  la trimiteri succesive

[•jupanu92]

As putea declara o matrice cu 1001 coloane si 1001 linii  ?? ?de tip int ?

[•fireatmyself]

da. poti sa calculezi memoria inmultind dimensiunea fiecarui tablou cu marimea tipului de date al tabloului si adunand rezultatele. daca ai doar o matrice de 1001 pe 1001 o sa ai 1001*1001*4 bytes ~ 4 MB (o variabila 'int' are 4 bytes). aici gasesti o lista cu dimensiunile tipurilor de date. o variabila 'long long' are 8 bytes.

L.E.: uitandu-ma mai bine la problema am observat ca a fost data la judeteana, deci evaluarea s-a facut pe borland. in borland nu poti sa declari mai mult de 128kb (selectand modelul huge), deci in concurs nu ai fi putut sa declari o astfel de matrice. daca vrei sa te antrenezi pentru la anul, iti sugerez sa lucrezi problemele de la aceste faze pe borland, pentru a fi cat mai aproape de conditiile de concurs.

[•sigrid]

In plus poti rezolva problema folosind decat 2 vectori de 1001 elemente. Incearca sa gasesti o astfel de rezolvare si daca tot nu merge poti eventual sa citesti solutiile oficiale.

Sa ai spor !

[•DITzoneC]

Am micsorat limita de memorie (ca sa fie ca pe borland) si am reevaluat.

Acum nu mai poti declara o matrice de 1000 linii si 1000 coloane.

[•jupanu92]

da Ms ptr sfaturi dar pr asta am mai rezolvato cu matrice dar dupa restrictiile de la oji nu de pe infoarena si acu cred ca tre sa ma gandesc la alta metoda de rezolvare

[•jupanu92]

wow se pare ca toti siau declarat matrice cu  1000 de linii si 1000 de coloane ptr ca doar 2 pers am vazut cu 100 de p din foarte multi

[•fireatmyself]

majoritatea au facut-o asa pt ca incapea fara probleme....dc sa te chinui sa gasesti alta rezolvare cand incape si cu o matrice!

scopul rezolvarii problemelor din arhiva infoarena este antrenamentul. nu este o idee buna spunand ca "merge si asa". evident, daca "merge si asa" in concurs, atunci nu te mai complici, dar pe infoarena ai tot timpul din lume

[•jupanu92]

N-am spus ca nu o sa mai poata sa o faca ci ca o sa se chinuie mai mult ptr ca inainte mergea lejer acu trebuie sa te gandesti la o rezolvare mai eficienta

[•Robybrasov]

am facut mai multe solutii, cea care necesita cea mai putina memorie foloseste 1000 KB unde folosesc o matrice de 1000*1000 de tip byte (in fpc), ca sa retin 0 si 1 pentru fetita/tip de floare
nu imi dau seama cum sa retin datele cu mai putina memorie sau de o solutie care sa nu foloseasca deloc matrice.
imi puteti da vreo indicatie?

[•gabitzish1]

Eu am folosit liste de adiacenta, si am cel mult 248kb memorie.

[•Mishu91]

Complexitatea oficiala cam care este? Pentru ca banuiesc ca O(N^3) cum m-am gandit eu iese cu mult din timp(avand in vedere ca N are valoarea maxima 1000, iar limita de timp este de 0.5 secunde) 

[•wefgef]

Merge O(N^2) cu memorie O(N).

[•Mishu91]

O(N^2)
Asta inseamna ca ar trebui sa verific daca doua fetite au flori comune in O(1)?

[•wefgef]

Nu am gandit asa problema. Eu am incercat sa aflu ce flori au cel putin o fetita comuna

[•Mishu91]

Nu am gandit asa problema. Eu am incercat sa aflu ce flori au cel putin o fetita comuna

Si cum ai scos O(N) memorie? Adica m-am gandit ca pentru fiecare floare sa tin o lista dinamica cu fetitele care au floarea respactiva, dar totusi nu cred ca intra in 640 kb  Si cum adica ce flori au cel putin o fetita comuna?

[•Cristian_B]

Pot spune ca nu m-am chinuit niciodata la o problema mai mult decat la aceasta, am incercat 3 moduri de abordare ale ei ( prima data sa citesc din fisier si sa lucrez cu fisierul care m-a incurcat enorm din cauza ca tabloul cu fetite incepea de pe a 2-a linie, apoi cu matrice care mi-a taiat 2 teste din grupa a 2-a ca am depasit cu 4 kb  in final alta abordare cu matrice mi-a adus 40 de puncte pe infoarena, care, chiar daca sunt 0 in evaluator dar mi se par cele mai muncite  0 puncte vreodata, mesajul meu este offtopic probabil dar sunt curios, functia eoln(f), ori nu stiu eu sa operez cu ea ori ea se lasa pacalita de un spatiu liber la sfarsitul randului sau ce? Btw /bow pentru cei care au rezolvato pana acum.

[•robigi]

pot santreb shi eu un lucru: cand la note scrie: Intr-o grupa numerele de ordine ale fetitelor trebuie date in ordine crescatoare se refera la faptul k datele de intrare sunt astfel scrise sau datele de iesire trebuie scrise crescator?
 

[•gabitzish1]

Se refera la datele de iesire.

[•andrey932]

e problema de la oji din 2006...originala era cu
•   1<=n<=150
•   1<=k<=100
astfel o puteai face cu multimi:)   

[•Florian]

e problema de la oji din 2006...originala era cu
•   1<=n<=150
•   1<=k<=100
astfel o puteai face cu multimi:)   

Asa, si? 

[•doru.nitu]

Stie cineva ce e asa special la testul1?  ca imi da incorect
E vreun caz particular ?

[•xtreme]

Merge O(N^2) cu memorie O(N).
Nu am gandit asa problema. Eu am incercat sa aflu ce flori au cel putin o fetita comuna

Daca nu gresesc , ai folosit doua liste alocate dinamic in care tineai toate fetitele ce detin tipul florii i(i=1,k) si toate tipurile de florii ce detin fetita j(j=1,n).De aici eu cred ca tu ai folosit memorie O(N^2) pe testul de gen: 

1000 1000
1 2 3 4 ... 1000    //linia 1
.
.   
.
1 2 3 4 ... 1000   //linia 1000

Banuiesc ca nu exista niciun test de gen din moment ce ai trecut peste toate folosind O(N^2).
Te rog sa ma corectezi daca gresesc.

[•wefgef]

Nu folosesc alocare dinamica decat pentru afisare (si acolo aloc O(N) memorie).

Poate ca nu este destul de clar cum functioneaza algoritmul meu asa ca il voi explica mai in detaliu:

La prima vedere, problema pare ca ascunde un graf destul de evident: nodurile sunt fetitele, iar muchiile sunt reprezentate de flori. Intre doua fetite exista muchie daca si numai daca au cel putin o floare comuna. Se cere determinarea componentelor conexe.

Eu am abordat altfel modelarea grafului: la mine nodurile sunt reprezentate de flori (am intotdeauna 1000 de noduri), iar muchiile de fetite. Intre doua noduri i si j exista muchie daca si numai daca exista o fetita care sa aiba atat o floare de tip i, cat si una de tip j. Deasemenea si in aceasta modelare se cer componentele conexe.

Pe parcursul algoritmului imi mentin un vector c (initial c[ i ] = i) avand proprietatea ca c[ i ] == c[ j ] daca si numai daca nodurile i si j fac parte din aceeasi componenta conexa. Pentru fiecare fetita noua pe care o citesc, inserez niste muchii in graf, deci s-ar putea ca vectorul c sa se modifice. Ar trebui sa fie destul de clar cum fac modificarile in timp liniar.