infoarena

Aici puteti discuta despre Runda 1 Algoritmiada 2014. Postati toate supararile si complimentele voastre.

Frumoasa runda, cu probleme interesante, inafara de un detaliu la problema Magicmatrix

Am trimis in timpul concursului o solutie gresita in N^2 care a luat 100 de puncte, apoi am trimis una buna in N^3 care a luat 90.
Contraexemplul gasit este:
0 2 3
-2 0 4
-3 -4 0
In alte cuvinte, testele nu au acoperit unele cazuri foarte importante.

Pai tie ce iti dadea pe exemplu ala?

N^2 da YES
N^3 da NO
Correct ii NO

Frumoasa runda la 9-10, problema de gandire a fost intr-adevar cea cu patratul magic, cu o solutie ingenioasa in 30 de linii (m-am prins de ea in ultima ora si am zis in acel moment "Genial!"). Interesant ca dupa ce te prindeai de solutie trebuia sa o si reduci de la O(n^4) la O(n^2) (printr-o observatie simpla). Problema mission mi s-a parut foarte simpla ca idee, dar greu de implementat de 100p (se pare ca treaba cu sortatul dupa crossed product merge numai cand unghiurile formate < 180 grade - din acest motiv am pierdut 20p (si locul 1 in clasament  :sad:). Problema kami (jos palaria eudanip :thumbup:) mi s-a parut cea mai dificila (dar e genul de problema la care iti face placere sa te gandesti cum sa o scoti) - am luat 30p pe ea cu un brut. Am incercat initial sa imi tin un AIB pe sumele alea si sa caut binar, dar mi-am dat seama ca nu merge cautat binar si am abandonat ideea. Sunt curios cum se facea (poate ceva amortizat?). Oricum, runda mi-a placut si as vrea sa stiu si parerile celorlalti.

Frumoasa runda :) Sunt curios la Kami care era ideea de rezolvare a celor care au scos-o in sub 1.00kb (eu cu arbori de intervale si aib am scris destul de mult)  :D
As preciza doar ca la problema Kami testele sunt cam slabe. Prima mea sursa de 100pct pica pe exemplul asta : http://pastebin.com/tEUbK5Er (http://pastebin.com/tEUbK5Er) (sursa aia gresea cand intalneam operatia "0 n val", iar sursa mea finala de 100pct are corectata chestia asta).

Off-topic : fanul meu care imi da minus la karma de vreo luna in continuu este rugat sa iasa din anonimat :eyebrow:

Problemele au fost dragute, cu exceptia faptului ca la Kami se ia 100 cu o rezolvare de 2 lei, adica brut optimizat :)

Care era acea optimizare de 2 lei?

Daca la vreun pas, suma curenta > valmax, atunci sol = 0.

Ne-am dat seama si noi in timpul concursului. In arhiva nu o sa mai ia 100.

Care era solutia "adevarata" la kami?

Daca a luat 100 in concurs, degeaba nu mai ia in arhiva, cel putin din punctul meu de vedere :))

Au fost niste probleme foarte frumoase (cel putin cele de la Open, caci doar pe alea le-am citit). Abia astept sa le puneti in arhiva ca sa imi mai incerc solutia la Sistem3 (aveam cam multe bug-uri in sursa trimisa in timpul concursului pentru cazul cand ciclul contine mai mult de 1 element). Si mi se pare foarte bine faptul ca ati publicat rezultatele la foarte putin timp dupa terminarea concursului (alte dati stiu ca erau intarzieri destul de mari). Pe scurt, felicitari!

Singura observatie mai putin pozitiva este referitoare la faptul ca ati anuntat runda foarte tarziu (eu am primit email-ul cu anuntul joi seara - si ma mir ca nu mi-a intrat in Spam, caci altfel nu stiu daca mai participam azi :) )

Moral conteaza  :) . Sa stii ca ai facut problema pe bune.

Nu stiu, pe mine nu ma ajuta cu nimic sa stiu ca m-am chinuit jumate de concurs sa gasesc o idee buna (am gasit ceva ce parea ok, dar ori nu era ok, ori am gresit implementarea, habar n-am) si altii au luat 100 cu un brut optimizat, mai ales ca "optimizarea" aducea 70 de puncte in plus :) asta in conditiile in care, chiar si 10 puncte pot face diferenta la final

Oricum eu doar mi-am expus punctul de vedere. Exceptand bulaneala asta la kami, mie mi-a placut runda :)

Puteai sa iei 100 si cu N^3, daca optimizai citirea datelor (eu am trimis in total 3 surse in concurs - prima era N^3 si a luat 90, a doua era N^3 cu parsarea datelor de intrare si a luat 100, iar a 3-a a fost N^2 si, bineinteles, a luat tot 100).

Din limita de timp pentru problema Magicmatrix banuiesc ca solutia comisiei era mai proasta de N^2 ?

Mie cu n^2 imi mergea intr-o secunda

Buna ziua!

