Coordonatele copacilor au valori intregi din intervalul [0, 2.000.000]

Asta inseamna ca inmultirea coordonatelor ar trebui facuta pe tipuri de date pe 64 de biti (i.e. long long in C/C++), dar sunt multe surse care iau 100 de puncte desi opereaza cu tipuri de date pe 32 de biti. Interesant ca nu este niciun test care sa verifice asta 

Salut.

Am o intrebare legat de problema asta. Am scris o rezolvare care a luat 100p dar nu sunt sigur daca e corecta (uitandu-ma la alte surse care au luat 100, vad ca nu sunt chiar la fel).

Ce mi-am dat seama e ca e usor sa afli ranspunsul la problema daca centrul ("senatul") e fixat. Dar nu stiam cum sa imi aleg centrul respectiv. Dupa ceva timp, am incercat sa il aleg greedily dupa regula "cel cu suma distantelor catre alte noduri minima" pentru ca intuitiv vorbind daca am suma distantelor mica, am mai putin de "minimizat" prin "pavare" ca sa ajung la raspunsul optim.

Solutia a fost acceptata dar nu reusesc sa demonstrez corectitudinea ei. Cum stiu ca nu exista un nod care, desi in prima faza nu are suma distantelor minima, pot sa il "pavez" in asa fel incat sa obtin o solutie mai buna decat a altor noduri? Exista vreun contraxemplu? Ma poate ajuta cineva? Ma tot bate intrebarea asta

O idee "interesanta" pt aceasta problema.

Imparti nodurile de interes random in doua multimi A si B. Faci un BFS pornind simultan din toate nodurile din A iar raspunsul furnizat este cel distanta cea mai scurta catre un nod din B.

Hai sa analizam un pic rezolvarea aceasta. Daca nodurile care dau distanta optima sunt x si y, atunci daca la imparteala noastra random nodurile x si y sunt in multimi diferite, rezultatul furnizat de solutia noastra este chiar raspunsul la problema. Probabilitatea ca x si y sa fie in multimi diferite este evident 1/2. Asadar, algoritmul nostru are probabilitate de esec de 1/2. Cu alte cuvinte, daca repetam algoritmul de P ori, probabilitatea de esec este (1/2)^P. Ca punct de reper, asta inseamna de exemplu ca pentru P = 10, algoritmul esueaza doar o data din 1024 de incercari.

Cum pe infoarena sunt ~10 teste, P=4 sau P=5 ar trebui sa asigure 100 de puncte in majoritatea cazurilor. Eu am trimis cu P=7 to make sure si a intrat
Complexitatea este evident O(P * (M + N)) pentru ca realizam P BFS-uri, dar trebuie tinut cont ca constanta acestui algoritm este in general mai mica decat o rezolvare "normala", asa ca in practica acest algoritm scoate timpi comparabili cu rezolvarea optima.

Este vreo cineva care a luat 100 cu hash-uri?

Am luat eu (raspuns cu 4 ani intarziere )

Din enunt:

Intre oricare doua noduri x si y exista maxim un arc, însă arcele x -> y şi y -> x pot exista simultan.

Insa in testul 5 exista doua arce 60 84 10227 si 60 84 4334 (liniile 84 si 176 din fisierul de intrare) 

Ar trebui micsorata limita de timp. Se poate obtine 100p in NlogN.

Imi explica si mie cineva ceva la aceasta problema va rog?
Am luat 100 de puncte la ea, dar nu prea inteleg de ce functioneaza...

La inceput nu intelegeam de ce trebuiau ajustate costurile de fiecare data cand faci Dijkstra in loc sa le ajustezi o singura data cu Bellman-ul de la inceput, dar apoi mi-am dat seama ca tu vrei costurile minime luand in considerare doar muchiile nesaturate.. dar acum am o alta problema...

