Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 222 Aladdin  (Citit de 4041 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« : Aprilie 02, 2006, 12:26:35 »

Aici puteţi discuta despre problema Aladdin.
Memorat
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #1 : Aprilie 28, 2006, 18:45:04 »

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

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #2 : Aprilie 28, 2006, 20:48:50 »

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

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : Aprilie 28, 2006, 22:45:39 »

Merge back ... Sad

cum naiba sa mearga backul? :O
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #4 : Aprilie 28, 2006, 23:29:52 »

optimizat  Rolling on the Floor Laughing, 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.
Memorat
nivan
Vizitator
« Răspunde #5 : Aprilie 29, 2006, 00:34:05 »

 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.
Memorat
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #6 : Aprilie 29, 2006, 11:00:39 »

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

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #7 : Aprilie 29, 2006, 11:57:21 »

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 ...
Memorat
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #8 : Aprilie 29, 2006, 12:07:20 »

Aha.....mai bine citesc din revista  Smile
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #9 : Aprilie 29, 2006, 12:31:19 »

optimizat  Rolling on the Floor Laughing, 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.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #10 : Aprilie 29, 2006, 12:38:00 »

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

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #11 : Iulie 06, 2006, 16:50:24 »

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

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
C_Ovidiu
Strain
*

Karma: -37
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #12 : Aprilie 23, 2007, 21:07:17 »

    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 .

Citat
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 ??   Huh
Memorat
florin.elfus
Strain
*

Karma: 109
Deconectat Deconectat

Mesaje: 43



Vezi Profilul
« Răspunde #13 : Martie 17, 2016, 22:48:15 »

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

 Shame on you  Shame on you  Shame on you
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #14 : Martie 18, 2016, 13:10:36 »

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  Smile.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #15 : Martie 18, 2016, 14:18:07 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #16 : Martie 19, 2016, 10:57:20 »

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

Asta era acum 10 ani.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #17 : Septembrie 27, 2018, 22:43:42 »

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  Think Se pare ca evaluatorul verifica sumele si atat  Think
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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