Mobinteymoori's blog

goodcode rectangle
By Mobinteymoori, 11 years ago, In English

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 :)

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here you can find it

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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);
    }
→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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).

    → Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply