infoarena

Runda 3 se desfășoară în intervalul 25 Aprilie - 1 Mai pe situl competiției http://www.fiicompetition.ro/f11/ la secțiunea Algoritmică și Programare http://www.fiicompetition.ro/f11/category/algoritmica/

La problema razboi nu se stie nimic despre numarul de muchii?

A venit cineva cu o intrebare asemanatoare
http://blog.fiicompetition.ro/2011/intrebari-algoritmica-si-programare/
in comentarii
:)

La problema razboi orasele x si y trebuie sa fie diferite? Daca orasul in care se ajunge cel mai repede este chiar orasul x?

La problema razboi, daca avem un nod izolat, raspunsul e
0
0 0
sau
0
0
?

e 0
0 cred ca s-a mai intrebat.

De ce au disparut toate punctajele de la problema safeu? Va fi reevaluata?

De ce la echipa mea nu apare absolut nici o sursa trimisa ca eu am trimis si la razboi si la safeu. Sau evaluat toate sursele?

Am testat sursa la Safeu pe FIECARE TEST si imi da corect, eu iau 40 pct doar pe Impossible, de ce ? As vrea sa-mi dati sursa pe care ati primit-o .... ar trebui facuta o reevaluare la problema Safeu, vad ca nu exista niciun punctaj.
[LE] Am vazut ca o sa se reevalueze  :oops: .

Nelamurire/Contestatie

Am vazut ca s-a reevaluat problema safeu, cu timp 1s in loc 0.1s cat era precizat in enunt.
Se poate spune de ce s-a modificat timpul precizat in cerinta (si inca de 10 ori mai mare) ? Nu mi se pare normal, pentru ca noi am luat 100/200 cu toti timpii sub 0.1s iar altii au luat punctaje mai mari cu timpi de pana la 0,7-0,8s determinati de ineficienta algoritmului si nu de alte cauze. Daca stiam ca timpul este 1s si nu 0,1s am fi abordat altfel problema, probabil si altii s-au ghidat dupa limita de timp precizata in enunt ...

Eu cred ca sunt multi care au luat TLE fiindca au folosit coada din STL, deci nu e vorba de ineficienta algoritmului :). Au marit probabil limita ca sa nu fie prea stransa pentru anumite implementari (ale unui algoritm corect). Ma indoiesc ca a luat cineva 200 cu altceva decat o parcurgere in latime.

Gresit. Eu am luat cu aceeasi parcurgere 200 SUB 0,1 si nu mi se pare corect sa mareasca limita, asa a fost si asa sa fie. Am optimizat programul ca sa intre in 0,1, niste optimizari nu chiar la indemana. As dori daca se poate sa se reduca limita asa cum a fost, poate la 0,12-0,15 sa nu existe neplaceri.

Ar trebui redusa limita. Eu cred ca e exagerata

Ce e 'gresit'? Am zis eu ca era imposibil sa o scoti in 0.1? Am zis doar ca erau multe implementari care nu au reusit sa faca asta desi era vorba de acelasi algoritm.
In general se considera fair-play sa lasi limita mai libera pentru ca implementarile mai neingrijite (dar nu grosolan) sa nu-ti afecteze prea tare punctajul. Atata timp cat nu exista pericolul ca solutiile proaste sa ia mai mult. Ce-i drept ar fi trebuit sa o puna 1 sec de la inceput, dar in fine..

De acord, dar totusi sa o maresti de 10 ori (cu un ordin de marime) mi se pare exagerat .. nici la prima runda cand a fost problema cu citirile cu fluxuri nu s-a marit de atatea ori, desi unii tot nu au luat chiar maxim exclusiv din cauza citirilor. Cu atat mai mult ca unii s-au ghidat dupa timpul din enunt in abordare, una e sa stii ca ai 0.1 si alta 1

Corect. Sunt si eu deacord daca s-a pus initial 0,1s sa se faca verificarile pe 0,1s si nu pe 1s.

Eu zic ca limita 0,2 ar fi suficienta, poate prea suficienta. Nu stiu daca sunteti de acord cu mine, dar nu am muncit degeaba la sursa s-o optimizez si acum sa aflu ca intra lejer in 1 sec.  [-X

@Simoiu: Cu toate astea, ai luat punctaj maxim asa ca frustrarile tale nu cred ca isi au rostul.

Stiu, dar nu e corect, adica daca am facut ceva sa fie corect pana la capat :P.

Eu cred ca ar trebui date limitele mai largi de la bun inceput. Un concurs cu limite de timp atat de stranse nu va fi foarte popular, mai ales in randul studentilor.

In cazul de fata cred ca ar trebui sa ia maxim cei care au stiut rezolva problema si nu doar cei care au facut niste amarate de optimizari. :) Desigur, eu tin cu echipa mea si nu ma intereseaza atat de mult capra celorlalti. :P
:horsy:

Asta e alta discutie, eventual o sugestie pt problemele urmatoare .. dar daca problema asta a fost data pe 0.1s ar trebui sa ramana asa sau eventual sa fie trecuta pe 0.2s pentru a se accepta si alte solutii destul de bune, dar nu pe un timp de 10 ori mai mare.

Adica noi chiar ne-am ghidat dupa timpul din enunt si ne-am generat teste mari pentru a ne testa timpul .. daca stiam ca se va testa cu 1s poate trimiteam o alta sursa, de-aia nu mi se pare corect sa se schimbe timpul.

Daca sunt asa de "amarate" optimizarile, de ce nu le-ati facut si voi, stiind ca limita este de 0,1 nu de 1 secunda :P ?

Pentru ca credeam ca baietii sunt de treaba si stiu ei ce fac cu limitele astfel incat sa intre si solutiile care nu sunt f optimizate (dupa cum am explicat ca mi se pare normal si se practica la acm , topcoder , etc ). Si se pare ca asta si vroiau, dar nu au estimat bine :) Mai lasa optimizarile alea ca nu e ca si cum ai plecat 5 ani la ucenicie in Tibet ca sa inveti sa le faci :P no offence . Cred ca daca pur si simplu alocai coada static mergea mult mai bine.

Am inteles, v-ati agitat mai mult decat altii care au acum si ei maxim. Sunteti seriosi si asta e admirabil. Dar organizatorii vor sa atraga lume si nu prea o sa se intample asta daca se ia 20 de puncte cu o idee corecta, dar implementata mai lejer. Robert, tu oricum esti pe locul 2 sau ceva de genul, chiar mori de cine e in spatele tau ? Las' ca demonstrati voi mai incolo ca sunteti smecheri :D.

Da, nu zic nu, dar nu e pb. de coada dinamica, e pb. de 1 matrice tridimensionala in plus, si cod consistent in plus :P. Alta data trebuie sa te gandesti la orice, si se putea spune 1 secunda de la inceput, sa nu ne chinuim degeaba. Eu ce castig daca m-am chinuit, fata de voi care ati facut sursa .... asa cum e ea ?
P.S. Ar trebuie sa vorbeasca cineva din afara concursului, nu cineva care are 200 puncte pe 1 secunda si evident ca ii ciuda daca i se ia din punctaj :P.

Dude, ti le dau pe toate , really  :) Eu intotdeauna am sustinut limite mai libere. Si atunci cand a fost problema cu streamurile, desi citisem cu scanf si eram ok.
Eu nu trag cu disperare de punctaje, daca te uiti pe unele concursuri ai sa vezi ca am luat 0 fiindca mi-a fost sila sa trimit bruturile daca nu m-am prins de 100 la nicio problema :) (cred ca am pierdut si finala la algo pe o chestie ca asta).
Asa ca nu ma acuza de chestii de genul asta , ca vorbesti prostii.
Cu asta am terminat.

Cheers

De ce sa te acuz, am zis doar ca trebuie sa faca limitele de la inceput mai stranse, ca sa stim pe viitor, si ca ar fi corect sa se evalueze pe 0,1 secunde, la Nationala nu s-ar fi intamplat asa ceva :P.

Cred ca ar fi mai util in locul comentariilor pe forum sa incerci sa aprofundezi materia pentru anul viitor, poate o sa vezi cum e si la baraj la nationala...

O sa incerc, la nationala m-am incurcat urat de tot :P, nu vreau sa mai vorbesc despre asta.

Altii in schimb nu sunt pe locul 2 si au gandit si testat problema astfel incat sa obtina cat mai multe rezultate corecte in 0,1s, nestiind ca in final se va evalua pe 1s. Oricum nu e vorba de loc, punctaj, sau dinastea, e vorba de principiu, nu stiu ce e asa greu de inteles ca pe unii oameni ii intereseaza si ca principiul sa fie corect si nu doar rezultatul personal cum au recunoscut unii.

Nici la reevaluarea cauzata de citirea din fluxuri nu mi s-a parut normal sa fie marit timpul stabilit in enunt, chiar daca a fost macar partial in favoarea mea. Lumea care a patit-o din cauza fluxurilor a atras atentia ca pe viitor sa fie mai atenti organizatorii si sa anunte ce compilator folosesc si au propus eventual sa fie updatat compilatorul si sa se reevalueze asa, nu sa se mareasca timpul. Si oricum timpul nu s-a marit de 10 ori, daca se marea de 10 ori noi de exemplu luam maxim atunci. In schimb acum nu inteleg de ce s-a marit chiar de 10 ori. Totusi, e ca si cum ai mari de la 1s la 10s sau de la 2s la 20s, mi se pare exagerat.

In legatura cu ideea ca ar trebui sa fie limite mai lejere fiindca sunt si studenti (obisnuiti cu alt gen de concursuri) sunt partial de acord, insa e offtopic. E o sugestie pt alte probleme si nu justifica marirea de 10 ori a timpului de la o problema dupa ce sursele au fost deja trimise pe enuntul initial.

Asa putem reevalua problema cu timp 0.25s , cu timp 0,5s , cu timp 0,75s, cu timp 1s si obtinem punctaje si clasamente diferite. Pe ce criteriu s-a ales 1s si nu alta valoare? Cred ca reevaluarea ar trebui sa se faca pt 0,1s daca asa a fost enuntul, mai ales ca timpul tine exclusiv de eficienta algoritmului si nu sunt motive de gen citire cum a fost la prima runda (si repet, si atunci timpul nu a fost marit de 10 ori)

Eu nu inteleg o chestie daca ma puteti ajuta. Eu am trimis sursa si la safeu si la razboi si mi sa evaluat doar cea de la safeu iar cea de la razboi nici macar nu apare ca problema trimisa desi eu va ASIGUR ca am trimis-o la fel de bine ca si cea de la safeu. Poate sa imi explice cineva ce sar fi putut intampla ca sa am si eu pacea sufleteasca ca sunt nervos rau pe chestia asta(am pierdut 400 de puncte la f11 asta pana acuma).

PS: singura chestie e ca sursa de la razboi am retrimis-o in ultimul minut. Atata si nu cred ca poate avea legatura cu asta.

Uita-te la surse trimise, la tine in profil, si trimite-mi tot ( adica copiaza numele si data ), poate te pot ajuta :).

1   8   cpp   [AP][Gteam]8.cpp   2011-05-01 23:27:59
2   5   cpp   [AP][Gteam]5.cpp   2011-04-10 23:04:41
3   4   cpp   [AP][Gteam]4.cpp   2011-04-10 23:04:22
4   3   cpp   [AP][Gteam]3.cpp   2011-04-10 23:04:05
5   2   cpp   [AP][Gteam]2.cpp   2011-03-19 14:18:18
6   1   cpp   [AP][Gteam]1.cpp   2011-03-19 14:18:06

Asta imi apare. Imi apare ca nu am trimis sursa razboi desi eu stiu sigur ca am trimis-o si ca mi-a zis ca a fost trimisa cu succes.
Cel mai nasol e ca safeu mi-a luat-o iar razboi NU.

