487 Imagine

[•DITzoneC]

Aici puteţi discuta despre problema Imagine.

[•airineiv]

Pentru rezolvarea acestei probleme am folosit QuadTree pentru reprezentarea binara a imaginii, si totusi iau numai 50 de puncte deoarece imi da memory exced la testele 9 si 10 si time limit exced la testele 6, 7 si 8 . Eu aloc dinamic cu new si delete cele doua arrayuri pentru reprezentarea codificata si respectiv codul operatiilor, cate 10000000 caractere pentru fiecare. Pentru operatii am folosit functii recursive pe quad tree. Poate voi primi un sfat util aici pe forum, in incercarea mea de a obtine maximul de puncte la aceasta problema.

[•devilkind]

pai nush dkak aceasta iti poate aduce 100, poate da nush. Dar gandestete ca ai 10 mil de caractere acolo, asta inseamna ca dak am reprezenta imaginea ca o matrice am avea cam 5 mil de elemente (scazand parantezele) iar pe quad tree la fiecare operatie faci cam 5 mil de operatii (ptr ca trebuie sa le rotesti fiecare cadran, dupa ce ai rotit un cadran te duci recursiv si pe cele 4 cadrane din el, dak au culori diferite) si ai cam 10 mil de operatii dak tin eu bine minte ceea ce nu prea cred ca intra. Nush e solutia oficiala sa fie pe aceeasi idee dar cu niste smenuri pe acolo.

[•bogdan2412]

Poti sa ai o matrice 2^2000000 x 2^2000000 daca ai cazu: ((...(((aann)aaa)aaa)....
Evident ca nu o sa intre in timp 2 mil * 10 mil. 

E de ajuns sa simulezi operatiile pe o matrice 2x2 si sa aplici doar o operatie finala pe matricea initiala.. cum faci asta sa intre in timp / memorie nush

[•adrianradulea]

Poate sa imi dea cineva un exemplu care sa imi pot da seama unde gresesc ? Toate raspunsurile pe exemplele mele sunt corecte si totusi iau numai 10 puncte 
Multumesc anticipat !

[•devilkind]

dak ne spui si cum faci poate o sa iti dam.

[•airineiv]

In arborele pe care vreau sa il construiesc un nod are un pointer la right brother (daca nodul e nod intermediar, atunci right brother e chiar primul fiu) si 8 biti impachetati cate doi pentru fiecare dintre fii pentru a desemna daca fii sunt frunze si daca sunt frunze retinand culoarea. In descrierea solutiei scrie ca arborele se construieste cu ajutorul unei stive. Poate sa imi dea cineva o idee, cum s-ar acest arbore pornind de la expresia imaginii, cu ajutorul unei stive? Ca nu am reusit

[•Marius]

Se pot efectua mai multe operatii asupra unei imagini, cum ar fi SDOIV ? Daca da, cum sunt separate operatiile intre mai multi fii ?

[•DITzoneC]

In exemplu nu se efectueaza mai multe operatii ( DOI ) ?
Nu inteleg exact intrebarea. Operatiile sunt facute asupra intregii imagini nu stiu la ce te referi prin fii.

[•Marius]

Eu am crezut ca punand o '(' voi merge intr-un cadran asupra caruia pot aplica alte operatii separat de intreaga imagine. Deci operatiile sunt asupra intregii imagini, nu se intra in nici un cadran ?
Imi cer scuze pentru acei "fii", am scris pe forum direct cum gandeam. Fii sunt cele patru cadrane ale imaginii, sau alte subcadrane alte altui cadran samd.

[•DITzoneC]

Da. Operatiile se efectueaza asupra intregii imagini.