Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Centrale Nucleare  (Citit de 2162 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« : Martie 26, 2016, 08:57:04 »

Aici se pot pune întrebări legate de problema Centrale Nucleare de la concursului AGM 2016.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #1 : Martie 27, 2016, 00:11:14 »

Se poate mai putin decat N^2*log(10^6)? Am implemenat asa (cautare binara + 2SAT) si am luat TLE.
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #2 : Martie 27, 2016, 08:09:24 »

Se poate mai putin decat N^2*log(10^6)? Am implemenat asa (cautare binara + 2SAT) si am luat TLE.

Si solutia noastra de N^2*log(10^6) a luat TLE Smile. Se poate si in complexitati mai bune de atat. Avem doua solutii: una in O(N log(10 ^ 6) log^2(N)) si una in O(N log(10^6) log(N) sqrt(N)). Prima obtine pe testele noastre timpi de ~2s, in timp ce a doua, surpirnzator, ~0.3s.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #3 : Martie 27, 2016, 11:11:39 »

Ok.  Smile Se pot da niște hinturi in legatura cu cele 2 solutii?  Smile
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #4 : Martie 27, 2016, 12:00:24 »

Rotim planul cu 45 de grade. Vrem sa determinam muchiile 2-SAT-ului. Acum, in afara de muchiile inputului, celelalte muchii din 2 SAT dandu-se un nod se pot gasi uitandu-ne intr-un patrat centrat in acel nod (determinat de punctul corespunzator si numarul cautat binar). Trebuie sa gasim rapid primul punct nevizitat dintr-un patrat dat, ceea ce se poate face cu un AINT si in fiecare nod sa tinem set-uri sau AIB-uri, sau cu SQRT decomposition.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines