infoarena

Aici puteţi discuta despre problema Autobuze (http://infoarena.ro/problema/autobuze).

Cum se rezolva de 100? Eu fac asa pentru 80 de puncte: sortez vectorul a si iau valoarea maxima (fie ea MaxVal). Apoi, pentru fiecare valoare a[j], iau toti multiplii sai <= MaxVal si ii caut binar in vectorul a. Daca am gasit vreun multiplu al lui a[j] la pozitia m, inseamna ca am muchie intre j si m in graful pe care il construiesc. Raspunsul este egal cu numarul de componente conexe din graf, lucru pe care il rezolv cu BFS. Vreo idee pentru 100? Se face altfel sau trebuie un pic optimizata ideea mea?

Vom publica articolul cu solutii in cel mult doua zile (dupa prezentarea/premierea de la Unibuc).

Ideea ta e buna, vezi daca nu cumva reusesti sa inlocuiesti cautarea binara cu ceva mai rapid.

Eu fac cu hash si marchez multiplii pentru a nu-i mai verifica si pe ei si tot 80 iau.

Am incercat cu hash si multimi disjuncte, insa iau 80 de puncte. Care ar fi ideea de 100 sau ce optimizari ar mai trebui sa fac?

*SPOILER ALERT!*

Tii in hash toate numerele din vector cu pozitiile lor cu tot; Pe langa asta mai tii un vector unde marchezi daca o valoare se afla in vector,si inca un vector unde marchezi daca valoarea curenta ai gasit-o prin cea precedenta.Acum iei fiecare numar,si ii vezi multiplii;daca un multiplu se afla in multime il cauti in hash;dupa ce il gasesti faci muchie intre cele 2 pozitii din multime;apoi faci bfs ca sa vezi numarul componentelor conexe.

http://ideone.com/bn388X
Cine ma poate ajuta si pe mine?Am facut cu paduri de multimi disjuncte dar pe 50% din teste iau mle.Nu inteleg de ce,trei vectori micuti si un map....

Incearca sa accesezi un element cu functia map::find()