Sper ca in ultimul minut ala in care am trimis la razboi sa nu fi fost ceva gen: mi-a sters ultima sursa de la razboi si cand sa o inlocuiasca cu cea noua s-a terminat concursul.

Cred ca ai trimis un ultimul minut, pana s-o incarcat pe site o trecut timpul limita, si s-or sters amandoua. Mi s-a intamplat si mie pe infoarena ceva gen :P.
[LE] Sau .... poate ca ceasul de la tine de la PC ( sau unde te-ai uitat ) era mai in urma decat cel de pe F11 :-?

Cred ca e prima varianta ca daca era a doua nu as mai fi putut trimite nimic in plus. Da trist, trist rau. Cer scuze la echipa. Nu mas fi asteptat la o prostie ca asta.

depune te rog o contestatie la [email protected] cu datele echipei, ca sa avem in record. si investigam cu cei de la IT mai departe cazul tau.

Observ că s-a iscat o discuÈ›ie aprinsă pro-contra reevaluării de 1 secundă. Consider corect să explicăm ce s-a întâmplat. Pe scurt, când am primit arhiva, nu am văzut fiÈ™ierele .ok È™i le-am generat cu sursa oficială. Sursa oficială a generat teste greÈ™ite, ceea ce am observat azi dimineață în urma contestaÈ›iilor (pentru care vă mulÈ›umim), fapt pentru care am realizat ulterior o sursă de la 0 în C++. Deoarece spaÈ›iul stărilor era mare, surse care implementau coada, vectorii diferit (STL, versus de mână) obÈ›ineau punctaje mai mici. Am considerat corectă în principal ideea de rezolvare È™i în secundar super optimizarea - pentru care îi felicit pe băieÈ›i.  :weightlift: Acordarea limitei de 1s/test a fost în avantajul celor care rezolvaseră problema corect, dar au folosit Q.push(x); în loc de Q[++sf] = x; Ne cerem scuze pentru inconvenienÈ›e, în special celor care s-au chinuit să rezolve de 0.1 È™i le urăm succes tuturor în continuare.

MenÈ›ionez că, dacă vreunul dintre voi are de depus o contestaÈ›ie nominală, le primim È™i le rezolvăm după un mail cu numele echipei, problema È™i ...problema la [email protected]

Sursa oficială inițială a prof. Sergiu Corlat (.pas de 0.1 secunde, presupusă a fi greșită) rezolvă problema corect, dar doar în altă versiune de FPC (un concurent ne-a demonstrat cu 2.4.2). În 2.2.2, însă, ea nu prinde unele teste. În orice caz, cea compilată cu 2.4.2 depășește 1 secundă la evaluare pe unele teste. În concluzie, domnul profesor NU a greșit sursa oficială, iar limita de 1s este rezonabilă.

Cred că a fost evident pentru toată lumea că o soluÈ›ie de complexitate (N*M)² nu poate să intre în timpul de 0.1 sec decât dacă este foarte foarte (exagerat de) optimizată (mai ales din cauză că necesită foarte multă memorie). Eu încă sunt mirat că totuÈ™i a reuÈ™it cineva să găsească o astfel de soluÈ›ie. Eu eram mai mult decât sigur că soluÈ›ia "oficială" are o complexitate mai bună.

După părerea mea, dacă se dorea să se lase un timp mai lejer la problemă, se putea face asta în timpul concursului. Cu cel puțin 24h înainte de final. Eventual participanții să fi fost anunțați prin eMail. Nu mi se pare normal să se schimbe regulile unui joc după ce acesta a fost terminat. Nici măcar dacă nu s-ar putea face nicio soluție care să rezolve problema în 0.1 sec. Nu-mi amintesc ca în ultimii ani să se fi schimbat limita de timp sau restricțiile unei probleme la vreun concurs serios, după terminarea acestuia.

Motivele pentru care am mărit timpul cred ca sunt (mai) clare. Ne-am dat seama că sursa oficială, compilată cu 2.2.2, nu lua toate testele abia după contestații, deci runda era terminată. Sursa oficială nu a recurs la optimizările pe care le-au găsit băieții cu 0.1s, deci nu am considerat necesar să păstrăm 0.1s ca să intre obligatoriu cu optimizări. Pe scurt, nu a fost acesta scopul problemei, deși am fi fost bucuroși să ne dăm seama de ea.

