|
Titlul: 123 Razboiul lumilor Scris de: ditzone din Octombrie 23, 2005, 21:48:48 Aici puteţi discuta despre problema Razboiul lumilor (http://infoarena.ro/problema/razboi).
Titlul: 123 Razboiul lumilor Scris de: Ovidiu Rosca din Octombrie 29, 2005, 21:12:30 Complexitatea e O(n*t), nu? Poate sa-mi dea cineva vreun hint? Eu nu am reusit decat ceva de genul O(n*n*t) care, evident, nu intra in timp.
Titlul: 123 Razboiul lumilor Scris de: Iorgulescu Calin din Octombrie 29, 2005, 21:29:50 Eu am facut un algoritm O(N*T). Dar nu sunt sigur de corectitudine... Si dat fiind ca nu iau 100... presupun ca nu e corect... or uit ceva. Iata ce fac eu:
1. Leg de frunze un nod virtual care are distanta catre acele noduri 0 2. Pornesc un bfs din acel nod astfel incat sa generez intr-un vector distantele minime din orice nod catre cea mai apropiata frunza. 3. Selectez maximul dintre aceste valori. 4. Afisez toate nodurile care au distanta maxima. Pe testul dat in exemplu merge. Logic cred ca ar trebui sa fie ok. Daca poate cineva sa-mi zica daca ii se pare incorect. Mersi mult. Titlul: 123 Razboiul lumilor Scris de: Tiberiu-Lucian Florea din Octombrie 30, 2005, 12:19:17 Cred ca aceasta modalitate de a aborda o problema nu este foarte productiva. Ar fi mai bine sa pui mana pe foaie, sa vezi exact cum sta treaba, si sa te apuci de implementat numai in momentul in care esti sigur ca algoritmul tau e corect. Daca implementezi ideile care iti vin si lasi evaluatorul infoarena sa-ti spuna daca erau bune sau nu, o sa ai surprize pe la concursuri...
Titlul: 123 Razboiul lumilor Scris de: Ovidiu Rosca din Octombrie 30, 2005, 13:15:18 Citat din mesajul lui: calinux Eu am facut un algoritm O(N*T). Dar nu sunt sigur de corectitudine... Si dat fiind ca nu iau 100... presupun ca nu e corect... or uit ceva. Iata ce fac eu: 1. Leg de frunze un nod virtual care are distanta catre acele noduri 0 2. Pornesc un bfs din acel nod astfel incat sa generez intr-un vector distantele minime din orice nod catre cea mai apropiata frunza. 3. Selectez maximul dintre aceste valori. 4. Afisez toate nodurile care au distanta maxima. Pe testul dat in exemplu merge. Logic cred ca ar trebui sa fie ok. Daca poate cineva sa-mi zica daca ii se pare incorect. Mersi mult. Pai din ce inteleg eu tu calculezi distantele minime de la orice nod catre frunze. In enunt se cam cere altceva... (scuze daca am zis vreo prostie, sau am inteles prost explicatia ta) Totusi, se indura cineva sa-mi dea un hint? Titlul: 123 Razboiul lumilor Scris de: Filip Cristian Buruiana din Octombrie 30, 2005, 18:33:58 Pornesti un DFS din nodul 1 si pt fiecare nod calculezi in timpul DFSului distanta maxima a nodului respectiv la fiii sai. Apoi pt. fiecare nod calculezi si distanta maxima "in sus" din arborele DFS... ( nu mai zic cum :clover: ). Totul e in O(N) pe test.
Titlul: 123 Razboiul lumilor Scris de: u-92 din Noiembrie 20, 2005, 18:16:42 nu.. eu tot nu ma prind ](*,) adica nu imi dau seama cum sa determin distanta "in sus" in o(n)
Titlul: 123 Razboiul lumilor Scris de: VladS din Noiembrie 20, 2005, 18:21:51 Incearca sa rezolvi Color2 ca e cam aceasi idee si ai solutie oficiala din care te poti inspira.
Titlul: 123 Razboiul lumilor Scris de: u-92 din Noiembrie 20, 2005, 19:46:04 mersi, m-am prins acum :peace: rezolvasem si eu color2, dar acolo era oarecum mai simplu..
Titlul: Raspuns: 123 Razboiul lumilor Scris de: Anca Dumitrache din Decembrie 14, 2006, 22:26:39 sunt destul de nedumerita, am calculat pt fiecare nod subarborele cu radacina in nodul respectiv si suma distantelor maxima, si apoi am ales nodurile cu sume minime... in timp intra, exemplul de pe site merge, merg si cateva cazuri facute de mine, chiar nu reusesc sa-mi dau seama ce am gresit... oare nu e buna ideea de rezolvare?
Titlul: Raspuns: 123 Razboiul lumilor Scris de: Paul-Dan Baltescu din Decembrie 14, 2006, 23:06:54 Cod: 2 Cod: Testul nr #1 Titlul: Raspuns: 123 Razboiul lumilor Scris de: Anca Dumitrache din Decembrie 14, 2006, 23:13:05 merci :).. la primul test nu-mi afiseaza decat 12, but i'm working on it
Titlul: Răspuns: 123 Razboiul lumilor Scris de: Macarescu Sebastian din Aprilie 12, 2012, 10:02:16 Nu ar trebui micsorata limita de timp :) ? Sursa mea http://infoarena.ro/job_detail/733433 (http://infoarena.ro/job_detail/733433) merge sub 200 ms.
Titlul: Răspuns: 123 Razboiul lumilor Scris de: Mihai Visuian din Septembrie 22, 2012, 22:09:17 La primul test, nu inteleg de ce e orasul 4. Nu ar trebui sa fie primul oras, pentru ca e mai aproape de multe orase decat 4? ???
Titlul: Răspuns: 123 Razboiul lumilor Scris de: Dumitru Andrei Georgian din Septembrie 22, 2012, 22:19:20 Problema iti cere sa alegi orasul pentru care drumul maxim intre el si orice alt oras e minim. In cazul testului 1, distanta maxima de la orasul 4 la alt oras este 5 (drumul de la 4 la 3), pe cand distanta maxima de la orasul 1 la alt oras este 7 (drumul de la 1 la 5).
Titlul: Răspuns: 123 Razboiul lumilor Scris de: Pirtoaca George Sebastian din Decembrie 14, 2012, 09:19:16 Folosesc multiset din STL si vreau ca functia heap.erase(x) sa stearga un singur element cu valoarea x chiar daca sunt mai multe cu aceeasi valoare. Cum fac asta? Multumesc!
Titlul: Răspuns: 123 Razboiul lumilor Scris de: Salajan Razvan din Decembrie 14, 2012, 09:42:24 stergi iteratorul pe care se afla elementul X
faci ceva de genul : Cod: multiset<int>::iterator it; Titlul: Răspuns: 123 Razboiul lumilor Scris de: Pirtoaca George Sebastian din Decembrie 14, 2012, 14:15:56 Multumesc! A mers pana la urma.
|