Feedback Runda 2

[•eudanip]

Hai cu feedback la Runda 2. http://infoarena.ro/jc2012/clasament

[•gramatovici_paul]

Ce repede au aparut rezultatele!!

[•scipianus]

Felicitari echipei pentru efortul depus la organizarea celor doua runde Felicitari Dani pentru subiectele interesante de azi Doar ca pot spune ca ai fost cam zgarcit cu memoria la primele doua si prea generos la a treia

[•Schumi]

Problemele au fost interesante si au fost formulate clar(gj Dani ). Totusi la problema hacker3 ar mai fi mers 200k de memorie ). Asteptam sa publicati articolul cu solutii si sa se modifice ratingurile  

[•S7012MY]

Felicitari pentru organizare. Problemele chiar au fost foarte clar formulate si destul de interesante. Totusi au fost prea multe teste partiale, iar mie nu mi-a placut asta. Daca nu erau ele probabil n-as fi rezolvat nici o problema corect deoarece se putea gresi foarte usor din neatentie.

Problema sqrt nu mi-a prea placut deoarece (zic eu) problemele cu numere mari nu prea sunt potrivite pentru concursurile online.

Cum se facea hacker3 fara sa deschizi de 10 ori fisierul ?

[•eudanip]

Stiu ca am fost putin zgarcit cu memoria dar am facut asta ca sa departajez solutiile oficiale de alte solutii (care mergeau mai bine dar erau mai plictisitoare dupa parerea mea  ). O sa public si solutiile.

@Petru Trambitas: Nu toti cei care au lucrat la problema sqrt au copiat numerele mari din sursa lui Simoiu. Plus ca era putin mai smen sa faci radical pe numere mari in O(n^2)

[•deneo]

Felicitari pentru runda. Ai cam nimerit nivelul de dificultate pentru junior challenge. GJ Dani 

[•soriyn]

La hacker e nevoie de numere mari ?

[•klamathix]

Nu.

[•elfus]

Tot timpul o sa ai la dispozitie, in cel mai rau caz, o solutie formata din Bi. In cazul cel mai rau, Bi sunt toti 2.000.000.000 si sunt 100.000, care ar face 2 * 10^14, care intra lejer in long long. Deci nu-ti trebuie numere mari. Frumoasa runda Dani

[•VisuianMihai]

Nu mi se pare normal ca la Hacker3, un simplu LONG LONG sa faca diferenta intre 15 puncte si 70, adica e mai importanta ideea de rezolvare decat niste limite amarate, parerea mea.

[•klamathix]

Asa sunt concursurile de informatica, te vei obisnui cu ideea. Aici era destul de evident ca e nevoie de long long. Probabil iti va prinde bine in viitor si vei evita sa faci greseli de genul asta in competitii mai importante, cum au facut-o multi de-a lungul vremii. Te invit sa participi si pe TopCoder sau Codeforces  .

[•soriyn]

Apropo se putea face fara sa deschizi de 2 ori fisierul ?

[•klamathix]

Da. Ideea era sa faci o dinamica dp[ i ][ j ] costul minim sa rezolvi primele i task-uri si sa fi avut loc j dublari pana acum. Iti dai tu seama cum sa o reduci de la n ^ 2

[•VisuianMihai]

Ratingul se va modifica dupa clasamentul rundei a 2-a sau dupa clasamentul final sau dupa ambele?
Si inca ceva... Imi puteti da va rog o idee de rezolvare la bleach?

[•darren]

La Bleach eu am facut asa:
Daca ai sirul sortat, problema se poate rezolva foarte usor cu un greedy. Ca sa iti obtii sirul sortat, si sa iti incapa in memorie, iti tii un heap cu K+1 elemente. La inceput heap-ul contine elementele [1, K+1]. Daca iti iei minimul, sigur acela va fi minimul din tot sirul. La fiecare pas i, elementul actual minim din heap va fi elementul al i-lea in sirul sortat (si il scoti afara din heap), si daca mai sunt elemente care nu au fost bagate, il bagi pe urmatorul.

Apropo, mi-a placut runda.  
Hacker3 mi s-a parut cea mai frumoasa (rezolvarea cu dinamica), iar Sqrt cea mai urata.

[•Schumi]

La bleach ti se da sirul aproape sortat(asta inseamna ca fiecare element e decalat cu maxim k pozitii). Stiind asta, observi ca poti sorta vectorul folosindu-te de un heap de minim in care sa tii doar k + 1 elemente. Este evident ca cel mai mic element se va afla pe una din primele k + 1 pozitii din sirul dat, al doilea va fi in intervalul [2, k + 2] etc. Ca heapul sa iti ramana suficient de mic ca sa intre in memorie, de fiecare data cand adaugi ceva nou, scoti varful(elementul minim).

[•S7012MY]

Apropo, mi-a placut runda.  
Hacker3 mi s-a parut cea mai frumoasa (rezolvarea cu dinamica)

Poti detalia putin te rog ?
Multumesc

[•VisuianMihai]

Mersi Rares si Schumi, acum am inteles.

[•danalex97]

Frumoasa runda.   Totusi inca nu stiu cum se face sqrt de 100p. Eu am reusit doar de 60p.

[•darren]

Poti detalia putin te rog ?
Multumesc

Observi ca, daca folosesti doar b-uri, rezultatul maxim e 2000000000 * 1000000 < 2^30 * 2^17 (care este egal cu 2^47). Deci rezultatul nu poate depasi niciodata valoarea, sa zicem, 2^50 (sa fie mai rotund, in loc de 47). Asa ca, vom folosi tot timpul mai putin de 50 de a-uri. Acum iti tii o dinamica D[ i ][ j ] = timpul minim pentru primele i hack-uri, daca folosim j a-uri. De recurenta probabil iti dai seama (la pasul actual poti sa alegi a sau b: daca alegi a, j-ul creste; daca alegi b, j-ul ramane acelasi).

[•lucian666]

au fost publicate solutiile oficiale la runda a 2-a?

[•SpiderMan]

Frumoasa runda.   Totusi inca nu stiu cum se face sqrt de 100p. Eu am reusit doar de 60p.

Ai folosit cumva impartirea pe numere mari (dintre 2 numere mari, nu dintre un nr. mare si unul mic) ?

[•PlayLikeNeverB4]

Observi ca, daca folosesti doar b-uri, rezultatul maxim e 2000000000 * 1000000 < 2^30 * 2^17 (care este egal cu 2^47). Deci rezultatul nu poate depasi niciodata valoarea, sa zicem, 2^50 (sa fie mai rotund, in loc de 47). Asa ca, vom folosi tot timpul mai putin de 50 de a-uri. Acum iti tii o dinamica D[ i ][ j ] = timpul minim pentru primele i hack-uri, daca folosim j a-uri. De recurenta probabil iti dai seama (la pasul actual poti sa alegi a sau b: daca alegi a, j-ul creste; daca alegi b, j-ul ramane acelasi).

Si cu observatia ca numarul maxim de a-uri pe care s-ar putea sa le folosim e 31 scapam si de overflow.

[•danalex97]

Ai folosit cumva impartirea pe numere mari (dintre 2 numere mari, nu dintre un nr. mare si unul mic) ?

Da , de fapt inmultirea pe rand la fiecare cifra , insa mi se parea ca intra ( am lucrat in baza 10^6 ) Oricum o sa incerc si asa. 10x