Totuși, diferența de la 30p la 200p pentru respectiva optimizare nu se justifică. Complexitatea timp e aceeași. Dacă sursa oficială (compilată cu 2.2.2) rezolva corect testele, rămânea 0.1 și nu era nimic de observat. Dar nu am avut norocul. Aceeași sursă (compilată cu 2.4.2) rezolvă corect, dar depășește 1s pentru câteva! O sursă C++ asemănătoare se încadrează în 1s. Adevărul e la mijloc, așadar 1s este o limită ok din punctul de vedere al surselor oficiale.

Este suspect pentru Cosmin (și nu numai) că nu am păstrat 0.1s - și are și el dreptate! Dacă știam de problemă, o remediam în timpul rundei și (cu mare probabilitate) schimbam atunci tot la 1s. În orice caz, am răspuns cum am considerat mai bine și mai prompt acestor probleme, și în avantajul celor care au rezolvat corect problema, indiferent de abordare, i/o, structuri etc.

Nu am organizat concursul pentru a fi neserios și nici pentru a promova anumiți concurenți selectați de noi. S-ar putea face asta și direct, fără un concurs în care să investim noi timp și resurse. Sunt de acord că unele decizii nu sunt perfecte, dar e imposibil să se întâmple așa ceva. Vom căuta să fim mai atenți la sursele și testele oficiale în următoarele runde.

E bine ca macar acum s-a explicat de ce s-a reevaluat problema cu 1s. Dar partea cu in avantajul celor care au rezolvat problema ar trebui completata cu dar nu si-au dat seama ca nu intra in 0.1s si in dezavantajul celor care au exclus de la inceput solutia de complexita O(n²*m²)  fiindca si-au dat seama ca nu intra in timp (cel putin nu fara niste optimizari pe care nu stiau sa le faca dar nici cei care au primit 200 in urma reevaluarii nu au stiut sa le faca).. Eu consider ca si alte echipe aveau o sansa sa rezolve problema de 200 stiau de la inceput de timpul de 1s insa au avut castig de cauza cei care nici macar nu s-au gandit sau nu si-au dat seama ca solutia lor nu are nicio sansa sa intre in 0.1s.

Toate persoanele care aveau (n*m)² neoptimizat È™tiau că nu vor lua punctajul maxim. Probabil majoritatea se aÈ™teptau la cel mult jumătate din punctajul problemei.
Sincer, eu nu văd care ar fi fost problema dacă o sursă care merge de 10 ori mai prost decât o altă sursă primește un punctaj de 6-7 ori mai mic decât acea sursă. Eu chiar cred că cei care au muncit să rezolve problema conform cerinței din timpul concursului se simt total dezavantajați.

ps: echipa mea nu se numără printre cele dezavantajate !!

Am citit multe discutii in contradictoriu pe tema problemei safeu si marturisesc ca imi plac discutiile in contradictoriu, insa, am imbatranit si stiu ca nu aduc nimic bun. Eu va propun sa incheiem discutia si sa ramanem cu un algoritm dragut. Concret, am sa va prezint optimizările pe care le-au găsit băieții cu 0.1s.

I. Solutia evidenta (pentru mine):
Complexitate timp: O(N*M*N*M)
Complexitate spatiu: O(N*M*N*M)

Se observa ca, deoarece pe tabla exista un singur seif cu Pocalul (X) si un singur spatiu liber (.), indiferent ce secventa de mutari am realiza, vom ajunge intr-o stare care poate fi caracterizata in mod unic prin pozitiile spatiului liber si al seifului.

Astfel, identificam o functie bijectiva intre o stare si multimea [1;N]x[1;M]x[1;N]x[1;M].

