infoarena

Aici puteti discuta despre problema Dreptunghiuri2 (http://infoarena.ro/problema/dreptunghiuri2).

... grafuri? eu am luat 100 cu un divide et impera

Problema admite si o solutie care consta intr-o parcurgere in latime / adancime a matricei.

Testele sunt aceleasi ca si la ONI? Nu-mi dau seama de ce pe testele de la ONI iau 100p si aici 90p  #-o.

Da, numai ca ultimul test e de fapt primul test, penultimul e ultimul si tot asa. Cu alte cuvinte, testele sunt aceleasi  :)
LE: Am testat sursa ta si pe testul pe care iei wa raspunsul tau este 250 249 2, cand ar trebui sa fie 251 250 2.

imi da killed by signal 11 SIGSEGV...am inteles k aceasta eroare o da in momentul in kre accesez o zona de memorie nealocata sau cand aloc prea multa memorie...folosesc o matrice de tip boolean si 4 variabile de tip int.imi poate zice cineva de ce primesc eroare?.am incercat si sursele oficiale de la ONI si primesc aceeasi eroare

Poate depasesti limitele matricii, adica poate acesezi C[ 1020 ][ 1020 ] desi ai declarat matricea de mai putin ? Nu pot zice sigur daca nu vad codul :)
Fa un debug ;)

Poate gresesc eu la implementare dar facand asa:
Pentru fiecare dreptunghi parcurg toata zona din interiorul acestuia(O(n*m) n,m dimensiunile dreptunghiului curent) si cand dau de 1 repet procedeul(recursiv). Solutia asta pare a avea o complexitate O(n!*m!) si iau 100 cu ea.
In schimb daca pentru fiecare dreptunghi umplu portiunea cu zerouri si cand intalnesc un 1 repet procedeul pentru dreptunghiul mai mic(deci la dreptunghiul mare nu mai parcurg zona din interiorul dreptunghiurilor mai mici) iau 90 cu TLE.
Nu prea inteleg de ce :D

Mersi Dragos  :) ! Cred ca mi-am dat seama ce greseam...

Propun modificarea enuntului de la 8 la 4 directii,deoarece este necesara numai parcurgerea pe una din directiile nord,sud,est,vest!Daca vreun moderator crede ca este incorecta afirmatia mea,rog stergerea postului!

observi ca in exemplul de mai sus pozitia (2, 2) este vecina cu dreptunghiul cu coltul stanga-sus in (3, 3) pe una din directiile pe care tu vrei sa le elimini?
Enuntul e corect .

Gabriel, testul tau este gresit deoarece nu ai nici un dreptunghi. 

Nu am postat un test valid, ci un exemplu de dreptunghi care are un vecin pe directia nord-vest, directie pe care Eduard ar fi vrut sa o elimine din enunt.
Cred ca se vede ca exista un dreptunghi cu coltul stanga-sus in pozitia (3, 3) si cu latimea si lungimea 3.

Asa ,acum am inteles.Multumesc pentru lamuriri!

Iau TLE pe testul 9, desi pe toate celelalte teste nu depasesc 200 ms. E ceva capcana la 9 ?:)

Mie testul 9 imi ia cat testul 5 ( 168 ms ) , dar probabil e cel mai mare test. Daca nu ai incercat sa parsezi , parseaza. Daca nu , sigur complexitatea ta e buna daca restul intrau , deci gandeste-te la cazuri particulare pentru care tu faci pasi inutili.

Am rezolvat pana la urma inlocuind 2 functii recursive facute degeaba (aflam cu ele lungimile laturilor unui dreptunghi) cu 2 while-uri. Mersi pentru raspunsul prompt :D

As avea si eu o intrebare. Iau doar 90 de puncte si am Killed by signal 11 pe testul 5. Nu prea stiu de ce.
Folosesc o matrice de tip short si inca vreo 6 variabile. Daca ma puteti ajuta cu testul 5 sau sa imi dati vreo explicatie. Merci mult! :D

Incearca sa faci fill-ul iterativ, simuland recursivitatea cu ajutorul unei stive sau fii sigur ca nu iesi vreodata din limitele matricei.