infoarena

A doua runda (http://infoarena.ro/algoritmiada-2013/runda-2) a concursului Algoritmiada 2013 (http://infoarena.ro/algoritmiada-2013) va avea loc duminica, 20 Ianuarie, la ora 9:00. Va asteptam in numar cat mai mare!

Mult succes tuturor!   :thumbup:

Nu prea se vad problemele. :))

Nu pot vedea problemele...

Trebuie sa le intuim cerintele dupa nume...

Nu apar problemele, la nici o clasa...

Nici la mine nu se vad.

Epic  :rotfl:

0 probleme momentan z

mie mi se vad ok toate, nu stiu ce greutati intampinati voi. 8)

,, Houston, we have a problem "

Aceeasi problema...

Va rugam , nu discutati problemele intre voi .

=)))))))))))))

Nici eu nu le pot vedea  ](*,)

cand dati drumu la probleme?

Putem sa asteptam , suntem rabadatori: Nu'i nicio problema !!:)))

Oricum, facand o paranteza de la subiect (cel cu coca cola), chestia faina e ca inca te poti dezinscrie 8)

sper ca se va rezolva problema cat de curand

problemele sunt tinute ostatice momentan, nu le vom da drumul prea curand  :evil:

Un minut !

Bafta tuturor !

Da-ti bataie !   :weightlift:

La treaba cu voi!!  :thumbup:

S-a blocat evalul.

Super problemele, felicitari autorilor :D

Frumoasa runda! Bravo!!!  =D>

Faine probleme!

Ar fi fain si un articol cu solutiile oficiale.

Pe cand se pun rezultatele?

Felicitari pentru probleme !  =D>

OFF : Nu ma pot abtine pana cand se face topicul de feedback.

Cand o sa se puna rezultatele?Mai reevaluati vreo problema?

se poate si fara reeval? :o

Cam asa eram eu in timpul rundei, nimic nu a mers.


(http://media.tumblr.com/tumblr_m08d4akz9B1r6h9nl.gif)

Rezlts pls

(http://i0.kym-cdn.com/entries/icons/original/000/003/549/1307920884001.jpg)

lol dat meme made me laugh)))

a fost o runda grea....

Mie mi-a placut foarte mult runda.E bine cand se dau probleme mai grele.Altfel, nu ai mai invata nimic din ele. :)

Ar fi frumos un articol cu solutiile ...

poate si rezultatele....

what about results??

(http://generatormeme.com/media/templates/250/10-guy.jpg)
I can't see the results because of the smell. Please, turn off the noise.

Nu mai puneti rezultatele odata?Concursul s-a terminat de mai mult de o ora :x

Am invatat tehnica asta la lotul de info.
Daca stai si te concentrezi, canalizandu-ti forta, folosind tehnici de Jedi, daca cineva care stie rezultatele se gandeste la ele, si tie o sa iti vina ideea ( in cazul acesta gandul ) si asa poti obtine mai repede rezultatele.  :)

E posibil sa refacem testele la 2stacks, rezultatele se vor posta mai tarziu. Ne cerem scuze.

Cam cat timp o sa mai ia?Nu ati putea sa afisati pana atunci separat pentru celelalte probleme?

Din ce am inteles de la restul comisiei sunt probleme cu 2stacks. Rezultatele vor fi afisate pentru toata lumea dupa ce se rezolva aceste probleme.

Avand in vedere dificultatile intampinate in rezolvarea situatiei de la problema 2stacks, am decis sa o scoatem din concurs. Astfel, punctajul maxim la clasele 5-9 si 11-12 va fi de 200p. Vreau ca in primul rand sa ne cerem scuze utilizatorilor care si-au consumat din timpul de concurs pe aceasta problema. Motivele care au stat in spatele acestei decizii sunt:
1. Testele au fost proaste. Detailed feedbackul, pe parcursul intregii probe, a indus in eroare participantii.
2. Complexitatea dorita in timpul concursului a fost de O(N^2), totusi momentan nu avem o solutie corecta care in teorie sa ruleze mai bine de O(N^3).
3. Consider ca problema, chiar si "reparata", ar fi prea diferita de ce s-a vrut initial, este ca si cum am adauga o problema noua dupa concurs si am folosi la evaluare sursele de la un alt task.