In continuare, stiind ca un seif obisnuit (c) si seiful cu Pocalul (X) se pot muta peste spatiul liber (.), putem concluziona ca urmatoarele tranzitii intre stari sunt permise:
1) mutarea spatiului liber (.) peste un vecin, daca vecinul este un safu obisnuit (c)
2) interchimbarea spatiului liber (.) cu seiful cu Pocalul (X), daca acestea sunt vecine

In final, stim ca starea initiala a seifurile se gaseste in fisierul de intrare, iar starea finala este de forma: (1,1,x,y)

Am construit un graf cu N*M*N*M varfuri si cel mult 4*N*M*N*M, in care avem de calculat cel mai scurt drum de la starea initiala la una din starile finale, stiind ca muchiile sunt ponderate egal. Cu o parcurgere in latime obtinem timpul optim pentru rezolvarea acestei probleme.

II. O Solutie interesanta:
Complexitate timp: O(N*M*N*M)
Complexitate spatiu: O(N*M)

Observam (dupa ce descoperim ca sursa anterioara nu intra in 0,1s pentru N = 50, M = 50) ca, in principal, trebuie sa cautam o modalitate prin care sa mutam seiful cu Pocalul (X) de pe o pozitie oarecare, pe o pozitie invecinata. Insa, acest lucru nu se poate face direct. Pe drumul optim, intre doua mutari succesive ale seifului cu Pocalul (X) trebuie sa mutam de cateva ori spatiul liber (.). Mai precis, imediat dupa ce a fost mutat seiful cu Pocalul (X), spatiul liber (.) ocupa unul din vecinii seifului cu Pocalul (X) (pozitia din care a venit), iar inainte sa fie mutat din nou, spatiul liber (.) ocupa un alt vecin (pozitia pe care se va duce).

Astfel, observam ca, daca pentru o pozitie fixata a seifului cu Pocalul (X), vom calcula toate drumurile optime prin care spatiul liber (.) se poate muta din orice pozitie vecina a seifului cu Pocalul (X) in orice alta pozitie vecina a seifului cu Pocalul (X), fara a muta seiful cu Pocalul (X), vom putea reformula problema astfel:

Reducem numarul de stari la multimea [1;N]x[1;M]x[1;4], reprezentand pozitia seifului cu Pocalul (X) si pozitia spatiului liber (.), stiind ca acesta nu poate fi decat vecin seifului cu Pocalul (X).

Observam ca folosind operatia de interschimbare si in baza timpilor de mutare a spatiului liber (.), putem determina tranzitiile dintre stari.

In final, observam ca starea initiala s-ar putea sa nu faca parte din multimea starilor reduse, si trebuie sa calculam distanta de la starea initiala la cele 4 stari similare ale ei, acestea devenind starile initiale din noua problema, iar costul de a plecare din ele este nenul. Starea finala este (1,1,x).

Am construit un graf cu N*M varfuri si cel mult 4*N*M, in care avem de calculat cel mai scurt drum de la una din starile initiale la una din starile finale, stiind ca muchiile sunt ponderate. Cu un algoritm eficient de calcularea a drumului optim, putem realiza acest lucru intr-o complexitate rezonabila.


III. Solutia mai buna (o fi una si mai buna?):
Complexitate timp - cazul mediu: O(N*M)
Complexitate timp - cazul defavorabil: O(N*M*N*M)
Complexitate spatiu: O(N*M*N*M)

Am observat in solutia anterioara aparent mult efort pentru nimic. Dar, solutia anterioara are ceva buna si ceva rau... poate putem sa facem o solutie in care pastram ce e bun si scapam de ce e rau!

Ce e bun: Reduce numarul de stari ale problemei! Era evident ca solutia I nu putea fi optimizata, decat prin reducerea numarului de stari (sau prin artificii in assembler care nu fac obiectul algoritmicii)! Acest lucru vine cu un pret: suntem obligati sa calculam distantele dintre cele 4 stari cu aceeasi pozitie a seifului cu Pocalul (X) - acest lucru trebuie sa-l facem de N*M ori iar o astfel de operatie dureaza O(N*M) timp, deci... nu am rezolvat nimic! Dar, stai! Oare asa sa fie si pe cazul mediu? Nu cumva, pe cazul mediu, mutarea spatiului liber (.) intre pozitiile vecine ale seifului cu Pocalul (X) se face in foarte putini pasi? Si nu cumva si timpul de executie este proportional cu lungimea drumului? BA DA! Evirka! (la 0:30, cand te chinui sa-ti intre problema in 0.1s).

