@cosmin: Solutia oficiala era cu cautari ternare . Acolo nu spuneau nimic de reducerea la varfuri.

Am sa incerc sa formulez si eu o solutie la problema asta.  

Am intalnit problema cu varfurile triunghiului aleatoare si suma 2MA + MB + MC trebuia sa fie minima.
Problema a fost la o regionala prin Asia in 2009 parca si se rezolva cu doua cautari ternare ceea ce
duce la complexitatea log(n)^2.

Am sa explic putin solutia de mai sus cu aplicatie in problema noastra.
De ce merge cautarea ternara? Fie M = (x, y). Functia f(x,y) = 2MA + MB + MC este o functie
convexa pentru y fixat si x variabil. Astfel pentru triunghiul dreptunghic de mai sus, daca vrem
sa maximizam f, tragem concluzia ca M nu poate fi decat pe marginea triunghiului.

Cazurile in care M este pe AB sau AC sunt similare. In ambele cazuri e clar ca este eficient ca M
sa fie cat mai departe de A, cu alte cuvinte coincide cu B sau C.
Cazul in care M este este pe BC nu este mult mai diferit. Oriunde s-ar afla M pe BC, valuarea lui
f(x, y) - 2*MA este egala cu BC. De aici tragem concluzia ca problema noastra s-a redus la a gasi
M pe BC astfel incat 2*MA sa fie maxim. Astfel ajungem la solutia M = C si anume f(x, y) = 13.


[Moderator] In general e corect ce zici. Dar nu ai nevoie de cautare ternara. Daca ne uitam pe o latura a triunghiului acolo tot o functie convexa ai, deci singurele locuri unde poate fi maximul sunt la capetele laturii. Deci e suficient sa te uiti la varfuri ca sa rezolvi problema.

Sper ca nu am povestit prostii mai sus

Salutare,

Daca citeste vreun admin postul asta, il rog sa se uite putin peste problema asta. Zice memory limit exceeded cu nici o variabila declarata

mda..  ai dreptate cu 1 2.. Ar fi mai bine sa schimbam testele dupa ideea ta, asa ar deveni si enuntul mai clar, nu ar mai fi interpretabil. O sa incerc cat pot de repede [eu am bacu acum  ] sa modific in sursa mea. Trimite-mi te rog si implementarea ta. Am acelasi id ca pe arena si pe yahoo. Mersi

m-am mai uitat si eu peste sursa Bogdan... e intr-adevar putin ciudat.  Eu am considerat chiar ce ai presupus tu mai sus, un cuvant dispare  daca termin literele din el. Am folosit restrictia lor exact la calcularea costului.
Nu ar trebui totusi pe exemplul AAA sa dea 1 3 (cu presupunerea ca nu avem cuvinte vide). Cu o mutare cuplezi A-urile din mijloc si cu inca 2 mutari le duci la primul A. Sper sa nu gresesc.

salutare... am  si eu o intrebare.. am rezolvat problema cu algoritmul miller - rabin si ptr 7 baze iau 80 cu TLE, ptr 6 baze  90 cu TLE si ptr 5 baze deja 70 cu TLE si incorect  bazele le generez aleator cu o functie random, nu e totusi ceva mai optim ? mersi

salut! daca am fost eu destul de atent cred ca este o greseala in exemplul de la problema.. nu ar trebui un operator binar in expresia ~a~b&~c&~d intre "~a" si "~b"... probabil & pentru a da exemplul... mersi

Am si eu o mica incurcatura la problema asta ... eu lucrez pe pascal si iau tle pe ult 3 teste... am scris sursa in cpp(unde nu ma prea descurc) si ia wa pe ult 6 teste...ideea de rezolvare e strict aceeasi...dar pe c am observat ca la teste mari depaseste tipul...
eu a declarat long long...e altceva mai tare sau ce ar trebui sa fac? mersi