|
Titlul: 308 Amenzi Scris de: Adrian Diaconu din Ianuarie 27, 2007, 18:17:56 Aici puteţi discuta despre problema Amenzi (http://infoarena.ro/problema/amenzi).
Titlul: Raspuns: 311 Amenzi Scris de: Kerekes Felix din Ianuarie 28, 2007, 14:03:40 Care este complexitatea oficiala?
O sa apara si un articol cu solutiile de la unirea ? Titlul: Raspuns: 311 Amenzi Scris de: Andrei Grigorean din Ianuarie 28, 2007, 16:07:04 Un O(Tmax*m) intra in timp lejer. Hint : PD.
Titlul: Raspuns: 311 Amenzi Scris de: Kerekes Felix din Ianuarie 28, 2007, 17:33:08 Pai presupun ca pe aceasi idee am mers si eu, dar nu reusesc sa reduc complexitatea.
Toate query-urile se fac in timp constant, dupa preprocesare, nu? Titlul: Raspuns: 311 Amenzi Scris de: Airinei Adrian din Ianuarie 28, 2007, 17:42:08 Da, la query raspunzi in O(1). Spune cum faci tu dinamica sa vedem unde te complici
Titlul: Raspuns: 311 Amenzi Scris de: Kerekes Felix din Ianuarie 29, 2007, 15:13:33 Dinamica am facut-o exact ca in articol, da foloseam o parcurgere in latime si puneam in coada momentul de timp si nodul, incepand cu nodul 1 si momentul 0. Apoi parcurgeam pentru fiecare nod toti vecinii si toate amenzile din acel nod si le bagam in coada.
Si rezultatul -> 0 puncte :yahoo: (toate TLE) Titlul: Raspuns: 311 Amenzi Scris de: Marius Stroe din Ianuarie 29, 2007, 20:46:59 Rezolvare de 0 puncte : am sortat crescator dupa timp "intalnirile cu sotia", apoi pentru fiecare am aplicat o PD cu memoizare, am retinut rezultatul si am initializat cu -1 R[X][T] pentru a nu transmite informatia mai departe R[X + 1][T], respectiv R[Y][T + k]. Am dat o multime de teste de mana dar, nici un rezultat gresit ... Voi cum ati completat matricea ? Multumesc.
Titlul: Raspuns: 311 Amenzi Scris de: Valentin Stanciu din Ianuarie 29, 2007, 21:07:49 Faci o singura data, la inceput, Programarea Dinamica si pastrezi toata matricea rezultata. Apoi cand urmeaza intrebarile, raspunzi usor in O(1).. matricea ar veni D[X][Y] = amenzile maxime ce pot sa le dau pana in momentul X si acum ma aflu in intersectia Y
Deci nu trebuie sa sortezi crescator "intalnirile cu sotia" Titlul: Raspuns: 311 Amenzi Scris de: Marius Stroe din Ianuarie 29, 2007, 22:25:08 Intelesesem gresit enuntul. Intalnirile acelea erau independente unele de altele. ](*,)
Titlul: Răspuns: 308 Amenzi Scris de: Rus Cristian din Ianuarie 31, 2007, 22:08:25 am urmatoarea problema...fac dinamica 'nainte...daca am deja max[timp][nod], calculez pt toti vecinii lui, in care pot ajunge, noul maxim, e bine ce fac?...sau am gresit ceva la gandirea asta?
Titlul: Răspuns: 308 Amenzi Scris de: Paul-Dan Baltescu din Februarie 01, 2007, 01:35:52 Depinde ce intelegi tu prin "noul maxim". Starile sunt bune, dar maximul ramane acelasi. O amenda nod, timp, cost o iei in considerare cand ajungi starea max[timp][nod] pe care o cresti cu cost.
Titlul: Răspuns: 308 Amenzi Scris de: Bondane Cosmin din Februarie 01, 2007, 20:58:11 Chiar nu inteleg ce busesc, iau doar 30 pcte :'(. Fac dinamica din articol: a[j] - maxim pt timp i la inter. j...
Titlul: Răspuns: 308 Amenzi Scris de: Filip Cristian Buruiana din Februarie 01, 2007, 21:10:54 Pot fi mai multe amenzi in acelasi timp si in acelasi nod. Verifica daca ai tratat acest aspect.
Titlul: Răspuns: 308 Amenzi Scris de: Bondane Cosmin din Februarie 01, 2007, 21:18:36 Multumesc ff mult, asta era :D :thumbup:
|