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:
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.
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
).
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.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena