|
Titlul: Centrale Nucleare Scris de: Adrian Budau din Martie 26, 2016, 08:57:04 Aici se pot pune întrebări legate de problema Centrale Nucleare (http://www.infoarena.ro/problema/centrale) de la concursului AGM 2016 (http://www.infoarena.ro/agm2016).
Titlul: Răspuns: Centrale Nucleare Scris de: Pirtoaca George Sebastian din 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.
Titlul: Răspuns: Centrale Nucleare Scris de: AGMInformatica din 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 :). 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. Titlul: Răspuns: Centrale Nucleare Scris de: Pirtoaca George Sebastian din Martie 27, 2016, 11:11:39 Ok. :) Se pot da niște hinturi in legatura cu cele 2 solutii? :)
Titlul: Răspuns: Centrale Nucleare Scris de: AGMInformatica din 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.
|