Feedback Runda 7

[•dushmi]

Runda 7 a concursului Monthly 2012 s-a încheiat. Felicitări primilor clasați!

Premiul special oferit de catre firma IXIA va merge la Spatarel Dan Constantin, deoarece a rezolvat problema Siret avand penalizarea (26 de puncte) cea mai mica dintre cei inscrisi in concurs! Felicitari!

Felicitari si lui Perticas Catalin care a reusit sa obtina cel mai mare punctaj pe problema Siret (75 de puncte) insa, din pacate, nu a fost inscris la aceasta runda!

Asteptam opiniile si eventualele sugestii ale voastre în legatura cu organizarea, subiectele propuse și orice probleme intampinate.

Mult succes în continuare!

[•PlayLikeNeverB4]

Felicitari pentru aceasta runda! Probleme interesante.

[•S7012MY]

Felicitari celor ce au facut problema. Nu prea mi-a placut runda asta, din cauza limitei la shuffle(imi intra in 0.8 pe testul maxim si nu prea mai aveam ce optimiza). Se observa si din clasament ca marea majoritate a facut doar o problema. Nici pitagora nu mi-a placut. La cpal trebuia sa se precizeze ca 0 nu este numar natural (cand am deschis eu problema nu era precizat)
Oricum felicitari comisiei pentru problema shuffle si pentru siret care au fost ft misto

[•danalex97]

Felicitari ! Super tari problemele.  Cum ati facut siret ?

[•klamathix]

Imi pare rau ca ai patit asta la Shuffle, nu-mi dau seama de ce. Restul lumii care a facut solutia buna are 500 de ms pe ultimul test. In 0.9 imi intra mie O(N log K)-ul deci nu prea puteam s-o ducem pana acolo . La cpal nu e vorba de 0, 0 e numar natural. Dar numar fara nicio cifra in schimb nu exista ). Nici eu nu ma omor dupa Pitagora, dar diversifica setul foarte bine si se vede ca n-a fost banala .

[•PlayLikeNeverB4]

In 0.9 imi intra mie O(N log K)-ul deci nu prea puteam s-o ducem pana acolo .

Nu inteleg. Si eu am O(N log K) si a trecut.

[•dushmi]

Cu Pitagora mai este si o alta problema. Majoritatea lumii nu stie solutia oficiala, care eu zic ca era "ceva" mai interesanta decat brute-ul pe care l-au incercat multi dintre cei din concurs. O sa va schitez eu mai jos, in mare

Cod:

a * a + n * n = b * b
n * n = b * b - a * a
n * n = (b + a) * (b - a)

De aici rezulta ca atat b - a cat si b + a trebuie sa fie divizori ai lui n * n. Facem divizori lui n si ii luam fiecare cu fiecare, obtinand astfel toti divizorii lui n * n pe care, mai apoi, ii luam pe rand .

Cu aceasta solutie sigur nu aveati probleme legate de intrarea in timp.

[•a_h1926]

Am patit si eu acelasi lucru la Shuffle am o solutie O ( N ) cu constanta 5 si iau 90 de puncte. Are idee cineva ce optimizari ar trebui sa mai fac pentru a obtine 100 de puncte?

[•visanr]

La pitagora am facut un for ca sa aflu lungimea ipotenuzei, plecand de la N + 1, iar pt fiecare lungime a ipotenuzei verificam daca a 2-a cateta are ca lungime un nr natural. Dupa ce gaseam prima lungime care verifica acea relatie opream cautarea si afisam a 2-a cateta. Cu aceasta rezolvare am trecut doar 5 teste cu incorect pe celelalte, timp maxim 4 ms. Ce a fost gresit in rezolvarea mea?

[•klamathix]

Verifici gresit daca un numar e patrat perfect. Tu verifici ca sqrt(x) - (int) sqrt(x) < eps, eps e 10 ^ -4. Ori radical din 10 ^ 10 + 1 de exemplu are prima zecimala nenula pe pozitia a 6-a.
Solutia asta nu ar fi intrat in timp, in orice caz .
Ca sa faci verificarea corect poti lua partea intreaga din radical si sa o ridici la patrat ca sa vezi daca obtii acelasi rezultat.

[•visanr]

Multumesc mult pentru raspuns si felicitari pentru aceasta runda!

[•lucian666]

La problema pitagora2.Am parcurs numerele de la n+1 si verificam daca numarul  (i * i - n * n  ) este natural si patrat perfect ,atunci sqrt din acel numar este cateta cautata .Totusi  iau doar 70 pct cu 2 WA si 1 TLE.
Aveti o alta idee de rezolvare?
Multumesc Anticipat!!!



[editat de admin] Solutia oficiala la pitagora2 o poti vedea putin mai sus in acest topic.

[•tzipleatud]

Am creat pagina de solutii si am pus solutiile pentru Cpal si Pitagora2. Daca ar putea cineva sa completeze solutiile pentru celelalte 2 probleme as fi recunoscator.

[•klamathix]

Am creat pagina de solutii si am pus solutiile pentru Cpal si Pitagora2. Daca ar putea cineva sa completeze solutiile pentru celelalte 2 probleme as fi recunoscator.

Done.

[•harababurel]

cand se va modifica ratingul? au trecut cateva zile si inca nu s-a schimbat la nimeni.

[•Schumi]

Cand va avea unul din admini timp de asta