Deci prima data cand fac Dijkstra, imi ajustez costurile in functie de vectorul de distante reutnat de Bellman-Ford, ceea ce e ok; dar apoi la fiecare pas, faci un Dijkstra, trimiti fluxul prin drumul de augmentare gasit si apoi la urmatorul Dijkstra ajustez costurile in functie de ce a returnat Dijkstra-ul precedent... problema mea e ca intre Dijkstra-ul curent si cel precedent, graful rezidual nu mai e acelasi.. pentru ca am trimis niste flux prin acel graf. Asta inseamna ca eu imi ajustez costurile pe graful rezidual curent in functie de costurile de pe graful rezidual precedent; asta nu ar trebui sa fie o problema?

After all, tot motivul pt care imi ajustez costurile dupa fiecare Dijkstra e ca sa le am actualizate dupa distantele minime din graful rezidual curent, nu?

https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

Stie cineva care este scopul BFS-ului din primul pas al algoritmului descris aici?.. nu se poate si fara?
Vad ca toata lumea de pe aici a implementat solutia cu lanturi alternate, fara sa se chinuie cu Hopcroft-Karp cu BFS-ul lui de la inceput..

++ to that

Eu deja am inceput sa cred ca infoarena is down for good vazand ca se face o saptmana si problema inca nu s-a rezolvat

Any news on cand isi revine evaluatoru?
E down de vreo 3 zile deja 

Se intampla ceva interesant la problema asta.

Am luat 100 de puncte pe ea dar timpii mei sunt mult mai slabi decat cei obtinuti de alte surse. Adica cel mai prost timp pe care l-am obtinut e de 124 ms, iar altii s-au incadrat in 30-40... problema e de la fluxul meu pe graf neorientat care se misca foarte incet.

Dar partea dubioasa e ca algoritmul meu de flux pe graf orientat (implementat pentru /problem/maxflow), ia timpi foarte buni. Cel mai prost timp pe care il obtin acolo e 8 ms iar din ce vad timpii obtinuti de alte surse se duc undeva la 20-30 ms. Si singura schimbare intre cei doi algoritmi e ca daca am muchia x->y de capacitate C, atunci capacitatea muchiei y->x e tot C (nu 0 asa cum era la graf orientat).

M-am uitat prin alte surse si vad ca majoritatea au tinut o matrice pentru flux si capacitate. Eu nu am facut asa ci le-am tinut minte in listele de adiacenta (mi s-a parut mai eficient din punct de vedere al memoriei si intr-adevar vad ca memory-wise sursa mea sta bine comparativ). Ma gandesc ca poate de asta iau timpi atat de slabi dar then again daca asta e problema de ce iau timpi foarte buni pe graf orientat?

EDIT: surca aici http://www.infoarena.ro/job_detail/1466457?action=view-source
o sa incerc sa fac si eu o implementare cu matrici sa vad daca asta e problema

E vreo optimizare de care ar trebui sa stiu? Ma tot framanta asta 

EDIT2: Am implementat cu matrici si am mai facut niste mici optimizari si am ajung la ~80 ms.. dar e still de doua ori mai mult ca alti timpi. Totusi ramane ciudat faptul ca implementarea initiala tot scoate timpi mai buni pe grafuri orientate; are cineva o explicatie?

Salut !
Imi spune si mie cineva va rog de ce iau 0 puncte  pe sursa asta .. nu e cea mai eficienta ..dar am luat testele la rand si afiseaza bine.

http://www.infoarena.ro/job_detail/1458914?action=view-source

Multumesc anticipat !

Pt problemele din arhiva educationala, fisierele de intrare/iesire sunt valabile pentru download. Pentru problema asta, e poti gasi aici: http://www.infoarena.ro/problema/evaluare?action=attach-list
Ia de acolo un fisier de intrare si vezi ce rezultat obtii pe el.. daca iei 0 puncte, atunci ar trebui sa fie diferit fata de rezultatul din fisierul de iesire .. si asa iti vei putea da seama ce nu merge

In "indicatiile" problemei scrie ca o rezolvare cu set va lua doar 80 de puncte dar eu am trimis cu set si am luat 100  .. si nu m-am chinuit prea mult cu optimizari. Poate ar trebui redusa un pic limita de timp?