222 Aladdin

[ditzone]

Aici puteţi discuta despre problema Aladdin.

[•tm_radu]

okei....are cineva vreo idee la problema asta? ca io nu-mi dau seama.....

[•Cosmin]

Merge back ... , frumos se face in O(n*m) transformand problema in una de 2sat si poti sa citesti in ginfo 16/1 exact cum.

[•wefgef]

Merge back ...

cum naiba sa mearga backul? :O

[•Cosmin]

optimizat  , just kidding ... , dar daca te gandesti putin fixand cateva patratele duce la fortarea valorilor din alte patratele din aproape in aproape si astfel iti poti da destul de devreme seama daca mergi pe o solutie gresita.

[nivan]

 O metoda mai inceata ca back'u ar fi sa completezi cu random matricea ( 0 sau 1). Si daca nu respecta conditiile refaci procedeul, pana se respecta toate conditiile.

[•tm_radu]

Imi poti spune te rog, pe larg, cum s-ar face in O(n*m), ca nu am numarul acela din Ginfo.....

[•Cosmin]

E cam mult de explicat, ideea e ca daca fixezi valorile de pe prima linie si prima coloana, atunci restul valorilor din matrice sunt determinate. Notand aceste valori cu variabile obtii un sistem de inecuatii, din care fiecare inecuatie are doua variabile. Cum variabilele pot lua doar valori 1 sau 0, o sa vezi din forma inecuatiilor ca ele se pot transforma in propozitii logice a doua variabile. Astfel problema sa redus la una a satisfabilitatii unei formule logice in forma 2CNF. Si pentru acest tip de formule logice exista un algoritm care determina o solutie daca aceasta exista in O(V + P) unde V e numarul de variabile ale expresiei si P e numarul de propozitii logice. In gazeta e explicat mult mai pe larg si cu mai multe exemple de aplicatii ...

[•tm_radu]

Aha.....mai bine citesc din revista 

[•wefgef]

optimizat  , just kidding ... , dar daca te gandesti putin fixand cateva patratele duce la fortarea valorilor din alte patratele din aproape in aproape si astfel iti poti da destul de devreme seama daca mergi pe o solutie gresita.

exact asta era si ideea lui ciucu, dar am zis ca nu merge ca e prea mare matricea.

[•tm_radu]

depinde si cum calculezi celelalte valori....generzit cu back prima linie si prima coloana si dup-aia parcurgi intai linia urmatoare si apoi coloana urmatoare ca sa determini valorile.
de exemplu, calulezi intai valorile de pe linia 2, apoi coloana 2, apoi linia 3.....si asa mai departe, si daca gasesti ca solutia ii gresita, continui back-u....ar trebui sa iasa, daca ii si back-u optimizat un pic....

[•tm_radu]

mi-ati putea spune unde pot gasi mai multe despre formule logice in forma 2CNF? am incercat si pe google da n-am gasit mare lucru...

[•C_Ovidiu]

    Mda , ma chinui de o gramada de timp la pb asta . Am gasit intre timp ceva pe net de 2CNF .
 Dar nu prea vad cum pot sa reduc pb asta la 2CNF .

E cam mult de explicat, ideea e ca daca fixezi valorile de pe prima linie si prima coloana, atunci restul valorilor din matrice sunt determinate. Notand aceste valori cu variabile obtii un sistem de inecuatii, din care fiecare inecuatie are doua variabile. Cum variabilele pot lua doar valori 1 sau 0, o sa vezi din forma inecuatiilor ca ele se pot transforma in propozitii logice a doua variabile. Astfel problema sa redus la una a satisfabilitatii unei formule logice in forma 2CNF. Si pentru acest tip de formule logice exista un algoritm care determina o solutie daca aceasta exista in O(V + P) unde V e numarul de variabile ale expresiei si P e numarul de propozitii logice. In gazeta e explicat mult mai pe larg si cu mai multe exemple de aplicatii ...

  Imi poate explica cineva si mie cum se poate obtine   un sistem de inecuatii cu doua  variabile ??   

[•florin.elfus]

http://acm.sgu.ru/problem.php?contest=0&problem=307

    

[•klamathix]

Vei fi surprins, dar dacă e să cauți puțin pe google: http://petr-mitrichev.blogspot.com/2009/02/remembering-petr-mitrichev-contest-1.html.

Petr a dat problema asta în August 2006 la Petrozavodsk. Iar după cum vezi, la noi primul comentariu este în Aprilie 2006. S-or fi inspirat oamenii din acelaÈ™i paper, no harm done  .

[•wefgef]

Da, Cosmin a propus problema inaintea lui Petr. Doar ca pe infoarena testele sunt slabe si intra si solutii incorecte.

[•Cosmin]

this is awsome. Elfus esti foarte vigilent. Spune-i lui Petr ca fura probleme

Asta era acum 10 ani.

[•SebiSebi]

Am impresia ca evaluatorul nu verifica daca numerele afisate in fisierul de iesire sunt 0 sau 1. Eu am o sursa care afiseaza numere nu neaparat 0 sau 1 (am pus assert si pe toate testele crapa cu SIGNAL 6). Daca scot assert-ul si afisez numere astfel incat sumele sunt satisfacute iau 100p  Se pare ca evaluatorul verifica sumele si atat