infoarena

Runda 1 a concurslui Algoritmiada 2015 s-a incheiat! Felicitari castigatorilor (http://www.infoarena.ro/algoritmiada-2015/runda-1/clasament/juniori)! Așteptăm feedback-ul vostru! :)

Înainte de toate, dorim să ne cerem scuze pentru lipsa de feedback din ultimele 10 minute. Pe viitor vom lua mai multe măsuri pentru ca evaluatorul să nu devină congestionat pe parcursul concursului.

De-asemenea, setul a fost poate nepotrivit pentru a departaja vârful clasamentului. Acest lucru s-a datorat în principal faptului că soluția noastră la Disconnect este complet lipsită de structuri de date, ceea ce aparent ne-a făcut să scăpăm complet din vedere soluțiile care liniarizau arborele. Ne cerem scuze, sperăm ca data viitoare să nu vă apucați de citit Miorița înainte să se termine concursul! :)

Super draguta runda!Felicitari organizatorilor si autorilor ! :)

Frumoasa problema fenrir! :)

La spectacole am luat 70 cu O(M * M) si 50 cu O(N * M * log M), cam aiurea :D
Se poate mai bine de O(P * nrdiv(N)) la perioada?

@Visan: Da. Se poate si O(suma de divizori de P) dar din pacate nu am putut diferentia fata de solutia O(nrdiv(p) * p).

LE: acum observ ca tu ai zis O(nrdiv(N) * p). Asta nu trebuie sa ia 100.

Sunt curios cum suna solutia oficiala la Disconnect, fara structuri de date :).

Eu am O(nrdiv(p) * p) si totusi mi-a picat ultimul test, deci cred ca ati reusit sa faceti diferentierea destul de bine.
Cred insa ca la problema Spectacole testele au fost generate slab. Cu un M^2 optimizat cred ca se poate lua 100.

Tinand cont ca operatiile sunt generate random (folosind xor), se pare ca bruturile au luat 100.

Primul pas e să observi că dacă reușești să faci fiecare tăiere în O(mărimea subarborelui mai mic), îți iese N log N complexitatea tăierilor + O(1) per query. Al doilea pas e să-ți dai seama cum să determini subarborele mai mic. Dacă alegi o cale elegantă să faci asta, ies 90 de linii  :)

La Perioada01 se poate si O(P). KMP cu ideea de la Perioada2.

Sunt într-adevăr niște surse care iau 100 deși nu au complexitate ok. Ne pare rău pentru asta. Dar în niciun caz testele nu sunt generate random și doar unele tipuri de bruturi au luat 100. Ne-am străduit să picăm anumite bruturi și am neglijat altele. Ne cerem scuze, vom completa testele in arhivă  :sad:

Foarte frumoase problemele! Felicitari organizatorilor si autorilor, a fost o runda reusita! Am si eu o curiozitate: cum arata graful de la Fenrir?

Runda de azi mi-a placut. Problema Fenrir a fost pe atat de diferita si pe atat de interesanta de rezolvat cum multe probleme din ziua de azi nu sunt (gg Mihai, in plus, enuntul e bazat). Problema  Perioada01 se putea face si cu un Z (asa am implementat eu) in O(p). Problema disconnect are un enunt foarte dragut si imi place cu atat mai mult cu cat am inteles acum rezolvarea fara liniarizare (in concurs am implementat LCA si liniarizare cu AIB). Am fost cu 1min in urma sa trimit un O(N*M) corect la spectacole, presupun ca pentru 100  aveti o dinamica cu AIB pentru maxim (sau cu o structura de date ceva) in complexitate O(MlogN). Per ansamblu, keep up the good work.  :thumbup:

P.S. Am si eu o curiozitate: voi cum verificati in evaluator la Fenrir ca graful nostru sa nu aiba lant hamilton fara sa bagati ceva foarte costisitor ca timp? :-?

Problemele mi s-au parut foarte tari. Neplacut e sa ajungi la sfarsitul concursului sa vezi ca puteai sa iei 100 la probleme mult mai simplu, cu algoritmi mai prosti. Dar nu ai ce face, unele probleme se preteaza la astfel de situatii si e imposibil sa le eviti. Plus ca nu e asta un motiv sa nu dai o problema frumoasa. Felicitari comisiei !