Solutia oficiala era O(N^2) (am postat in articolul cu solutii). Am lasat limita de timp mai larga pentru ca nu am vrut sa fie nevoie de parsare pentru 100 de puncte si am considerat ca, in cazul in care intr-adevar exista o solutie O(N^3) care sa ia 100 de puncte, e in regula (se bazeaza pe aceeasi idee esentiala a problemei).

De asemenea, ne cerem scuze pentru intarzierea cu care am anuntat concursul. Nu eram siguri daca o vom organiza in aceasta sambata sau ramanea pe alta data.

EDIT: a fost postat articolul cu solutii (http://www.infoarena.ro/algoritmiada-2014/runda-1/solutii). Vom adauga solutiile si la celelalte probleme in curand.

Eu am luat 70 la magicmatrix cu tle pe 3 teste incercand permutari permutari aleatorii si cred ca se poate si mai bine daca reduc numarul de incercari.

Frumoasa rezolvare la Magicmatrix! Eu m-am complicat cu cuplaj...  #-o

Dragute problemele :) Mi-e ciuda ca n-am fost atent la permut si am luat 260.  :fighting:  ](*,)  :aha:  :) se mai intampla :D

 Scuze ca postez de mai multe ori , dar nu a raspuns nimeni pana acum . Am trimis sursele la problema kimo la o sectiune gresita (open) in loc de 9-10 . Mentionez ca nu m-am inscris la sectiunea open , ci doar la 9-10 deci nici nu stiu cum a fost posibil sa trimit sursa acolo :( .Va rog mult , puteti sa adaugati punctajul la 9-10 ?

Organizarea tehnica a concursului a fost buna, insa testele au fost facute (foarte) prost. La Magicmatrix am trimis o sursa prima oara cu unsigned int si tot a luat 100 (?) si cineva mai sus a dat un exemplu in care la fel a luat 100 desi nu trebuia.

Cat despre Kami ar fi trebuit sa se modifice un test in timpul concursului ca sa pice bulaneala aia. Stiu ca o reevaluare a tuturor surselor e foarte costisitoare, dar nu e deloc corect sa ai o diferenta atat de mare de punctaj pe aceeasi solutie practic, mai ales la Algoritmiada.

O sa luam in cosiderare si o sa vorbim cu restu. Momentan nu putem face nimic.

Problemele de la 11-12 mi s-au parut faine(is tare curios cum se face Sistem3. Cand se va completa articolul cu solutii?).
Singura mea obiectie este legata de testele de la Kami. Eu am avut o rezolvare in O(sqrt(N)) pe query si update si am luat 90 cu TLE pe ultimul test, din cauza ca foloseam LL in prea multe locuri, banuiesc. Daca e sa judec dupa complexitate nu ar fi avut motive sa imi iasa din timp. Iar un brut optimizat sa ia 100 mi se pare putin exagerat.

Update la rating cand se da?
Multumesc anticipat.

Eu la mission am facut altfel, am sortat punctele in functie de unghiul pe care il fac cu puntul 0 raportat la axa ox, apoi le parcurgeam in sens trigonometric, daca existau 2 puncte consecutive cu unghi mai mare de 180 intre ele, trebuiau sa fie punctul de start si punctul de finish.

Incercati sa faceti voi teste. Si sa tratati toate cazurile. In timp ce mai pregatiti si alte probleme.
Cei carora nu v-a intrat solutia la Kami (fiindca nu ati bulanit-o) nu aveti niciun motiv sa va simtiti depunctati. Iar cei care ati bulanit-o va felicit, nu ati castigat nimic prin asta. Nu sunteti mai destepti in vreun fel ca ati reusit sa bulaniti o problema.

Dupa parearea mea a fost o runda bine organizata. Problemele mi-au placut , mai ales problema Kami. Per total , felicitari comisiei !  :ok:

Super runda !  =D&gt; (cel putin la 11-12) . Singurul inconvenient ar fi chestiunea cu bruturile optimizate la kami, dar in rest problemele au fost dragute.

Testele le-am generat cat de bine am putut (toti). La Magicmatrix, am generat matrici magice in care am "stricat" o singura valoare din ele. Nu puteam mai bine de atat. Oricum, nu ne pot trece prin cap toate bulanelile sau bug-urile pe care le pot avea 200 de participanti intr-un concurs.
Solutia ta a mers chiar daca ai folosit unsigned int in loc de int pentru ca atunci cand compari A + B cu C + D se compara reprezentarile binare ale lor. Daca A + B == C + D, atunci egalitatea va fi adevarata, indiferent daca sunt unsigned sau signed, pozitive sau negative. Prin urmare, nu poti genera un test pe care solutia ta sa pice.
Sincer, mie nu mi-a trecut prin cap sa vad ce se intampla daca folosesc unsigned.


Atunci cand s-au modificat teste in cadrul altor runde, toata lumea a fost suparata. Am decis sa nu modificam nimic, pentru a nu mai crea discutii. Se pare ca oricum am proceda, nemultumiti vor fi mereu.

Nu stiam ca asa se face compararea, greseala mea.

Oricum, nu am vrut in niciun caz sa minimalizez munca comisiei. Sunt constient ca e aproape imposibil sa scoti teste perfecte, era doar o parere despre ce s-ar putea eventual imbunatati pe viitor (de aia e si topic de feedback)

Referitor la problema Kami si la faptul ca unele "bulaneli" au reusit sa ia 100p, intr-adevar, este neplacut. Insa ideea de a adauga/modifica teste dupa ce comisia a vazut sursele concurentilor (cu intentia de a pica sursele respective) este una destul de discutabila. De exemplu, la ONI, asa ceva nu s-ar face (cel putin nu s-a facut niciodata in comisiile din care am facut eu parte si am vazut surse care au luat mai mult decat ne-am fi dorit sa ia din cauza ca testele nu au fost chiar atat de bune pe cat ne-am fi dorit). La alte concursuri aceasta practica este folosita. De exemplu, la concursurile lungi (de 10 zile) de pe Codechef se intampla frecvent asa ceva - mai ales in prima jumatate a concursului (daca cineva ia Accepted la o problema si sursa nu e OK, autorul mai incearca sa adauge teste ca sa pice solutia respectiva), dar mai putin spre final (cand ar fi foarte neplacut sa afli ca aveai o solutie Accepted care a devenit deodata TLE sau WA). Pe Codeforces s-a facut asa ceva o data si a generat o discutie foarte lunga (pentru cei interesati, aici e un post de-al lui Petr pe acest subiect: http://codeforces.com/blog/entry/6928 )

Am adaugat problemele in arhiva, mai putin Kami, unde va fi refacut un test, astfel incat bulanelile sa nu mai ia 100 de puncte in arhiva.

EDIT: De asemenea, ratingurile au fost actualizate.

Desi mult mai putin important (din cauza ca nu a luat nimeni mai mult de 50p in timpul concursului), poate ar trebui sa va ganditi sa mai adaugati/modificati un test la sistem3 ca sa contina si un ciclu cu fix 2 noduri (practic un caz in care ai 2 noduri diferite x si y, unite prin 2 muchii diferite, eventual de cost diferit - nu cred ca restrictiile problemei exclud un astfel de caz). Solutia cu care am luat initial 100p in arhiva nu trata cazul asta OK. De exemplu, mi-a luat un pic de timp pana mi-am facut solutia sa mearga si pe un test de genul:

Bineinteles, de ciclul cu 2 noduri mai pot fi "atarnate" oricate alte noduri pana la limitele datelor de intrare.

Daca nu tratai bine cazul cu cicluri de lungime 2 nu inseamna ca greseai cu ceva. Doar scapi un caz. Sa avem 11 teste ar fi un pic dubios. Solutia oficiala nu are caz particular pentru ciclu de lungime 2 asa ca nu m-am gandit sa adaug test si cu asta.

bagati cel putin 100 de teste pe problema. fiecare 10 teste grupate pentru 10 pct.

La o limita de timp de 0.5 secunde pe test, 100 de teste ar putea dura pana la 50 de secunde. Daca vrei sa nu mai primesti feedback, si evaluarea rundei sa dureze cateva ore dupa terminarea concursului, poti face asta.
Ca sa se poata baga atatea teste, sau ar trebui schimbat cum functioneaza evaluatorul, sau adaugate mai multe servere. (Codeforces si Topcoder pot sa aiba 100 de teste, sau mai multe, pentru ca au o groaza de servere, si cum pici un test evaluarea se opreste, deoarece nu conteaza punctajul final, conetaza Accepted or not)

In timpul unui concurs:
* arhiva ar trebuii sa fie blocata.
* Din alea 100 de teste, doar 2-4 sa fie rulate.
* Evaluare poate incepe dar cu rezultatele ascunse.
* Limitare la numarul de surse trimise pe problema/concurent (e.g. 10-20).


Da, Topcoder si Codeforces se opresc la primul test picat. Dar gandeste-te ca-s concursuri internationale si au multi mai multi participanti.
Si da, Topcoder si Codeforces e cu AC sau nu si e mult mai simplu sa generezi teste pentru ca nu trebuie sa te gandesti la distributia punctajelor. (E.x. un brut 10pct, un brut optimizat 20pct, n^5 30pct, n^3 50 .. etc).
Si un avantaj pentru comisie la topcoder si codeforces e ca testele din challenge sunt adaugate.

* Iar la kami trebuia sa se gandeasca comisia la faza ca suma creste repede pentru teste destul de random.

* La numarul de servere, sper ca a mai evoluat infoarena de acum 7 ani cand rula pe un laptop.
Oricum nu trebuie 100 de teste, ca daca nu-s generate calumea tot degeaba. dar 20-30 parca ar fii indeajuns pentru a acoperi destule cazuri.

Echipa infoarena cere feedback, asa ca luati feedback-ul fara sa aparati toate criticile :). Si daca din feedback se poate face infoarena mai bun.. atunci sa se faca.

Multumim echipei pentru runda&probleme :)