Ok, ati scos-o din lista. Dar rezultatele cand apar?

Ar fi util daca ar scrie cineva solutiile.  :thumbup:

By the way ... Ce complexitate trebuia la Mergesort ? Eu am gasit o solutie O(N lg N) , dar presupun ca nu asta e cea optima.  

Am trimis la queue o sursa goala care ia 100: http://infoarena.ro/job_detail/860763
Rog un admin sa se uite peste problema...

Cam stransa limita la circulatie. Iau 70 cu cuplaj

Si testele la queue, facute sa nu conteze cerinta de maxim 500000 de caractere pe linie  :thumbdown:

Da, intr-adevar faza cu 500 000 a fost cam derutanta ...
Pe un test de genul


Pe ultima linie o sa ai cam 700 000

@Petru Mie mi-a intrat in timp(608 ms pe cel mai naspa test) cu cuplaj.

Nu e stransa deloc. Avem si sursa care face 2 cuplaje si intra lejer in timp :).

La Citylog care era solutia ?

Eu am avut de ales dintre doua solutii:

1) sa fac aproape O(log(N)) pe operatie (memorand toti stramosii cu 2^i nivele mai sus pt fiecare nod), insa din cauza limitei de memorie nu se puteau tine toti stramosii pana la log(N) (caz in care devenea O(logmax) + O(N / 2^logmax) pt operatiile de tipul 1 -- logmax a ajuns pana la 6 pt a se incadra in limita de memorie) -- am incercat si varianta in care am "comprimat" mai multi stramosi in limita de memorie (pana la logmax=11), caci fiecare stramos avea nevoie doar de maxim 17 biti, insa era mai lenta din cauza ca faceam O(17) pt a seta/gasi fiecare stramos
2) sa memorez stramosii cu O(sqrt(N)) nivele mai sus pt fiecare nod (sau de la un nivel multiplu de sqrt(N)), care ar fi condus la o complexitate de O(sqrt(N)) pe operatie, ceea ce mi s-a parut prea mult pt limita de timp a problemei

In cele din urma am ales solutia 1 (cu diverse variante), neavand timp sa testez si varianta 2 (si neavand nimic care sa sugereze ca varianta 2 ar fi fost mai rapida).

Daca exista o alta solutie mai buna decat cele 2 mentionate, as fi curios sa o aflu. Daca cumva se voia solutia cu radical (pe care nu am incercat-o), atunci parerea mea e ca a fost o problema aiurea (pt ca limita de timp nu sugera ca o solutie cu O(sqrt(N)) pe operatie ar fi suficient de rapida). Sincer, sper ca exista o solutie mai desteapta la care nu m-am gandit eu...

Mie mi-a iesit cu prima solutie propusa de dvs. Am tinut pentru fiecare nod al 10^i-lea stramos.

La queue?care este solutia optima?...eu iau doar 30 cu tle pe celelalte teste...

Ce tare!  :thumbup:

@Radu Szasz: Ti-a iesit si recurenta ok ? (adica sa intre in timp)  Bineinteles ca m-am gandit si eu sa folosesc alta baza decat 2 pt stramosi. Dar ideea e ca daca vrei sa calculezi Ancesor(x,i) = al 10^i-lea stramos al nodului x, trebuie sa il calculezi in 10 pasi, nu ? (pornesti de la Ancestor(x,i-1) si mergi in sus de inca 9 ori din Ancestor(*, i-1) in Ancestor(*, i-1), pana acoperi o "distanta" de 10^i). Anyway, mie mi s-a parut ca asta o sa fie prea lenta pt limita de memorie (daca ai facut ceva mai destept de atat, please share).



@Petru Trimbitas: Referitor la circulatie (ai mentionat ca solutia cu cuplaj ar fi prea lenta): Eu am facut cuplaj (x 2), insa folosind optimizarea Hopcroft-Karp, care creste "fluxul" pe mai multe drumuri simultan. Altfel zis, pt fiecare parcurgere BFS pe care o faci nu cresti fluxul doar pe un singur drum, ci pe un numar maximal de drumuri disjuncte. In felul asta, complexitate devine O(M*sqrt(N)) (M=nr muchii, N=nr noduri), adica pt problema asta O(N*sqrt(N)). E suficient sa faci 2 cuplaje, pt ca al 3-lea consta din muchiile care nu sunt incluse in primele 2 cuplaje.



@Dan Alexandru: Referitor la Mergesort: Eu am facut O(N*log(N)), asa cum ai zis si tu. Practic am "simulat" mergesort-ul si pt fiecare interval [left,right] la care se ajunge conform algoritmului am calculat (in timp O(1)) cate permutari ajung pana la intervalul respectiv (avand intervalul respectiv ori sortat ori nesortat) -- ideea e ca daca numarul de permutari pt care ajungi la un interval [left,right] este X (indiferent daca continui mai departe sau nu), rezultatul este suma acestor valori X pt fiecare astfel de interval [left,right].

Eu am implementat a doua solutie a dumneavoastra, dar tot nu a intrat in timp (deci nu asta se dorea). M-am gandit si eu tot ca dumneavoastra la solutia cu aproape NlogN memorie, dar nu am pierdut timpul cu ea pentru ca am considerat ca oricum nu va intra in memorie si ca se doreste o solutie O(MlogN) ca timp si O(N) ca memorie. Sunt si eu foarte curios care este solutia oficiala :D. As ramane indatorat daca ar explica cineva solutia.

Edit: se pare ca noi cei care am cautat solutia optima ne-am pacalit :D se pare ca se putea lua maxim si cu solutii nedorite

La CityLog, ideea era sa calculezi stramosii doar pentru N / log N noduri, alese random. La query aveai 3 cazuri.

1. Esti in nod precalculat -> scoti msb-ul din y si continui.
2  Nu esti in nod precalculat, iar stramosul cautat este mai jos decat cel mai apropiat stramos precalculat. In cazul asta, poti merge din tata in tata fiindca distanta asteptata intre 2 noduri precalculate este O(log N).
3. Nu esti in nod precalculat, iar cel mai apropiat stramos precalculat este mai jos decat stramosul de query, caz in care sari direct in el si esti iar in cazul 1.

Asa iese O(N) memorie si O(logN) pe query. Din pacate s-a dovedit imposibil sa diferentiem asta de solutii cu memorie N log N dar cu baza mare la logaritm.

@Mugurel Ionut Andreica Exact cum ati spus acum am facut si a intrat in timp cu 1.1s pe cel mai naspa test.

@Mihai Calancea Foarte faina solutia  =D>

Am gresit analiza complexitatii solutiei mele la mergesort. De fapt, iese O(N). Numarul de intervale prin care trece mergesort este doar O(N) -- practic, o analiza de calcul simpla ne spune ca sunt N intervale de lungime 1, N/2 intervale de lungime 2, N/4 intervale de lungime 4, etc. Asadar, numarul de intervale este aprox. N+N/2+N/4+N/8+....+1=aprox. 2*N=O(N). Cum fiecare interval este procesat in timp O(1), reiese ca solutia are complexitate O(N).

deci..nimeni nu are o idee la queue?as ramane dator :)

La mergesort complexitatea oficiala era O(n + log(n)). Eu precalculam factorialele si invers modularele si dupa calculam pentru fiecare din cele log(n) lungimi de intervale distincte (desi sunt O(n) intervale sunt doar log(n) lungimi distincte) cat ar fi raspunsul fata de cea din care vine. Si dadeai cu combinari.

LE: la circulatie limita era buna. eu ca prostu am facut 3 cuplaje si a intrat lejer in timp.

