1013 Dreptunghiuri2

[•stef2n]

Aici puteti discuta despre problema Dreptunghiuri2.

[•gabipurcaru]

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

[•mathboy]

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

[•ssergiuss]

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

[•mathboy]

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.

[•darkseeker]

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

[•alexandru92]

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

[•Bogdan_tmm]

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

[•ssergiuss]

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.

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

[•thesilverhand13]

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!

[•gabitzish1]

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!

Cod:

0 0 0 0 0 0
0 1 0 0 0 0
0 0 1 1 1 0
0 0 1 0 1 0
0 0 1 1 1 0
0 0 0 0 0 0

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 .

[•andunhill]

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

Va exista cel puţin o zonă dreptunghiulară în matrice.

[•gabitzish1]

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.

[•thesilverhand13]

Asa ,acum am inteles.Multumesc pentru lamuriri!

[•NicuCJ]

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

[•danalex97]

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.

[•NicuCJ]

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

[•hi5all]

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!

[•mathboy]

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