infoarena

Aici puteţi discuta despre problema Flori (http://infoarena.ro/problema/flori).

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  :-k la trimiteri succesive

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

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 (http://www.space.unibe.ch/comp_doc/c_manual/C/CONCEPT/data_types.html#int) 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.

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

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.

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

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 :D

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 :D

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

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?

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

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)  :D

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

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

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  :-k Si cum adica ce flori au cel putin o fetita comuna? :?

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.

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

Se refera la datele de iesire.

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

Asa, si?  :)

Stie cineva ce e asa special la testul1?  ca imi da incorect ](*,)
E vreun caz particular ?

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

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.

Multumesc pentru raspuns,am reusit sa fac si eu in memorie O(N) si timp O(N^2) cu un deque si mai multi vectori, si deque si vectorii alocati static.Nu imi iesea la inceput deoarece uitasem ca pot fi tipuri(de flori) de 0.

 :D iau pe testele alea mari (cele 4) memorie depasita  644kb respectiv 652kb.. ](*,) http://infoarena.ro/job_detail/351241

 :-' nu stiu daca se mai poate imbunatati ceva pe o matrice de dim 1001 , doar asta am folosit.. si nu inteleg de ce ati micsorat memoria incat sa nu intre pentru asa ceva,..  :-k

..  cum as putea face cu 2 vectori ? :readthis: :eyebrow:

Pentru ca nici la concursul unde s-a dat nu intra asa ceva (la OJI se facea evaluarea pe bordland si puteai declara maxim 128 kb )
Incearca sa faci problema cu multimi disjuncte.  :) Citeste tot forumul si o sa gasesti idei de rezolvare folosind O(N) memorie.

am o intrebare .... de ce nu s-a respectat cerinta de la oji ( n<150 shi k<100) iar timpul de rulare 1 sec
 :wink: :readthis:

Limita de timp a fost modificată pentru că sunt alte medii de evaluare (aici fpc/g++ pe linux, acolo borland pe windows). Încearcă să rezolvi problema cu N și K mai mari, chiar dacă la OJI luai 100 și cu algoritmi mai ineficienți. În fond scopul arhivei este de a învăța, nu de a face puncte.

De curiozitate, pentru testul
ar trebui sa dea
1 3 2
sau
1 2 3 sau altceva?

Mie imi da 1 2 3.

Mersi de raspuns, am reusit cu o solutie foarte ciudata cu seturi si cu bfs. Mersi inca o data.

Puteai sa faci cu paduri de multimi disjuncte.

Eu am facut problema cu paduri de multimi disjuncte si cu o matrice cu niste biti si ideea e ca iau TLE pe testele 6 si 7.
Am o intrebare : Nu se poate lua 100 si cu solutii fara grafuri? Am incercat sa fac si o parsare care da roade , dar obtin Incorect pe testele de la 4 incolo.
Parsarea este aceasta :
Cod :
fin.getline(sir,25000);
aux=0;cnt=0;
for(poz=0;sir[poz];poz++)
            if(sir[poz]>='0' && sir[poz]<='9')
                aux=aux*10+sir[poz]-'0';
            else
             {
                 t[++cnt]=aux;
                 aux=0;
             }
        t[++cnt]=aux;
Imi puteti spune va rog ce gresesc aici sau, daca se poate sa-mi dati testul 4.
Multumesc anticipat!

LE : A iesit cu parsare!  :winner1:

Nu imi intra primul test, dar celelalte da. Are cineva idee de ce?

Edit: Nu mai conteaza. Rezolvarea era gresita, dar imi intra totusi pe 9 teste  :D

limita de timp este destul de stransa, daca imi declar vectorii de int in loc de short int nu intra iar majoritatea au teste cu 200ms

Se poate folosi o matrice de bitset daca trebuie :)

Poate cineva să-mi dea un mic hint în legătură cu primul test? Pe restul testelor merge ok...