Asa e, sunt doar O(log(N)) lungimi distincte, dar eu n-am vrut sa ma complic in vreun fel, asa ca am considerat toate intervalele independent.

In solutia mea nu am avut nevoie de inverse modulare (desi initial mi s-a parut ca as avea). Toti factorii importanti pe care ii aveam erau de forma Combinari(N,K) * (N - K)!  (pt diverse valori ale lui K). Daca explicitam combinarile, obtinem N! / (K! * (N-K)!) * (N-K)! = N!/K!. Asadar, toti termenii importanti erau de forma N!/K! = N * (N-1) * (N-2) * ... * (K+1) => am precalculat valorile astea (sunt O(N) astfel de valori, "sufixe" ale lui N!): in mod evident N!/K! = N!/(K+1)! * (K + 1).

Frumoasa solutia de la CityLog.  =D>

@Mugurel Ionut Andreica : Multumesc. Am lucrat asemanator cu dvs la Mergesort.

Veti modifica ratingul in urma acestei runde?

Felicitari, chiar mi-a placut runda.
Solutia mea din concurs la CityLog a fost tot un logaritm cu baza mare, si imi pare rau ca solutia comisiei nu a putut sa departajeze solutiile cu memorie chiar O(N), trebuiau limite mai stranse la memorie.
Se putea o solutie buna si cu 2 intregi pe nod (am cam spamat evaluatorul pentru testare):

http://infoarena.ro/job_detail/861474

Pentru fiecare nod am retinut tatal sau, sau predecesorul cu 2^K nivele mai sus (unde K e aleator ales intre 1 si logN).
Daca trebuie sa sar >= 2^K nivele, atunci ma duc la predecesor, altfel ma duc in tata (care are sper un K mai mic). Complexitatea e undeva intre O(logN) si O((logN)^2)
Mergea pusa asa limita de memorie la 1 - 1.1MB, si era mult mai greu pentru solutiile cu baza mare sa ia puncte.

Cand se va face update la rating?
Vad ca, la cam toate rundele, dureaza cam mult pana se face update-ul, care ar fi motivul?  :)

Trebuie facut manual, de catre Bogdan Tataroiu.

Subscriu la intrebarea pe care a pus-o si Mihai Popa mai sus: se va mai modifica ratingul dupa aceasta runda?

LE: dupa ce am postat am vazut ca s-a modificat. Totusi nu pot sa inteleg cum de runda asta de concurs mi-a afectat ratingul de la ultima runda de .com (inainte era 700 acum e 699).  :eyebrow:

Observand evolutia ratingului tau tin sa apreciez faptul ca de la 699 ai coborat tocmai la 669. Mai like a Boss de atat nu cred ca se putea.

Mi se pare cam mica limita de timp la mergesort. Solutia mea(corecta), desi are O(N) complexitatea, ia TLE-uri pe aproape jumate de teste.

Nu la asta ma refeream, am vazut si eu ca pe grafic,
ratingul scade de la 699 la 669 insa eu ziceam ca
inainte de aceasta runda de concurs, acel 699 era
defapt 700 (stiu sigur pentru ca inainte eram rosu iar acum, dupa cum se vede, in ultima perioada nu mai este nici un punct rosu pe grafic).

Si eu am tot O(N) si am luat 100, ultimele 2 teste au 92 ms.  :-k

Eu am 48 de ms. Limita a fost stransa pentru a departaja O(N)-urile de O(N log N).
Avem o sursa in N log N care merge mai repede ca a ta Cosmin.

Observatia cheie e ca iti trebuiau doar factorialele, dupa complexitatea devenea log^2.

Pana la urma, cu 2stacks ce faceti ?

El intreba daca se refac testele si se pune problema in arhiva  :)

Am inteles chestia asta si faptul ca complexitatea dorita era de N², chiar daca nu s-a gasit una mai buna ca N³, dar am intrebat pentru ca eram curios daca o s-o refaca, sau .... nu.
[LE] Merci George, mi-ai luat-o inainte.

