308 Amenzi

[•DITzoneC]

Aici puteţi discuta despre problema Amenzi.

[•StTwister]

Care este complexitatea oficiala?

O sa apara si un articol cu solutiile de la unirea ?

[•wefgef]

Un O(Tmax*m) intra in timp lejer. Hint : PD.

[•StTwister]

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?

[•astronomy]

Da, la query raspunzi in O(1). Spune cum faci tu dinamica sa vedem unde te complici

[•StTwister]

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)

[•Marius]

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.

[•svalentin]

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"

[•Marius]

Intelesesem gresit enuntul. Intalnirile acelea erau independente unele de altele. 

[•crus]

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?

[•pauldb]

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.

[•cos_min]

Chiar nu inteleg ce busesc, iau doar 30 pcte  . Fac dinamica din articol: a[j] - maxim pt timp i la inter. j...

[•filipb]

Pot fi mai multe amenzi in acelasi timp si in acelasi nod. Verifica daca ai tratat acest aspect.

[•cos_min]

Multumesc ff mult, asta era