114 Muzeu

[•domino]

Aici puteţi discuta despre problema Muzeu.

[•spixie]

cam ce complexitate are Lee pentru o matrice n*n?
n*n cred poate

[•calinux]

O(N*N)  

[•spixie]

si banuiesc ca problema asta nu se face cu Lee nu ?

[cristi8]

si de ce banuiesti tu ca nu se face cu Lee ?

[•spixie]

mi se parea ciudat sa fie 0.1 secunde si sa fac backtracking la 250^250 dar banuiesc ca iterativ ar trebui sa mearga struna

[cristi8]

pai hotaraste-te. lee sau backtracking ?

[•rmikeweb]

Cu un Lee iti merge sigur mai ales ca graful este rar fiecare nod poate avea cel mult 4 muchii.Ai grija numai cum implementezi .

[•mocke]

d c e afisata matricea asa de ciudat?....chestia aia m-a indus in eroare! am crezut ca trebuie sa fac o afisare identica ! uitati-va la coloana cu numere pozitive si observati ca e mai in stanga!  

[Tabara Mihai]

O abordare cu backtracking duce la TLE pe cel putin 90% din teste(cel mai probabil).Problema se face clar cu Lee(cel putin ...pentru nivel de clasa X)..

Acuma incerc sa o fac si eu,deci inca nu prea e normal sa vorbesc.

P.S.Am o intrebare....cati paznici pot fi maxim?

[Tabara Mihai]

Nu mai conteaza numarul de paznici.Am facut-o dar iau numai 60 de puncte>pe restul iau TLE.
Am incercat doua abordari ->

Lee pe o coada si Lee pe doua cozi. Ambele solutii iau 60 de puncte si le-am optimizat la maxim.
Folosesc doar o matrice

Cod:

ok[i][j] pt conditiile de existenta ( '.' -> 1, '#' -> -2 ) si 
b[i][j] - cea dinamica pe care o tot reactualizez cu un lee pentru fiecare paznic.

Binenteles ca aici intra si coada(*respectiv cozile).Ma poate ajuta cineva cu niste idei in plus???(pls..... )

[•tm_radu]

incearca sa faci lee-ul cu mai multe porniri, nu cate una pentru fiecare paznic.....ii mai rapid 

[Tabara Mihai]

incearca sa faci lee-ul cu mai multe porniri, nu cate una pentru fiecare paznic.....ii mai rapid 

  \/A mers asa cum ai zis tu ...cu mai multe plecari ....am luat 100

gata...keep going

[•Dastas]

Mi-ati putea da un sfat in legatura cu pornirile multiple? Nu-mi iese nici cum, si fara nu iau peste 80 orice-as face, se pare...

Eu retin pozitiile paznicilor intr-o structura, pe care o parcurg si fac pe fiecare paznic lee. Cu porniri multiple am incercat sa parcurg structura din 2 in 2 si sa pun in coada paznicul i si i+1 dar abordarea astea mi-a adus o groaza de raspunsuri gresite si sigsegv-uri (si tot 2 TLE-uri...). Sunt pe drumul cel bun, sau trebuie altcumva?

[•sima_cotizo]

Incearca sa bagi in coada asa: intai toti paznicii pe care ii gasesti, o sa ai Q[ p ] primul paznic, Q[ u ] ultimul paznic...
Pe urma ia "while (p<=u)" si expandeaza nodul curent, indiferent de tipul lui (paznic sau nu), in aceeasi coada ... Si daca nu merge in aceeasi coada alocata static, atunci aloca dinamic si sterge toate elemetnele cozii de care nu ai nevoie (adica atunci cand te duci cu p in p->next, il si stergi pe p initial... )...

Eu zic ca asta e cea mai usoara implementare de Lee ..

[•Tabara]

coada alocata static, atunci aloca dinamic si sterge toate elemetnele cozii de care nu ai nevoie (adica atunci cand te duci cu p in p->next, il si stergi pe p initial...
Eu zic ca asta e cea mai usoara implementare de Lee ..

Nu stiu daca e nevoie de alocare dinamica.(  ) Merge si fara, are la dispozitie memorie destula. (  ).Desi, cred ca ar merita sa incerce cum spui tu 

Secretul problemei cred ca era sa bagi in coada Q[p] paznici si sa lasi Lee-ul sa mearga singur. ( tin minte cat m-a enervat TLE-ul si pe mine la problema asta  )

By the way, daca iese asta, merita sa incerci Barbar ( misto problema de tot  )

[•Dastas]

Va multumesc, a iesit!

O sa incerc si cu alocare dinamica. O intrebare in legatura cu asta: am vazut articole si pe site cum ca pointerii ar fi mai inceti. In cazul acesta, nu conteaza? La un concurs de exemplu, cum ar trebui implementata o coada sau stiva, pe vectori sau pe liste?

[•devilkind]

ideea de stergere de care zice sima cotizo poate fi implementata si folosind memorie statica, folosind ori o coada circulara (daca ai ajuns la sfarsit incepi si bagi de la inceput) dar trebuie sa ai grija sa o declari destul de mare in asa fel incat sa nu se suprapuna, sau folosind 2 cozi, una in care ai elementele curente si una in care le bagi pe cele noi, iar cand treci la pasul urmator copii din coada a 2-a in prima coada astfel reduci foarte mult memoria, insa nu prea ai nevoie de astfel de optimizari. (decat pe la un oji unde lucrezi in borland)

[•Dastas]

Ce bine era sa stiu asta la oji... 

Multumesc pentru ajutor

[•IoNu-]

ce matrice ati folosit ca mie imi dau prea multe variabile la 200x200 si primesc doar 40p   

[•Robytzza]

poti folosi destula memorie ,mareste si tu matricea la 255 255 si daca nu ai alte greseli ar trebui sa-ti meagra

[•Florian]

ce matrice ati folosit ca mie imi dau prea multe variabile la 200x200 si primesc doar 40p   

Hint: Fa asa incat un element sa il bagi in coada o singura data. 

[•alexys]

dc nu mai putem vedea sursele problemelor? 

[•Mishu91]

La problema asta nici nu cred ca s-au putut vedea vreodata sursele

[•beyond_k7a]

am si eu o problema, daca ma poate ajuta cineva:
iau doar 30 de pct: 5 incorecte si 2 TLE-uri si chiar nu pricep dc iau incorect.
am memorat pozitile paznicilor si am facut pe fiecare un Lee.

stie cineva care sa fie problema?