Algoritmiada 2013, Runda 2

[•deneo]

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

[•vladtarniceru]

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

Cod:

30000
push_back(999999)
push_back(999998)
push_back(999997)
...
push_back(970001)
pop_front()

Pe ultima linie o sa ai cam 700 000

[•repp4radu]

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

[•klamathix]

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

[•mugurelionut]

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...

[•repp4radu]

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

[•superman_01]

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

[•PlayLikeNeverB4]

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

Ce tare! 

[•mugurelionut]

@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].

[•a_h1926]

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 . As ramane indatorat daca ar explica cineva solutia.

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

[•klamathix]

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.

[•repp4radu]

@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 

[•mugurelionut]

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).

[•superman_01]

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

[•eudanip]

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.

[•mugurelionut]

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).

[•danalex97]

Frumoasa solutia de la CityLog.  

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

[•mihaipopa12]

Veti modifica ratingul in urma acestei runde?

[•gogu]

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.

[•visanr]

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? 

[•wefgef]

Trebuie facut manual, de catre Bogdan Tataroiu.

[•Challenge]

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). 

[•eudanip]

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). 

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.

[•cosmin79]

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.

[•Challenge]

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). 

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.

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).