In cat timp sa rezolve solutia comisiei.

[•fluffy]

Am si eu o propunere, sa introducem o noua restrictie, solutia comisie sa ruleze in maxim x% din timpul disponibil.
Sa nu mai avem probleme de genul stramosi si cutii fix la limita.

[•Cosmin]

Limita din concurs si limita din arhiva sunt 2 lucruri diferite. Pe UVA o problema in concurs era 3 secunde / test si in arhiva orice problema e de 10 secunde. Pe de alta parte la voi sunt punctaje partiale si pe uva nu. Ideea nu e sa dublati timpu ci sa nu dati avantaj unui limbaj fata de altul, eu cu pascalul cred ca am facut algoritmul comisiei si nu intru in timp la stramosi ... Pe de alta parte pascalul citeste mai repede ca c-ul daca nu se folosesc buffere la citire. Ideea e ca daca un propunator face solutia oficiala in limbaju respectiv s-ar putea sa dea involuntar un avantaj acelui limbaj. La problema cutii ideea e sa fie algoritmul cat de cat, pt ca in n^2 o stie face tat prostu ...

[Anonymous]

Omiteti faptul ca sunt de multe ori diferente de timp intre limbaje. De asemenea multe probleme au mai multe solutii de aceeasi complexitate (asimptotica) insa cu constante diferite. Daca de exemplu la o problema exista doua solutii O(N), una de doua ori mai inceata, ar trebui totusi sa ia 100 de puncte si un concurent care face solutia un pic mai inceata si mai lucreaza si in pascal...

De aia probleme gen cutii (la care a trebuit sa optimizez un pic in ca sa intre si inca eram in C) mi se par aberante limitele. E mai logic sa mariti N-ul ca sa se diferentieze mai clar un NlogN de un N^2 si timp lejer pt Nlog^2N (de exemplu de 10 ori mai putine teste cu N de 10 ori mai mare si timp dublu fata de sursa voastra). Iar la aia cu stramosi sa nu intre in timp solutia decat daca inversezi matricea e prea de tot...

Parerea mea e ca atunci cand faci o problema, implementezi mai multe surse, iar limita de timp o dai astfel incat sursa CEA MAI INCEATA care vrei sa ia totusi max sa ruleze in vreo 75% din timp. Btw. exista convertoare din c in pascal si din pascal in c destul de bunicele (necesita doar cateva modificari de mana dupa conversie) deci nu e mare osteneala sa se incerce sursele cu ambele limbaje.
Oricum, in caz de nesiguranta, injuraturile la adresa membrilor familiilor dvs. scad exponential atunci cand limita e prea mare fata de cazul in care e prea mica.

Radu B.

[•silviug]

S-a adus in discutie problema "cutii". Ca propunator al problemei vreau sa dau o justificare a limitelor alese. Sunt 100 de teste in fisierul de intrare cu N = 3500 din urmatoarele motive:

1. Am considerat ca o solutie ce utilizeaza Arbori Indexati Binar cu timp de rulare O(N log^2 N) si memorie N^2 este suficient de dificila pentru concursul nostru. Din aceasta cauza N-ul nu putea fi foarte mare. Totusi diferentele dintre solutia O(N^2) si solutia mea pentru un N asa de mic erau nesemnificative si a trebuit sa introduc mai multe teste in acelasi fisier.

2. Solutia mea ruleaza in 6 sec. Mi s-au parut suficiente 9 secunde mai ales ca solutia O(N^2) implementata in C rula in aproximativ 15 sec.

3. N-ul nu putea fi mai mare de 3500 pentru ca fisierele de intrare deveneau mult prea mari.

Acestea fiind spuse tin sa-i multumesc lui Radu pentru sugestii.

Silviu Ganceanu