Ce e rau:
1. Graful obtinul la final are muchii ponderate si nu putem folosi parcurgerea in latime;
2. Trebuie sa calculam separat timpii de mutare a spatiului liber (.);
3. Trebuie sa calculam timpii de pornire din starile initiale.

Ce putem face sa scapam de ce e rau?

Putem pastra intacta multimea starilor [1;N]x[1;M]x[1;N]x[1;M] si putem sa o folosim pentru a calcula in ea timpii de mutare a spatiului liber si timpii de pornire din starile initiale! Si putem sa calculam drumul minim in graful ponderat printr-o parcurgere in latime! Cum?

Foarte simplu - ajustam solutia I, folosind doar ceea ce e bun din solutia II:

Parcurgand in latime multimea a starilor ([1;N]x[1;M]x[1;N]x[1;M]), tinem si o structura paralela a multimii starilor reduse ([1;N]x[1;M]x[1;4]), in care marcam starile prin care a trecut parcurgerea in latime. Daca pentru o pozitie a seifului cu Pocalul (X) au fost marcate toate cele 4 stari asociate din multimea starilor reduse, atunci parcurgerea in latime este oprita pentru toate starile cu acea pozitie a Pocalului.

In incheiere:
Eu sunt autorul solutiei propuse si a sursei trimisa spre evaluare si nu o consider o optimizare, ci un alt algoritm, cu un alt grad de complexitate (pe cazul mediu).

Probabil ca voi fi atacat, reprosandumi-se ca atata timp cat cu reduc cazul defavorabil, solutia mea nu este mai buna. Daca intentionati sa ma atacati, atunci va aduc aminte ca cel mai fecvent utilizat algoritm pe scara larga a fost pana nu demult QuickSort, care, in ciuda timpului dezastruos pe cazul defavorabil, a fost preferat HeapSortului, doar pentru ca are o constanta mai mica.

Si eu sunt adeptul timpilor lejeri, iar pozitia lui Mihai Calancea mi se pare cea mai buna:

Considerand ca am inventat o solutie mai buna (dpdv teoretic si nu cu artificii de limbaj), mi se pare ca timpul a fost marit suficient de mult cat sa permita si solutiilor in O(N*M*N*M) sa obtina 200p, ceea ce e incorect pentru solutia mea. Insa, afland ca de fapt a avut loc o greseala in randul comisiei, iar solutia oficiala era tot in O(N*M*N*M), marirea timpului de executie mi se pare decizia corecta!

Cu aceasta ocazie, tin sa multumesc organizatorilor pentru acest concurs, deoarece m-a facut sa-mi dau seama ca inca mai stiu algoritmi! Si le spun si eu sa aiba un pic mai multa grija pe viitor, pentru ca noi, concurentii, putem sa busim si nu ne mai calificam, insa organizatorii, cand gresesc, trebuie sa-i impace pe toti nemultumitii... si... e mai complicat :-ss.

Imi pare rau pentru cei care "s-au fript", facand surse partial gresite, dar care sa intre in timp (vanatorii de puncte :P).

In ceea ce ma priveste, inteleg ca nu suntem la lotul national sau la vreo olimpiada internationala organizata de o tara capabila sa propuna probleme imposibile, astfel ca se mai intampla sa descoperi un algoritm mai bun decat al comisiei, caz in care nu poti decat sa te bucuri! :) Am impartit cu toata lumea solutia mea si sper sa va bucurati de ea, asa cum ma bucur si eu!

Sper ca v-a placut idea mea, pentru ca mie mi-a placut problema!
PS: Daca limita nu era de 0,1s, atunci nu m-as fi gandit la solutiile II si III.