Nu inteleg de ce am primit masajul "Fisier de iesire corupt" la problema Fenrir, unica idee ar fi ca eu nici nu am deschis fisierul de intrare, am scris doar solutia in fisierul de iesire, am verificat numele fisierului este corect, cred ca ar trebui reevaluate sursele cu acest mesaj pentru ca in enunt nu se specifica ca trebuie numaidecit sa citim datele din fisierul de intrare.  Mad

Dinamica O(2^N * M).

Nu are legătură cu fișierul de intrare, din câte îmi dau seama la prima vedere afișezi anumite muchii de mai multe ori.

Mda, scuze, acum mi-am dat seama, am crezut ca muchiile sunt orientate si am afisat fiecare muchie de doua ori  :aha:

@Andrei: Pai tu de ce crezi ca la fenrir numarul de stane e 20? Pentru ca evaluatorul e in 2^20, nu putem mai bine.

@Nitu: Am vazut si eu solutia aia in timpul concursului, foarte amuzant ca nu am facut asemanarea cu propria problema putin modificata :))). Solutia mea este O(Suma divizorilor lui P) care este foarte aproape de O(P). Din pacate O(numar de divizori * P) mergea prea bine, chiar si pe numere cu multi divizori.

Problemele Perioada01 si Disconnect nu au iesit asa cum vroiam noi. Speram cu toate acestea ca v-a placut runda si o sa participati si la rundele viitoare. O sa incercam in seara asta sa scriem un articol cu solutii.

Legat de partea cu "Fisier de iesire corupt" pentru probleme care au numai un test, ar fi dragut sa se implementeze o functionalitate la borderoul de evaluare in care sa se afiseze mesajul pe test fara rezultatul aferent.

Este destul de neplacut sa gresesti din neatentie la o problema de totul sau nimic :) .

Si daca ai mesajul ok nu iti dai seama ca ai trecut testul :))?

El se referea la probleme precum prima de azi, unde nu stiai nici macar daca ti-a compilat.

@Dani si @George: Nu facusem pe foaie, mi se parea ca dinamica aia ia destul de mult, dar, pana si matematic, mai mult de 4 secunde nu ia, ceea ce e ok.

@Cosmin Rusu

Ba da, dar poate nu ai primit tot punctajul pe test. Functionalitatea aceasta te-ar scapa la urmatoarea problema de tip Output Only de probleme cu memoria/timpul/depasiri de stiva sau erori de afisare...

@AlexValeanu: Graful la Fenrir era  un graf bipartit complet, cu 11 noduri in stanga si 9 noduri in dreapta.





(am albit textul ca sa nu fie spoiler pentru cei care vor sa se prinda singuri) :)

când vor fi adăugate problemele în arhivă?

@Andrei1998 Mersi!

Felicitari pentru runda!  =D> Desi, sincer, vad ca a scazut putin dificultatea maxima la probleme...

La problema Disconnect mergea o idee mult mai draguta cu liniarizare dfs si smenul lui mars pe aib. Am bagat asta in concurs si am luat doar 80. era mult mai tare daca intra si solutia pentru a incuraja solutii originale, nu implementare de heavy Path :p

@chiriacandrei25 daca ai TLE inseamna ca nu trebuia sa intre  :-'

Am aflat acum ca le-a intrat unora ci solutia asta, deci cred ca am gresit eu ceva. Oricum e o solutie cu 0 structuri de date, care cica e smen.

Nu cred ca se poate face legit fara structuri de date.

Interesante problemele si BIG LIKE pentru Fenrir!!  =D>

@Denis Mita

Într-adevăr a fost mai scăzută dificultatea maximă, dar nu intenționat. Reparăm asta la Runda 2, stai liniștit  :roll:.

Poți să citești un spoiler pentru soluția noastră la disconnect pe prima pagină a topicului. O vom publica și în articolul de soluții în curând.

Mda, sa nu va revansati prea mult totusi  :)

Cand va fi postat articolul cu solutiile:)?

Am publicat articolul (http://www.infoarena.ro/algoritmiada-2015/runda-1/solutii). Lipsesc 2 probleme, le vom completa cat de curand  :)

LE: Este gata si articolul cu solutii. :)

Salut,

Imi poate explica cineva in ce consta reetichetarea din solutia oficiala la disconnect ?

Merci anticipat ;)

Nimic complicat, eticheta unui nod e numarul componentei din care face parte nodul respectiv. La inceput toate nodurile au eticheta 1. La prima taiere, nodurile dintr-o parte vor fi reetichetate cu 2, etc  :)