infoarena

Runda 4 (http://infoarena.ro/algoritmiada-2012/runda-4) a concursului Algoritmiada 2012 (http://infoarena.ro/algoritmiada-2012) s-a încheiat. Felicitări primilor clasați (http://infoarena.ro/algoritmiada-2012/runda-4/clasament/5-9)!

Așteptăm opiniile și eventualele sugestii ale concurenților în legătură cu oraganizarea, subiectele propuse și orice probleme întâmpinate.

Mult succes în continuare!

Daca sunt solutiile, ma ofer eu sa le pun inneseara pe site.

Nu stiu cum au fost problemele, deoarece nu stiu cum se fac pana la urma, dar la prima vedere par grele. Nu e asa ca la Runda finala la clasele 5-9 se califica primii 14-15?  :-'

Intr-adevar au fost mai grele problemele (desi la clasa a 10-a au fost destul de grele si la Runda 1  :-' ),dar foarte interesante  :ok:  M-ar interesa cum se face problema Spirala3 (din ce am vazut parca nu s-a scos mai mult de 50pct pe ea :-k )

Felicitari pentru organizare,subiecte si pentru tot efortul depus in aceasta editie a Algoritmiadei :D

Super runda, mie unul mi-a facut aceasta dupa-amiaza mai frumoasa!

Go2 -> nu am inteles enuntul, nu m-am gandit, nu am bagat nicio sursa :))
Muncitori -> draguta problema
Puteri3 -> frumoasa, destul de grea, insa nu destul de originala :)
Spirala3 -> desi am complexitate de O(N^4) pe problema aceasta, nu am scos mai mult de 50 de puncte (se pare ca nimeni nu a scos). Cred ca limita de timp ar fi trebuit sa nu fie atit de strinsa, tinand cont ca a fost o problema grea (si o sursa mai dezordonata ca a mea ar fi trebuit sa intre in timp ^_^).

Felicitari organizatorilor!  =D>

La open mi s-a parut ca a cam lipsit lumea  :-'

Problemele au fost ok, desi muncitori se rezolva cam ca si Order, iar pentru puteri3 trebuia sa scoti doar recurenta din cartea lui Tomescu (intr-adevar nu era destul de originala ...) ...

Spirala3 si Go2 m-au naucit ... N-am avut nicio idee de unde sa le apuc.

Totusi felicitari tuturor!

@Andrici Cezar: Acum sunt 4 grupe, nu 3 ca anul trecut. S-ar putea sa fie la 5-9 mai putini ca anu' trecut :'(
@Ionescu Vlad: Are faptul ca te-ai clasat al doilea vreo legatura cu infrumusetarea dupa-amiezii?  :evil:


L.E.: Sa nu uitati de rating-uri.

Made my day  :winner1:

Au fost minunate problemele... Spirala3 inca ma tine foarte interesat, vad ca nimeni nu a reusit sa gaseasca solutia :-'
Anyway, astept solutia oficiala, felicitari organizatorilor =D>

BTW, sper ca luati mai multi la finala de la clasele 11-12 ca ne-am straduit mai tare :oops:

Un set de probleme destul de dificil si interesant.
Propun ca editia urmatoare sa inceapa mai devreme ca sa nu se suprapuna cu celelalte concursuri :)

Hm... din pacate, email-ul cu anuntul datei schimbate a rundei 4 mi-a ajuns in Spam (pe gmail). Mi-ar fi placut sa particip, dar, intrucat nu verific site-ul suficient de des (si cum email-ul de la infoarena mi-a ajuns in spam), se pare ca am ratat data desfasurarii rundei (eu observasem doar data initiala, de 25 martie).

La finala merg primii 10 ?

Nu cobi! [-X

Am regrupat testele si am marit limita de timp la Spirala3 (http://infoarena.ro/problema/spirala3) ca sa intre solutiile in N^4 dar cu o constanta mai mare, iar cele in N^5 sa nu intre. Au fost reevaluate toate sursele.

Ati refacut si ratingurile?

Felicitari primilor clasati!

O solutie N^4 nu ar fi si cea trecuta de mine in articolul de solutii, pentru fiecare element verific cea mai lunga spirala care incepe cu el? Inca are 40 de puncte...
In alta ordine de idei, poate cineva care a obtinut 100 de puncte la o problema sa dea idei de rezolvare in articolul de solutii?

Pai asta e problema, cum gasesti care e cea mai lunga spirala care incepe cu el?

Daca intrebarea este "Este complexitatea N^4?", raspunsul e da, pentru fiecare element din matrice vizitez cel mult toata matricea (N^2 * N^2).
Daca intrebarea este "Cum ai implementat?": am doua functii, spirala_orar si spirala_trig, care incearca sa extinda spirala curenta cat mai mult tinand cont de punctul de plecare, parcursul de pana acum, si directia in care trebuie sa continui (sens trigonometric/orar). Si, nu, nu ma intorc in stari anterioare, informatiile necesare mi le transmit prin parametri. Am 40 de puncte cu TLE, deci nu memoria e problema.

Nu m-am uitat peste solutia ta dar daca soluta ta necesita mai mult de o secunda pe testul maxim ceva nu e bine. Solutia in N^5 avand constanta 4 merge in 1.2 implementata frumos.

Eu spun ca algoritmul meu e O(N^4) pentru ca parcurg matricea, si la fiecare pas, parcurg (in cel mai rau caz) toata matricea (unele elemente de 2-3-maxim 4 ori, dar nu cred ca asta inseamna N^5, doar o constanta). Nu imi dau seama de unde N^5: pentru fiecare element din matrice, ii parcurgi coloana, si pentru fiecare element de acolo, parcurgi intreaga matrice?

Nu am zis ca solutia ta ar fi N^5. Doar scoteam in evidenta cum se comporta o solutie in N^5. Nu contest ca solutia ta e N^4 dar daca se comporta mai prost poate nu e asa eficienta.
Pe acelasi principiu sunt suffix-array-urile in N log^2 N cu sort STL care se comporta mai bine ca cele in N log N cu radix sort.

@andrei.finaru: M-am uitat pe sursa ta si vad ca faci back :). In niciun caz nu ai O(N^4) acolo.

As vrea sa stiu daca cei calificati la runda finala a algoritmiadei au primit invitatii sau au fost anuntati in legatura cu participarea. Eu nu am primit nimic si nu as vrea sa pierd participarea din necunostinta de cauza. Va multumesc anticipat.

Invitatiile inca nu au fost trimise, verificati-va mailul zilele urmatoare :D

Nu puteam sti cam la ce loc s-au oprit invitiatiile?

Primii 10 de la fiecare grupa,singura exceptie fiind la grupa Open unde au fost selectati 11 deoarece pe locul 10 a fost egalitate de punctaje.  :)