•DITzoneC
|
|
« : Ianuarie 27, 2007, 18:17:56 » |
|
Aici puteţi discuta despre problema Amenzi.
|
|
« Ultima modificare: Ianuarie 30, 2007, 20:51:35 de către Crestez Dan-Leonard »
|
Memorat
|
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #1 : Ianuarie 28, 2007, 14:03:40 » |
|
Care este complexitatea oficiala?
O sa apara si un articol cu solutiile de la unirea ?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #2 : Ianuarie 28, 2007, 16:07:04 » |
|
Un O(Tmax*m) intra in timp lejer. Hint : PD.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #3 : 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?
|
|
|
Memorat
|
|
|
|
•astronomy
|
|
« Răspunde #4 : Ianuarie 28, 2007, 17:42:08 » |
|
Da, la query raspunzi in O(1). Spune cum faci tu dinamica sa vedem unde te complici
|
|
|
Memorat
|
|
|
|
•StTwister
Client obisnuit
Karma: 11
Deconectat
Mesaje: 86
|
|
« Răspunde #5 : 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 (toate TLE)
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #6 : 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.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•svalentin
|
|
« Răspunde #7 : 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"
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #8 : Ianuarie 29, 2007, 22:25:08 » |
|
Intelesesem gresit enuntul. Intalnirile acelea erau independente unele de altele.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•crus
Strain
Karma: 3
Deconectat
Mesaje: 44
|
|
« Răspunde #9 : 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?
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #10 : 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.
|
|
|
Memorat
|
Am zis
|
|
|
•cos_min
|
|
« Răspunde #11 : 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...
|
|
|
Memorat
|
vid...
|
|
|
•filipb
|
|
« Răspunde #12 : Februarie 01, 2007, 21:10:54 » |
|
Pot fi mai multe amenzi in acelasi timp si in acelasi nod. Verifica daca ai tratat acest aspect.
|
|
|
Memorat
|
|
|
|
•cos_min
|
|
« Răspunde #13 : Februarie 01, 2007, 21:18:36 » |
|
Multumesc ff mult, asta era
|
|
|
Memorat
|
vid...
|
|
|
|