010 Stramosi

[•APOCALYPTO]

nu intzeleg o chestie dc 2^k trb <=n  dak avem totzi stramoshtii (1->2->3->4->5->6) unde primul stramos e 2 iar al 5-ilea 6 iar 2^5>6

[•Florian]

pai ai A[ k ] [ i ] - cel de-al 2^k-lea stramos a lui i. Daca 2^k > n, atunci cel de-al 2^k-lea stramos a lui i nu exista [ pt ca i are maxim n stramosi ] 

[•mathboy]

Fac un df recursiv si am o complexitate de O (N + M). Cu toate acestea primesc KBS 11 pe ultimul test. Am modificat limitele pana la 400 000  si am ajuns sa folosesc 40MB din memorie dar degeaba. Daca ar putea sa ma ajute cineva i-as ramane recunoscator. Multumesc.
Aici e sursa : http://infoarena.ro/job_detail/391337?action=view-source.

[•pauldb]

Poate e din cauza recursivitatii. Incearca sa scrii DFS-ul iterativ.

[•mathboy]

Am luat suta in sfarsit. Din cauza df-ului recursiv era KBS-ul ala. Multumesc inca o data .

[•mihaionly]

ObÈ›in "Killed by signal 11(SIGSEGV)." oricât de mare mi-aÈ™ fi declarat vectorul, iar algoritmul respectă la fix ideea matricii A[log(n)][n]. 
E a noua oară când uploadez sursa cu modificări minore care am crezut eu că pot fi cauza iar răspunsul e tot același.. signal 11
http://infoarena.ro/job_detail/395149?action=view-source

[•tinky]

a luat cineva 100p cu un program de complexitate n+m*p?
Pentru fiecare query caut stramosul cu ceva de genul x = tata [ x ]; (pentru asta am luat 80 p cu TLE pe ultimele 2)
Am incercat si sa imi 'preprocesez' al p-lea stramos pentru fiecare om si am luat memory limited exceeded pe ultimele 4 teste

[•ctlin04]

Poate cineva sa-mi explice de ce la intrbarea 5 din exemplu raspunsul e 8 dar nu 10?

[•PlayLikeNeverB4]

Al 3-lea stramos al lui 13 este 8. Mergand in sus pe arbore primul e 12, al doilea e 10.

[•retrograd]

Complexitatea oficiala este O(m+n)? Eu asa am facut-o, chiar fara multa bataie de cap(ca implementare)

[•klamathix]

Sunt 2 soluÈ›ii, cea pe care o ai tu în O(n + m) È™i una în O(n log n + m log n) care are avantajul că poate răspunde online la query-uri, nu are nevoie să le È™tie pe toate de la început. Ambele idei È™i implementări sunt utile 

[•vlad082002]

Ok am rezolvat problema cu stramosii de ordin 2^k ai fiecarui nod dar nu inteleg de ce ruleaza mai repede daca inversez indicii din matrice, imi poate explica cineva?