•klamathix
|
|
« : Decembrie 07, 2014, 14:11:16 » |
|
Runda 1 a concurslui Algoritmiada 2015 s-a incheiat! Felicitari castigatorilor! 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!
|
|
|
Memorat
|
|
|
|
•xtreme77
Client obisnuit
Karma: 7
Deconectat
Mesaje: 69
|
|
« Răspunde #1 : Decembrie 07, 2014, 14:17:54 » |
|
Super draguta runda!Felicitari organizatorilor si autorilor !
|
|
|
Memorat
|
|
|
|
•andrei.arnautu
Client obisnuit
Karma: 9
Deconectat
Mesaje: 58
|
|
« Răspunde #2 : Decembrie 07, 2014, 14:26:06 » |
|
Frumoasa problema fenrir!
|
|
|
Memorat
|
|
|
|
•visanr
|
|
« Răspunde #3 : Decembrie 07, 2014, 14:27:39 » |
|
La spectacole am luat 70 cu O(M * M) si 50 cu O(N * M * log M), cam aiurea Se poate mai bine de O(P * nrdiv(N)) la perioada?
|
|
|
Memorat
|
|
|
|
•eudanip
|
|
« Răspunde #4 : Decembrie 07, 2014, 14:30:56 » |
|
@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.
|
|
|
Memorat
|
|
|
|
•CosminRusu
|
|
« Răspunde #5 : Decembrie 07, 2014, 14:33:19 » |
|
Sunt curios cum suna solutia oficiala la Disconnect, fara structuri de date .
|
|
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit
Karma: 20
Deconectat
Mesaje: 74
|
|
« Răspunde #6 : Decembrie 07, 2014, 14:37:25 » |
|
@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.
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.
|
|
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit
Karma: 20
Deconectat
Mesaje: 74
|
|
« Răspunde #7 : Decembrie 07, 2014, 14:38:18 » |
|
Sunt curios cum suna solutia oficiala la Disconnect, fara structuri de date . Tinand cont ca operatiile sunt generate random (folosind xor), se pare ca bruturile au luat 100.
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #8 : Decembrie 07, 2014, 14:38:53 » |
|
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
|
|
|
Memorat
|
|
|
|
•Impaler_009
Client obisnuit
Karma: 23
Deconectat
Mesaje: 59
|
|
« Răspunde #9 : Decembrie 07, 2014, 14:41:35 » |
|
La Perioada01 se poate si O(P). KMP cu ideea de la Perioada2.
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #10 : Decembrie 07, 2014, 14:45:06 » |
|
Sunt curios cum suna solutia oficiala la Disconnect, fara structuri de date . Tinand cont ca operatiile sunt generate random (folosind xor), se pare ca bruturile au luat 100. 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ă
|
|
|
Memorat
|
|
|
|
•AlexandruValeanu
|
|
« Răspunde #11 : Decembrie 07, 2014, 14:47:40 » |
|
Foarte frumoase problemele! Felicitari organizatorilor si autorilor, a fost o runda reusita! Am si eu o curiozitate: cum arata graful de la Fenrir?
|
|
|
Memorat
|
|
|
|
•Andrei1998
|
|
« Răspunde #12 : Decembrie 07, 2014, 14:48:46 » |
|
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. 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?
|
|
|
Memorat
|
|
|
|
•Impaler_009
Client obisnuit
Karma: 23
Deconectat
Mesaje: 59
|
|
« Răspunde #13 : Decembrie 07, 2014, 14:54:22 » |
|
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 !
|
|
|
Memorat
|
|
|
|
•ctlin04
|
|
« Răspunde #14 : Decembrie 07, 2014, 14:56:55 » |
|
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
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #15 : Decembrie 07, 2014, 14:58:09 » |
|
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? Dinamica O(2^N * M).
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #16 : Decembrie 07, 2014, 14:59:30 » |
|
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
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.
|
|
|
Memorat
|
|
|
|
•ctlin04
|
|
« Răspunde #17 : Decembrie 07, 2014, 15:02:40 » |
|
Mda, scuze, acum mi-am dat seama, am crezut ca muchiile sunt orientate si am afisat fiecare muchie de doua ori
|
|
|
Memorat
|
|
|
|
•eudanip
|
|
« Răspunde #18 : Decembrie 07, 2014, 15:03:30 » |
|
@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.
|
|
« Ultima modificare: Decembrie 07, 2014, 15:05:44 de către Mihai Calancea »
|
Memorat
|
|
|
|
•maritim
|
|
« Răspunde #19 : Decembrie 07, 2014, 15:07:47 » |
|
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 .
|
|
|
Memorat
|
|
|
|
•CosminRusu
|
|
« Răspunde #20 : Decembrie 07, 2014, 15:11:54 » |
|
Si daca ai mesajul ok nu iti dai seama ca ai trecut testul )?
|
|
|
Memorat
|
|
|
|
•Andrei1998
|
|
« Răspunde #21 : Decembrie 07, 2014, 15:17:34 » |
|
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.
|
|
« Ultima modificare: Decembrie 07, 2014, 15:24:13 de către Constantinescu Andrei Costin »
|
Memorat
|
|
|
|
•maritim
|
|
« Răspunde #22 : Decembrie 07, 2014, 15:20:46 » |
|
@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...
|
|
|
Memorat
|
|
|
|
•Andrei1998
|
|
« Răspunde #23 : Decembrie 07, 2014, 15:25:43 » |
|
@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)
|
|
« Ultima modificare: Decembrie 07, 2014, 15:32:34 de către Constantinescu Andrei Costin »
|
Memorat
|
|
|
|
•Djok
Client obisnuit
Karma: 10
Deconectat
Mesaje: 71
|
|
« Răspunde #24 : Decembrie 07, 2014, 15:27:59 » |
|
când vor fi adăugate problemele în arhivă?
|
|
|
Memorat
|
|
|
|
|