Ideea e sa mergi cu toate forurile pana la "n". Eu faceam 6 foruri cu primul pana la "n-5", al doilea pana la "n-4" ... ultimul pana la "n" si primeam "Wong aswer!" doar pe testul 1. La asta m-am referit.

Pt "nash". Si eu primeam "Wrong answer!" pe testul 1 deoarece calculam suma a 6 elemente pana la ultimele 6, in loc sa consider pana cand apare si ultimul element de 6 ori. Poate asta te ajuta 

Nu stiu daca e cea la care te gandesti si nici de ce crezi ca ar fi neortodoxa. Insa am de facut o observatie: Ordonare in O(n*log n) si parcurgere/comparare in O(n) inseamna O(n + n*log n ) si nu O( n*n log n ) deci pana la urma e mai buna decat rezolvarea mea si ar putea obtine un timp mai bun!

O(n*n*log n) cred ca intra in timp. Eu nu fac sortare, de aceea am n^2. Si asta pe cel mai defavorabil caz, deci sunt sanse sa mearga chiar mai rapid. Dupa cum am zis mai sus, solutia mea are 416ms. Dar un O(n*n*log n ) cred ca e suficient.

LE: Pentru edit-ul cu quick sort. Poti folosi Interclasare, care merge mereu in O(n log n) pe orice caz. Quick-sort nu e cea mai rapida, doar ca la raportul timp/memorie e cea mai buna. Dar memorie e suficienta si pentru Interclasare.

Rezolvarea pare ok si ar trebui sa se incadreze in timp. Numai sa nu fi gresit ceva la implementare. Depinde si ce sortare ai folosit. Complexitatea ar trebui sa fie maxim n^2 pe 3 sec. Nu cred sa intre n^3. Incearca alta metoda de sortare, poate o scoti la capat 

Buna marius. Eu am observat 2 probleme, dar nu garantez ca asta e cauza:

                        if (a[i,j]=a[i,k]+a[k,j]) and (b[k,i]+b[k,j]>b[j,i] ) then
                            b[i,j]:=b[i,k]+b[k,j];

1. Nu inteleg de ce compari b[k,i]+b[k,j]>b[j,i]  si apoi atribui b[i,j] := b[i,k]+b[k,j] ? adica le pui pe dos. Prima comparatie ar trebuie sa fie b[i,k]+b[k,j] > b[i,j] nu invers cum ai pus tu. Ai inversat atat i si j cat si i si k.
2. De obicei e bine sa pui caracterul "sfarsit de linie" dupa ultimele date scrise in fisier, daca nu se precizeaza altfel in enunt. Deci dupa ce afisezi matricea b poti sa mai pui un writeln.

In rest pare corect.

P.S. Nu e bine sa postezi surse. Adminii iti vor sterge mesajul!

Mie mi se pare ciudat enuntul la aceasta problema. (Ma refer la observatii) Adica pana la urma cine e a si cine b. Pe undeva am impresia ca se confunda unu cu altul si nu imi dau seama unde ar trebui sa pun eu "b" si unde "a".

De altfel solutia oficiala nu prea are treaba cu rubrica de observatii, sau cel putin nu asa cum le-am inteles eu. Imi clarifica si mie cineva va rog ?

Tot off topic scuze: Pai vroiam sa subliniez ca intr-adevar poti sa si astepti mult. Dar daca folosesti brute-force uneori nu ai de ales 

Facusem o greseala de incepator... nush ce ma apucase. Oricum am luat si eu 100p 

Se poate intampla si asta, dar de cele mai multe ori nu.

De exemplu un backtracking daca il stii bine il scrii in 10 minute maxim si dupa aia poti sta sa astepti 10-20 minute sa rezolve un test. (In acest timp poti lucra la altceva lasandu-l sa ruleze intr-o alta fereastra). Apoi te uiti ce rezultat a dat si vezi daca poti descoperi o formula sau o dinamica... ceva cu complexitate mai mica.

La fel si la grafuri... daca ti se cere un anumit drum pe 100000 de noduri stii ca trebuie sa gasesti un algoritm foarte rapid, dar pana una alta bagi un Roy-Floyd ca poate apare o relatie 

Dap! 

Programele brut force sunt rezolvarile "mai clare" ale problemelor. Acele rezolvari mai usor de descoperit dar cu complexitati mult mai mari O(N^3) sau un BackTracking. Bineinteles ca exista si probleme unde aceste rezolvari se incadreaza in timp, dar acolo unde nu se incadreaza, le folosesti doar ca sa-ti faci teste.

Dai un fisier de intrare ( cu random sau cum vrei, in functie de problema ) si apoi lasi programul "brute-force" (rezolvarea cu complexitate mare) sa ruleze pe testul respectiv, chiar daca dureaza foarte mult. Dupa aceea in fisierul de iesire ai o solutie corecta. (Presupunand ca ai implementat si programul brute-force corect)

Astfel poti incerca alte rezolvari cu complexitate mai mica sa vezi cam cum trebuie sa faci sa iti dea aceeasi solutie ca si programul brute-force.

Functia o folosesc ca sa aflu numarul de zerouri de la sfarsitul lui n!. Ti-am trimis mesaj privat "florian". Multumesc mult pt ajutor!

