Блог пользователя 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 :)

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here you can find it

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

→ Ответить
»
11 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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);
    }
→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    But there are several different approaches with complexities O(r2c2), O(rc2) and even O(rc).

    → Ответить
»
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:

with this simple code \begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} enclosed in dollar signs $.

You can find more informations about matrices and other formulas in latex here.

→ Ответить