Centrale Nucleare

[•freak93]

Aici se pot pune întrebări legate de problema Centrale Nucleare de la concursului AGM 2016.

[•SebiSebi]

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

[•AGMinformatica]

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 . 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.

[•SebiSebi]

Ok.  Se pot da niÈ™te hinturi in legatura cu cele 2 solutii? 

[•AGMinformatica]

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.