Daca ma poate ajuta si pe mine cineva cu http://infoarena.ro/job_detail/530087 unde primesc Killed by signal 11(SIGSEGV) pentru toate testele. Ce e ciudat e ca daca comentez linia 71, primesc WA la toate, iar daca comentez doar a 2-a conditie din if-ul de pe linia aia, iar primesc killed. Diferenta e comparatia mDist[j] == mDist[k], care eu o vad corecta pentru ca toti indicii au conditia <n in for-ul lor. Ce e gresit?

S-a mai discutat, timpii afisati in monitor nu sunt exacti. Poti sa ai incredere in evaluator, iti calculeaza bine timpul de executie. Incearca sa mai optimizezi. Altora le-a intrat fara probleme.

Pai nu e facut cu timer de mare acuratete (Performance Counter)?

cand ai nevoie de mai multe numere, ciurul isi face foarte bine treaba... doar ca aici nu ai nevoie doar de ciur...trebuie sa-ti mai dai seama de ceva... dar numerele prime tot cu ciurul le calculezi... daca nu te descurci poti sa te uiti in articolul cu solutii

Da, adica faci preprocesare si trimiti sursa cu un vector v[500000], unde v[i ] = nr de nr prime pana la i. Cu asta ai rezolvat problema in O(n). Bad point: sursa cam mare (multi KB), s-ar putea sa n-o primeasca.

[Daca fiecare nod are 2 arce de iesire si 2 de intrare, un ciclu eulerian ar trece prin fiecare nod de 2 ori, adica am avea o secventa 010100101xxxxx...xxx de 2 ori in solutia finala, ceea ce ar duce la lungirea solutiei, si deci nu la cea mai scurta solutie.]

Ok, poate nu m-am exprimat suficient de bine. Vroiam sa exprim faptul ca am gasit o rezolvare mai simpla (dupa parerea mea). De ce trebuie sa gasesti graful? De ce trebuie sa gasesti ciclu eulerian? Cand graful il stii deja in O(1), adica stii orice "parte" din el printr-o singura formula, deci nu mai trebuie retinut, nu mai trebuie alocata matrice de 2^n * 2^n (sau liste liniare simplu inlantuite, cum facusem eu pana sa-mi dau seama ca nu trebuie). De ce trebuie ciclu eulerian cand un backtracking simplu (dar mai optimizat) rezolva totul? Este o regula ca trebuie gasit graful si apoi ciclul eulerian? Nu. Problema o poti rezolva in orice fel, atat timp cat raspunsul este corect. Eu am gasit o solutie ce scoate 0.5 s pentru ultimul test. Si am plecat de la un singur post de mai sus, care este defapt exemplul n=3 al lui Voicu Octavian. Nu consideri ca probleme astea le rezolvi si ca sa-ti largesti orizontul gandirii, originalitatea? Daca tot ce faci este sa citesti posturile si sa te iei dupa ele, practic tu nu ai "evoluat" decat pe plan teoretic, pentru ca acum stii de deBruijn, de graful lui si eventual de ciclu eulerian, daca nu stiai deja. Si da, initial am citit ca e ceva cu ciclu eulerian, dar inainte de a asterne pe ecran algoritmul pentru gasirea lui, am stat si m-am gandit, am scris pe foaie solutia si am vazut ca nu e ciclu eulerian pentru ca nu trece prin toate arcele. Daca fiecare nod are 2 arce de iesire si 2 de intrare, un ciclu eulerian ar trece prin fiecare nod de 2 ori, adica am avea o secventa 010100101xxxxx...xxx de 2 ori in solutia finala, ceea ce ar duce la lungirea solutiei, si deci nu la cea mai scurta solutie.

Cu alte cuvinte, te complici cu graful si ciclul eulerian, consumi memorie si timp de computatie.

[eulerian]

Cred ca e o diferenta enorma intre compilatorul de aici si al meu de acasa. Aici iau 100% punctaj, cu 0.5 sec pentrul ultimul test, iar pe calcu meu scot vreo ~2 sec la el, si e core2duo la 3ghz cu 4gb ram . In fine, problema am rezolvat-o cu un backtracking iterativ optimizat la greu, nu e nevoie sa retii niciunde un graf, deoarece fiecare nod are 2 arce care ies din el si 2 care intra in el (unele noduri au chiar un arc catre ele insele). Este un graf orientat si fiecare arc poate fi gasit printr-o formula in O(1), cu alte cuvinte stim daca intre nodurile N si M exista arc in O(1), de aceea stim care este graful fara sa il retinem. Trebuie gasit un ciclu care trece prin toate nodurile o singura data, si incepe cu cel mai mic nod. Primul ciclu gasit este cel cerut. Astfel, programul se termina dupa ce s-a gasit primul ciclu. Numarul de cifre ale solutiei se calculeaza printr-o formula, deci tot in O(1). Bafta si celor care nu au rezolvat problema asta!

Apropos,

NU este ciclu eulerian!!!! Este un simplu drum care contine toate nodurile grafului si incepe cu cel mai mic posibil. Nu conteaza unde se termina si NU trebuie sa contina toate arcele.

Editat de moderator: Nu posta consecutiv pe aceeasi tema! Modifica mesajele anterioare!

shi eu tot numai 60 de pct iau dar imi da incorect sau fisier de iesire lipsa la testele 3 si 4 shi vreau sa spun ca am incercat o multime de metode si variante sa vad unde am greshit shi tot nu inteleg, numere mari nu am probleme, i-am dat teste cu 128 de linii a cate 32 de biti fiecare, si vreau sa spun ca am urmarit cu watch tot testu shi merge perfect, ce cazuri ciudate ati gasit de nu imi merge mie?

Eu citesc numaru il transform in baza 10 shi apoi verific dak e par shi e mai mare decat cel mai mare nr par gasit anterior. Ce e greshit in acest rationament?

La ce trebuie sa-l transformi in baza 10? Un numar par are intotdeauna ultima cifra 0 in baza 2. Citesti cu fgets si parcurgi invers pana gasesti o cifra, daca e 0 numarul de pe linia aia e par, daca nu, treci la urmatoarea linie.

Am luat 100/100 cu timpi <= 0.04s.
Am declarat un vector de 30000 elemente. Daca elementul i are valoarea 1, atunci el face parte din reuniune, altfel nu. Citesc fisierul si pentru fiecare numar n din fiecare multime marchez cu 1 in vector pe pozitia n. Daca nu era deja marcat, incrementez c (cardinalul reuniunii). In fisierul de iesire scriu c, apoi parcurg vectorul si daca gasesc 1 pe pozitia p, scriu numarul p.
Bafta!

Am obtinut 100/100 cu timp <= 0.01s.
Am gasit toate numerele prime de la 2 la 2^10 si le-am hard-codat direct in sursa intr-un vector const int[]. Vectorul trebuie parcurs cu indicele de la 1 la (1 << n) - 1 (fiindca doar numerele intre 1 si 2^n - 1 au n cifre in baza 2). Citesc numarul prim direct din vectorul declarat (deci nu mai verific daca e prim sau nu, ca e sigur prim ) si tot ce mai trebuie sa fac e sa vad cate cifre de 1 are in baza 2. Fac asta tot impartind numarul la 2 si vazand de cate ori da restul 1. La scriere in fisier folosesc o functie recursiva pentru a-mi scrie cele n cifre in baza 2.
Bafta!

Hai sa facem putine clarificari: eu am luat 100/100

[Sters de admin: Hinturile sunt OK, solutiile intregi NU!]

Bafta si voua!