infoarena

Runda 3 (http://www.infoarena.ro/algoritmiada-2015/runda-3) a concursului Algoritmiada 2015 (http://www.infoarena.ro/algoritmiada-2015) s-a incheiat. Felicitari castigatorilor! (http://www.infoarena.ro/algoritmiada-2015/runda-3/clasament/juniori) Asteptam feedback-ul vostru.  :)

Parca au fost ceva mai accesibile problemele fata de runda 2. Sunt curios daca exista solutie in timp liniar la Arb4. De asemenea, ceva aproximari legate de data finalei? Am auzit ca va fi la Cluj, ramane valabil?

Felicitari pentru runda ! Problemele super originale :) Apropo, 3 oameni de la fiecare clasa se iau la finala ?

Se poate O(n * log*n) dupa ce sortezi muchiile dupa cost.

Conform regulamentului:

Se vor califica 15 concurenţi din grupa de Juniori.

Pentru fiecare clasă de gimnaziu, primii 2 concurenţi de la această clasă în ordinea clasamentului vor fi calificaţi. Restul de 7 locuri se vor distribui în ordinea punctajelor concurenţilor care nu sunt calificaţi după primul criteriu.

Se vor califica 25 de concurenţi din grupa de Seniori.

Pentru fiecare clasă de liceu, primii 3 concurenţi de la acestă clasă în ordinea punctajului vor fi calificaţi.

Restul de 13 locuri se vor distribui în ordinea punctajelor concurenţilor care nu sunt calificaţi după primul criteriu. Numărul de participanţi calificaţi la finală care nu sunt elevi în clasele 5 - 12 este limitat la 5.

Concurenţii care pot participa la grupa de Juniori, dar aleg să participe la grupa de Seniori pot face acest lucru şi se pot califica la Runda Finală în cadrul acestei grupe.

Concurenţii care nu se încadrează la grupa de Juniori, dar aleg să participe la această grupă pot face acest lucru la rundele online, dar nu se pot califica la Runda Finala în cadrul acestei grupe.

Eu am O(M*log(N))

Si eu am M * log(N) cu o constanta destul de mica si iau 40p. A fost strânsă limita de timp. Oricum dacă sortai muchiile aveai deja M * log(M).

Eu am sortat muchiile, am facut un O(NlogN) pentru LCA si apoi am avut O(N*log*N) si am luat 40p, cu tot cu parsare, chiar ca cam stransa limita de timp.  #-o Totusi problema frumoasa.  :thumbup:

Foarte dubios. Sursa comisiei intra ca deobicei in jumate din limita de timp. Daca ai si parsat inseamna ca ai o constanta incredibila (macar de 7-8 ori mai mare decat a comisiei). Nu toate testele sunt maximale deci deja sursa ta se comporta ca un n log^2 n.

[Editat de moderator]

Legat de problema Arb4
e posibil sa faci O(MlogM) sortare + O(NlogN) RMQ + O(Mlog*N + M) solutia propriu-zisa.
Nu stiu cat de Mlog*N e, pentru ca tot ce faci e compresia drumurilor, nimic mai mult, pentru simplitate.
Dar e acceptabil :)

Codul meu, cu RMQ cu stramosi + parsare -> http://ideone.com/Kk0h9R
lua 690 fara parsare, poate pierdeam ceva si am spus sa nu risc.

Am bagat tot in concurs, inafara de parsare.
Nu e un capat de lume.

Problemele au fost super ok.
Site-ul la fel
Problema metrou3 sincer mi s-a parut cam jegoasa.
Ideea din spate nu e super grea.
Pentru fiecare statie vezi doar in momentul cand is trenurile in gara cum o sa se duca oamenii, mai faci acolo ceva inmultiri si sume partiale + cautari binare.

Ideea e intuitiva, dar implementarea mi se pare ca poate sa cauzeze super multe probleme aiurea.

La final de zi, sper ca i-a ajutat pe cei care dau bacul la info joi.
Doar pentru ei a fost pusa acum  :dance:

Cand se pun problemele in arhiva? Cred ca am gasit o solutie in O(MlogM + N) si sunt curios daca merge  :D
O(M log M) pentru sortare si dupa O(M + N)

Ca fapt divers problema Metrou se putea baga in O(N). Eu am totul O(N) cu exceptia unei sortari trebuia sa fac merge de 2 intervale (puteam chiar sa folosesc  inplace_merge din stl si solutia era O(N)).

Nu aveam cautari binare. Sunt surprins insa ca nimeni nu a bagat O(N ^ 2). Nu era aproape nimic de facut pentru ea