goodcode rectangle - Codeforces

Блог пользователя Mobinteymoori

goodcode rectangle

Автор Mobinteymoori, 11 лет назад, По-английски

i was wondering about writing a question here .... as U know ... describing a question here is a little hard ... if there is a matrix in this question its impossible because when you write a matrix here it shows the whole matrix in one line that is confusing really ! so i decided to put this question as a link here ... because U can C it so better . click here to see the question don't remember to comment :)

math, matrix, implementation

Mobinteymoori
11 лет назад
13

Комментарии (9)

Показать архивные | Написать комментарий?

HolyInq

11 лет назад, # |

Here you can find it

→ Ответить

savinov

11 лет назад, # |

If constraints are 5x5, you can try all variants of submatrix and check is it ok or no. And choose the best one.

→ Ответить

mohelli5

11 лет назад, # |

anybody here does know about how we can prefer ourselves designed questions to the headquarters of this site .. maybe those are good like this question good rectangle and maybe they put these questions in contest . does anybody know about the way we can do this ???? i myself have designed several good questions that are good for contest div 2 .. i wanted to know how we can prefer questions to the headquarters and contest designers ?

→ Ответить

rock_lee

11 лет назад, # ^ |

you may look into the FAQ section.
see question 5 in this LINK -> http://codeforces.com/help

→ Ответить

DemoVersion

11 лет назад, # |

← Rev. 4 →

Optimize enough? I was already seen a problem a bit like this that was called Maximum Rectangle Sum ... In a (m * n)matrix with negative and positive numbers :)

for(y1=0;y1<5;y1++)
 for(x1=0;x1<5;x1++)
  for(y2=y1+1;y2<=5;y2++)
   for(x2=x1+1;x2<=5;x2++)
    {
     if((x2-x1)*(y2-y1)<=maxs)continue;
     for(j=y1;j<y2;j++)
      for(i=x1;i<x2;i++)
        if(!m[j][i])
           break;
       if(j==y2&&i==x2)
          maxs=(x2-x1)*(y2-y1);
    }

→ Ответить

Mobinteymoori

11 лет назад, # |

As savinov said we should check all submatrixs of this matrix and if its all covert with 1 then calculate the surface .... If surface > last surface then last surface =surface . If you do this then last surface variable will be the biggest good code rectangle's surface . Now just print last surface Solution is that easy yeah ?

→ Ответить

DemoVersion

11 лет назад, # ^ |

sure, one small optimization is that if a rectangle has less total point than the last max we could pass it without checking. I'm wondering in the dislikes.

→ Ответить

michal27

11 лет назад, # ^ |

Yeah. For very small matrices like 5 × 5 it is sufficient. Time complexity of this solution is O(r³c³).

But there are several different approaches with complexities O(r²c²), O(rc²) and even O(rc).

→ Ответить

michal27

11 лет назад, # |

+11

When you writtng a blog or comment, you can use Latex as typesetting program. It allowes you to create nice formulas and also matrices. Using it is pretty easy once you get used to it.

You can create matrix like this:

$\text{[math]}$