1) Ba da, anul trecut m-am lasat - adica nu m-am mai pregatit, dar n-am zis niciodata ca ma las de tot, ci doar un an
2) Nu radeam de tine, ci de raspunsul lui Domino, care culmea, era gresit....
Si ca sa rezolv si problema, iata si solutia mea:
Pentru testul:
16
2 2 3 2 2 1 2 2 3 3 2 1 1 2 2 1
Vom incerca toate permutarile ciclice sortate, si vom calcula costul fiecareia, pentru a o alege pe cea mai "ieftina". In acest caz, permutarea optima va fi:
2 2 2 2 2 2 2 3 3 3 1 1 1 1 2 2
Primul pas va fi eliminarea din calcul a sticlelor care se afla deja la locul lor, si vom obtine:
0 0 3 0 0 1 0 2 0 0 2 0 0 2 0 1
0 0 2 0 0 2 0 3 0 0 1 0 0 1 0 2
Cu un cost de 20*6 = 120
Diferenta dintre solutia mea si solutia oficiala consta in modul in care se "cupleaza" sticlele (nu e vorba de cuplajul prin flux...).
O metoda ar fi greedy: pentru fiecare sticla care nu e la locul ei, caut cea mai apropiata masa pe care as putea s-o pun - insa aceasta metoda este gresita.
O alta metoda este cea oficiala, insa si aceasta are metoda greedy la baza, motibul pentru care metoda oficiala scoate rezultate diferite fata de gredy, ar fi ordine in care sunt "cuplate" sticlele
Metoda cu care probabil toata lumea va fi de acord cu mine ca este corecta, este cuplajul intr-un graf bipatit, singura problema ar fi insa, ca o astfel de rezolvare nu se incadreaza in timp.
Si in final, ar mai fi rezolvarea la care m-am gandit eu, dar nu numai!, si care se baeaza pe cateva obsevatii de bun simt:
1) Sticlele cu aceeasi valoare se pot trata complet independent, in alte cuvinte, problema se poate reduce la o serie de probleme, in care trebuie sa "cuplam" intre ele, mai multe sticle de aceeasi valoare. Voi exemplifica aici cu valoarea 2:
0 0 0 0 0 0 0 2 0 0 2 0 0 2 0 0
0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 2
2) In acest caz, pentru a obtine cost minim, va trebui sa cuplam primele doua sticle cu primele doua pozitii, si ultima sticla cu ultima pozitie. Mai exact, costurile de deplaseare se pot marca in felul urmator:
0 0 0 0 0 0 0 2 0 0 2 0 0 2 0 0
0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 2
0 0 1 1 1 2 2 1 1 1 0 0 0 0 1 1 - costurile
Daca de exemplu, vom incerca sa cumplam sticlele altfel, vorm obtine mereu un cost mai mare (de ex.: sticla a doua, pe pozitia a 3-a, si apoi greedy)
0 0 0 0 0 0 0 2 0 0 2 0 0 2 0 0
0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 2
0 0 1 1 1 2 2 1 1 1 1 2 2 1 1 1 - costurile
3) Se poate observa clar (sper eu) care este "sursa" costului suplimentar. De aici se contureaza si solutia pe care o propun: dupa primul pas al rezolvarii, fiecare sticla care nu este la locul ei, se "cupleaza" cu prima masa ocupata necorespunzator. Algoritmul se repeta pana la rezolvarea tuturor sticlelor
Sper ca am explicat inteligibil pentru cat mai multa lume...
Si, ca sa rezolv si problema testelor si a evaluatorului, iata ce propun:
1) toate fisierele de intrare sunt corect definite iar eu nu-mi propun sa complic airea problema, asa ca nu vad nici un motiv pentru a le schimba
2) trimit acum spre evaluare sursa mea de 80p, care foloseste metoda explicata mai sus
3) tot ceea ce ar trebui facut pentru a corecta evaluatorul, este sa rulezi sursa de 80p, si sa modifici cele doua out-uri care sunt gresite
4) n-ar fi rau daca in final s-ar reevalua problema, atat in arhiva, cat si la preONI #3
Spor!
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena