117 Poligon 2

[•domino]

Aici puteţi discuta despre problema Poligon 2.

[•pauldb]

Am implementat aceasta problema in O(n), n<=10000  shi totushi iau 3 TLE. Ceea ce este mai interesant este ca iau TLE pe primele 2 teste, care presupun ca ar trebui sa fie mici.  Explicatzi-mi, va rog, care este gresheala; sunt sigur ca nu am cicluri infinite in rezolvare. Multzumesc.

[•pauldb]

Inainte de a se schimba calculatorul pe care se face evaluarea luam cele 3 teste, dar nu luam altele (gresisem sursa). Puteti verifica daca eroarea nu provine de la evaluator?

[•fireatmyself]

eu am rezolvat-o in O(n) si nu iau TLE. sigru programul tau e devina. rescrie sursa. chestia asta ajuta in astfel de situatii

[•pauldb]

ok... voi incerca...

Tu ai trimis problema dupa ce s-a modificat calculatorul de pe care se facea evaluarea?

[•Cosmin]

Limita de timp e prea stransa pentru pascal, 2 foruri iau tle pe un test ...

[•fireatmyself]

o(n^2) sau o(2*n) ?  

[•Cosmin]

Ia ghici ... (se scrie cu O mare, o mic are alta semnificatie, si nu am vazut O(2n) pe nicaieri , eventual O(n) )

[•fireatmyself]

apucasem sa scriu cu 'o' mic si mi-a fost lene sa editez . nu ai vazut pe nicaieri, dar, in unele cazuri, constanta din fata 'n'-ului poate sa atarne greu (io am patit-o   ). cat despre exprimarea ta :

Limita de timp e prea stransa pentru pascal, 2 foruri iau tle pe un test ...

poate fi interpretata in doua moduri :

Cod:

for i=1,n
begin_for
   .....
   for j=1,n
   begin_for
       .....
   end_for
end_for

sau

Cod:

for i=1,n 
begin_for 
.....
end_for

for i=1,n 
begin_for 
.....
end_for

[•greco]

Cred ca stie si Cosmin ca "constanta poate sa conteze"... dar te-ai exprimat gresit in orice caz. Nu exista O(2 * N).

De asemenea, cred ca si-a dat seama si de interpretarea celor 2 foruri, dar ti-a raspuns la misto ca i s-a parut evident care dintre variante e corecta.  

[•fireatmyself]

dar te-ai exprimat gresit in orice caz. Nu exista O(2 * N)

am inteles varule, dar ideea postului meu a fost sa-i arat cum poate fi interpretat postul lui [nu e nimic personal, Cosmin]

[•wefgef]

schimbati va rog limita, caci in pascal nu imi intra in timp nici macar citirea. probabil maine rescriu in c, dar nah...

[•pauldb]

Si eu am implementat-o Pascal si mi-a intrat in timp, dar incercati sa folositi for nu while (works faster)...

[•gogu]

Nu e de la asta.
Oricum cam tot timpul e consumat de citirea si scrierea datelor.
Inainte se foloseau versiuni de compilatoare cu bug-uri la operatiile IO.