Nu verificam acest lucru intr-adevar, dar si dupa ce l-am verificat iau tot 65p 
Imi puteti spune totusi daca functia pe care o folosesc eu e corecta ?

Am intrat de tot in ceata. Pai algoritmul meu, in momentul in care primul element nu e cel mai mic (adica si in exemplu) deja coada devine vida. Deci pana la urma nu am priceput eu cum se face...  am studiat degeaba o sapt... ufff

[LE]
Am implementat stiva "deque" complexitate liniara. M-am prins cum functioneaza numai ca imi iese din timp pe ultimul test. De fapt cateodata imi iese pe ultimele doua teste, alteori doar pe ultimul (daca trimit aceeasi sursa de mai multe ori)... nu este totusi prea stransa limita de timp ?

Este intr-adevar o impartire in triunghiuri, luata de pe TopCoder. Sunt mai multe post-uri cu ea si la toata lumea pare sa functioneze (pana am dat io de ea  ) . Formula cu determinanti nu sare din timp ? O sa o implementez si pe aceea dar as vrea sa stiu ce e in neregula cu calculul de mai sus ca sa stiu daca ma pot baza pe formula respectiva sau nu.

Multumesc mult pt sfat oricum. 

Imi spune si mie cineva va rog de ce urmatorul cod :

Cod:

    long long I, A, B;
    long x1, x2, y1, y2, c1, c2;
    A = 0;
    B = 0;
    for( i=2;i<n; i++ )    
         {
              x1 = p[i][0] - p[1][0];
              y1 = p[i][1] - p[1][1];
              x2 = p[i+1][0] - p[1][0];
              y2 = p[i+1][1] - p[1][1];
              A += x1*y2 - x2*y1;
         }
    if( A < 0 ) A = -A;
    A = A/2;

unde varfurile sunt memorate in p de la 1 la n, p[ i ][ 0 ] = x si p[ i ][ 1 ] = y nu da aria corecta  ?

Iau numai ultimele 6 teste...

Eu iau 65p cu raspuns gresit pe celelalte cazuri... nu imi pot da seama ce gresesc, poate formula de cautat numar de zerouri desi nu cred. Am lasat-o asa pana la urma, ca nu-mi dau seama.

Am folosit urmatoarea functie. Daca e interzis sa o postez va rog sa o stergeti:

Cod:

long nrz( long c )
{
     long p = 0;
     while( c )
     {
            p += c/5;
            c /= 5;
     }
     return p;
}

Nici o problema. Intre timp am descoperit unde am facut greseala. Scuze pentru ce am cerut. Am gresit eu intrebarea, ar fi trebuit doar sa cer cateva teste mari si atat  , in loc sa cer pe cele oficiale. Multumesc oricum!

Imi puteti divulga si mie unul dintre teste va rog ? Algoritmul meu merge pe exemplu si pe toate testele care i le-am dat eu. Totusi iau numai primul test  Inca un exemplu mi-ar fi de mare folos...

De pe pozitia 24 incolo e deja gresit. Nu-mi dau seama unde ai gresit in algoritm, poate ca intr-adevar calculez in asa fel incat iese din tipul de date pe care il folosesti ( int sau long ). Verifica cu un Brute-Force pentru 24 sa vezi ca nu mai coincide... pana nu vad algoritmul de generare nu pot sa zic mai mult, dar cred ca folosirea tipurilor e greseala.

Si daca ultimul caracter e spatiu ( ' ' ) sau tab ?

Anyway... daca nici asa nu merge creaza cu algoritmul tau un vector pentru numerele de la 1 la 100 si posteaza-l sa ne uitam de unde nu mai e bine. 

M-am inselat... chiar merge  Am facut eu o greseala la verificare  Cel mai probabil ai o greseala la implementare sau iti iese afara din tipul folosit. Daca folosest int (sau integer) incearca sa pui long (sau longint) si vezi daca tot 0 iei.

Pune un post cu citirea. Cum citesti char cu char ? Poate nu verifici ca ultimul sa fie '0'..'9' iar in fisierele lor de intrare ultimul e "ENTER". S-ar explica de ce iei numai 0 peste tot.

pe ca oricare 10 nr adunate asa(1^1+2^2...) dau suma 7

Am verificat asta pe cateva exemple si pe primele 10 numere da adevarata dar mai departe e falsa. Poti sa demonstrezi afirmatia asta ?

salut manu... si voua la fel... mda... deci eu am facut pb merge de minune pe nr mari super wow. am facut si un force brut sa vad daca e corect.. bun. dar p e evaluator iau 0. si acum metoda folosita. Citesc caracter cu carater. Iau ultimele ciprie s=7*nr[i-1] initial nr[0]=0; si apoi iau un for de la nr[i-1]*10 la nr[i-1]*10+nr si calculez ultima cifra al fiecaruia si adaug la suma. care e pb lui... pls help

Nu prea imi dau seama cum faci, fii mai explicit putin. Iar daca esti sigur ca e corect, sa te uiti la raportul evaluatorului, pare sa fie o solutie care iese din timp. Oricum, daca citesti posturile de mai sus pentru aceasta problema cu siguranta vei gasi informatii folositoare!