Se pare ca cineva a descoperit o solutie f. rapida la problema asta (nu eu, pt. ca eu am facut cu pre-calculare   - ce sa-i faci? daca razele nu erau numere reale... dar chiar si atunci ar fi mers cu pre-calculare )

Deci, intrebare: Ce complexitate are solutia oficiala?  

Eu am facut-o in O(N^2) - dar nu te baza pe asta... nu o sa gasesti solutia plecand de la complexitate

Voiam doar sa spun (pentru cei care au 90) ca 3*17 < 3*3*3 (sper sa-i fie cuiva utila chestia asta)

Am facut si eu problema asta, si dupa ce am implementat-o prima data, am dat un submit, si am luat 10 .
Asa ca am facut de mana un test, ca sa scap de WA
Acest test ar trebui sa verifice daca trati toate cazurile particulare, dar nu verifica daca lucrati corect pe numere reale!
Asa ca, daca il folositi, aveti grija sa folositi Eps in comparari, unde este cazul
Raspunsul corect este 312.
Sper sa va ajute!

http://www.savefile.com/files/4845550

[edited by svalentin] datele au fost puse intr-un fisier (citeste postul meu de mai jos)

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!

Am si eu o mica problema cu problema asta  

Nu stiu cat ar trebui sa-mi dea pe testul asta:

16
2 2 3 2 2 1 2 2 3 3 2 1 1 2 2 1

Dupa solutia mea, se pare ca in final, se va obtine:

2 2 2 2 2 2 2 3 3 3 1 1 1 1 2 2

Si costul pt. a ajunge la aceasta configuratie este 144 sau 150?

Primul pas, este sa eliminam sticlele cu aleleasi valori, de pe aceleasi pozitii:

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

Bun... apoi, adaugam la solutie 20*6 = 120

Si apoi ne hotaram unde ajunge fiecare sticla...

Sticla a 3-a va ajunge a 8-a (cost 5)
Sticla a 6-a va ajunge a 11-a (cost 5)
Sticla a 8-a va ajunge a 3-a (cost 5)
Sticla a 11-a va ajunge a 6-a (cost 5)
Sticla a 14-a va ajunge a 16-a (cost 2)
Sticla a 16-a va ajunge a 14-a (cost 2)

Facem totalul si obtinem 120+5+5+5+5+2+2 = 144

Si totusi... eu am implementat solutia oficiala, cu care am obtinut 100 de puncte, si imi da 150  

Asa ca... de fapt tie ti se pare ca lui rss1987 i se pare, pentru ca rss1987 are dreptate: atat solutia oficiala cat si doua dintre teste SUNT gresite

S-a gandit cineva ca poate ati gresit la infasuratoarea convexa? (pot exista si puncte coliniare)

Incercati testul asta:
8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0

raspuns: 4

Corect! Imi cer scuze! Am mai modificat ceva, dar parea inofensiv... De unde rezulta ca acolo s-a strecurat bug-ul .

Sper sa nu te superi, dar o sa spun si ce am gresit, ca sa nu mai greseasca si altii    - am pus conditia de cercuri fara puncte comune inaintea celei de cercuri tangente.

My Bad!  

Dupa foarte multe submisii fara nici un rezultat, am modifcat sursa gresit (din punctul meu de vedere), ca sa constat cu stupoare ca evaluatorul imi considera programul corect.  

Asadar, iata modificarea, in conditia pentru cercuri tangente:

corect (dupa mine):
if ((R1+R2)*(R1+R2) == (X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2) || (R1-R2)*(R1-R2) == (X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2))

corect dupa evaluator:
if (abs(R1+R2 - sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2))) <=0.0001 || abs(R1-R2 - sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2))) <= 0.0001 )

Daca ar fi dupa mine, as re-re-corecta problema   . In fine... voi ce parere aveti?