Revin cu parerea ca este nedrept updateul ratingului la runda aceasta, cel putin la clasele 11-12 si 5-9 unde a fost data problema 2stacks.
Am inteles ca problema a fost scoasa din concurs dar cred ca intelegeti cat de frustrant este pentru concurentii care au avut "ghinionul" sa se apuce de ea si sa isi risipeasca timp considerabil pentru a o rezolva.

Nu vreau sa para ca ratingul este scopul activitatii mele pe infoarena, dar de exemplu nu inteleg de ce ati judecat acum situatia diferit de runda 6 de monthly, unde nu l-ati actualizat pentru ca in primele minute au fost niste teste gresite la feedbackul unei probleme.

In rest, sincere felicitari pentru probleme pentru ca au fost foarte reusite.

+1

Eu as vrea sa continui ideea si sa reamintesc echipei Infoarena ca daca pana acum la celelalte concursuri s-au mai strecurat greseli, aici este vorba totusi de cel mai important concurs al acestei comunitati, Algoritmiada, si macar aceasta sa tinda catre 0 greseli. Personal cred, ca aceasta runda ar trebuii sa nu mai conteze de loc la clasamentul pentru Algoritmiada si sa aiba loc alta runda.

Eu personal, nu sunt de acord cu ceea ce propuneti. Intr-adevar, a fost o problema care s-a eliminat, insa a fost eliminata pentru toata lumea, deci nu s-au produs discriminari.

In al doilea rand, ar fi nedrept pentru cei care au obtinut un punctaj ok la celelalte doua probleme. In concurs, conteaza si impartirea timpului intre probleme si chiar daca s-ar putea ca feedback-ul sa va fi indus in eroare, nu va oprea nimeni sa treceti la alta problema.

Nu e chiar asa. Gandestete ca daca ai fi fost in locul lor, te-ai fi ofticat si tu. Desigur ca strategia de concurs e buna si cateodata trebuie sa mai schimbi problemele dar e o strategie si sa consideri ca problema la care lucrezi e buna. Imagineazati ca primesti o problema pe care esti la fel de sigur ca la problema A+B si nu vrei sa o lasi pana nu iti iese si sa fie defapt problema busita. Sunt de acord cu Mihai Popa (rating-ul sa nu se schimbe) dar nu si cu Murtaza (doar daca era zi de ONI sau lot atunci ar trebui eliminata runda).

Trebuie sa recunosc ca imi vine greu sa cred ca timpul alocat problemei de catre unii concurenti a fost atat de insemnat incat sa justifice refacerea/anularea rundei(chiar si la nivel de rating).

A nu se intelege ca nu cred ca s-a pierdut timp cu 2stacks, in conditiile in care si eu am pierdut aprox 2 ore incercand sa o rezolv.

Insemnat sau ne insemnat, a fost variabil de la un concurent la altul, in consecinta a facut diferenta (fie ea cat de mica)!

Asta imi aminteste de:


Cred ca cel mai bine ar fi sa nu se afecteze rating-ul la clasele ce au avut aceasta problema, insa runda sa conteze la clasamentul final al Algoritmiadei.

Bun. In primul rand suntem subiectivi; fiecare isi urmareste propriul scop. In al doilea rand propunerea cu anularea rundei e exagerata; ca si argument sunt de acord cu ce a zis eudanip anterior. Iar despre rating din cate vad s-a updatat si da as vrea sa ramana cum e :)) ( cel putin mie ). Si sunt de acord cu Szasz Radu, mai exact nimeni nu va oprit sa incercati celelalte probleme. Aceleasi conditii le-am avut toti.
Pt Popa Mihai : Defapt cred ca era runda a 4-a. Iar apoi structura concursului Monthly e diferita de Algoritmiada.

Personal, am petrecut cam 3,5 ore pe 2stacks. Sunt sigur ca nu am fost singurul caruia i-a trecut prin cap ca aceasta va fi o problema accesibila. Am avut senzatia asta pe tot parcursul rundei si mi se pare normal ca am actionat in consecinta.

Nu am spus ca imi doresc sa se refaca runda (stiu ca presupune foarte multa munca si ar fi nedrept pentru cei care au facut bine acum) dar neactualizarea ratingului mi se pare un lucru simbolic care se impune.


Nimeni nu ne-a oprit sa incercam celelalte probleme dar in departajarea concurentilor a intervenit sansa, ceea ce nu mi se pare ok, mai ales in vederea calficarii la finala.
Nu are nicio relevanta structura diferita a concursului Monthly fata de Algoritmiada (ar fi avut doar daca problema ar fi fost corectata/reevaluata/macar anuntata drept gresita in timpul probei).
Din contra, mi se pare mai grava situatia de acum; Algoritmiada are doar 3 sau 4 runde, fata de 12 si, de asemenea, o miza mai mare.

Vina ne apartine doar noua. Fiecare poate aborda concursul in maniera in care doreste, rezolvand orice problema doreste. Nu ar trebui sa fie necesar pentru nimeni sa-si adapteze strategia pentru a suplini neajunsurile comisiei. Vom face runda unrated, dar din pacate mai mult de atat nu putem face. Ne cerem scuze din nou.

Am dat rewind la rating pentru cei de la clasele 5 - 9 si 11 - 12 :).

Rewind infoarena style  :D

Apropo, si mie mi-a crescut in mod misterios ratingul cu un punct  ???. Am vazut ca a mai pomenit cineva de asta.

Probabil e de la erorile de precizie.

Eu nu ma prind de ce 2stacks nu se putea face in O(N^2)
ca pe dinamica de la cel mai lung subsir comun (T[ i ][j]) bagai o dinamica gen

d[ i ][j]=nr de moduri de a pune numerele in stive astfel incat sa-ti dea doua stringuri egale cu lungimea T[ i ][j]

d[ i ][j]+= d[i-1][j-1] , daca A[ i ]==B[j]
d[ i ][j]+= d[i ][j-1]    , daca T[ i ][j]==T[ i ][j-1]
d[ i ][j]+= d[i-1][j]    , daca T[ i ][j]==T[i-1][j]

e ca si cum ai parcurge matricea astfel incat sa mergi de nr T[N][N] ori pe diagonala.
De fiecare data cand mergi in dreapta sau in jos simulezi o introducere in stiva.

Din cauza acestei fraze:

Ce zici tu este fix solutia oficiala intiala, dar ea nu respecta restrictia de mai sus. Adica, iti garanteaza ca in stive sunt in ordine crescatoare, dar nu iti garanteaza si ca daca interclasezi operatiile, ele sunt in ordine crescatoare in continuare.

Mie mi se pare ca singura dificultate a problemei apare atunci cand aceeasi pozitie trebuie eliminata din ambele siruri (pt ca ai 2 variante de a ordona cele 2 operatii pt pozitia comuna). Altfel, daca din cele 2 siruri s-ar elimina seturi de pozitii distincte, ar fi un mod unic de a le interclasa pt a iesi in ordine crescatoare (si, astfel, raspunsul ar fi egal chiar cu numarul de subsiruri comune de lungime maxima, diferite doar ca seturi de pozitii, ceea ce se poate calcula usor extinzand un pic dinamica standard).

Mai exact, daca exista K pozitii eliminate din sirul 1 comune cu pozitiile eliminate din sirul 2 (pt a obtine dupa eliminare un subsir comun maxim), atunci pt acest subsir comun maxim trebuie adunata la rezultat valoarea 2^K  (pt ca pt fiecare pozitie comuna poti elimina ori mai intai pozitia din primul sir, ori pe cea din al doilea sir, dar in afara de asta, pozitiile pot fi interclasate intr-un singur fel).

Insa nu imi dau seama daca s-ar putea modifica cumva dinamica standard pt subsir comun de lungime maxima pt a "prinde" in solutii cazurile cand aceeasi pozitie i este eliminata din ambele siruri (ea "prinde" fara probleme cazurile cand aceeasi pozitie i este pastrata din ambele siruri, dar noua nu asta ne trebuie).