263 Patrol

[ditzone]

Aici puteţi discuta despre problema Patrol.

[•pauldb]

Am citit solutia oficiala si am o nedumerire.

Presupunand ca am un graf format dintr-un lant cu n>120 si 0 politisti, nu inseamna ca hotul ajunge la destinatie intr-un timp > 120?

[•filipb]

Ba da, dar tu in graful nou construit o sa ai urmatoarele noduri:
(1 1), (2 1), (3 1)... (120 1), (121 1).
Perioada este 1, nu timpul efectiv care este 121!

[•bigsarpe]

any ideas how to build a generator and a brute force for this problem?

[•filipb]

Poti incerca teste random. Generezi muchii pentru graful dat pana cand ai ajuns la numarul de M muchii. De fiecare data cand ai o muchie noua generata verifici sa nu mai fi fost creata anterior ( faci asta folosind un tabel de hash ). Pentru a crea un traseu alegi un nod din graf si apoi tot alegi un nod vecin ultimului nod si care nu apartine drumului.
Pentru teste mici brute force poate insemna chiar back. Daca nu, poti implementa djikstra in timp patratic in numarul de noduri.

[•bigsarpe]

eu ma refeream ,sa construiesc teste intotdeauna cu o solutie dar banuiesc ca voi generati teste si verificati daca exista solutie si abia apoi il bagati la arhiva ca test oficial

[•filipb]

Da, pe teste mari asa se face