If we think of a matrix as a chessboard, then all white and all black cells can be filled independently. I picked the following pattern to fill, let's say white cell (dots represent black cells):

. 1 . 2 . 1 . 2
3 . 4 . 3 . 4 . 
. 2 . 1 . 2 . 1 
4 . 3 . 4 . 3 .

The same pattern can be used for black cells (leading to the same solution as in editorial), or it can reflected along vertical axis and then used in black cells (leading to the same solution as @l_returns), or it can be shifted, rotated, etc. and then used in black cells.

My Pattern is the best, I guess. And it is

:-->

1 2 3 4 1 2...

1 2 3 4 1 2....

1 2 3 4 1 2....

1 2 3 4 1 2....

Easiest one too!:)

What I did was I followed a greedy approach. Just check the neighbors and find the mex. However I found it didn't work for some cases like (5,5). So I pre-processed for 50,50 and kept it. Now I just took a submatrix from it and filled for any n,m (except min(n,m) <=2 where greedy is used).

I did

  1 1 2 2  
  3 3 4 4  
  2 2 1 1   
  4 4 3 3

I used a backtracking search for this. The trick to making it work is the direction to search in. The obvious approach is something like this:

1 2 3 4 5 6
7 8 9 . . .

This is too slow because if the grid is wide, you have to search an extremely large number of possibilities before you discover that a given value of $k$ is impossible. I searched like this.

1 3 6 . . .
2 5 9 . . .
4 8 . . . .
7 . . . . .

This way, if a given value of $k$ is impossible, the search is confined to a corner and takes very little time. And if $k=4$ and the grid is large, it tends to settle into a tileable pattern and repeats it without having to backtrack.

i don't still understand what's wrong is in my code

include<bits stdc++.h="">

using namespace std; int main() { int i,j,k,l=0,n,m,t,c=0,d=0,max=0,h; cin>>t; for(k=1;k<=t;++k) { cin>>n>>m; max=0; int a[n+1][m+1]; l=1; h=3; if(n==2&&m>=3) { for(i=1;i<=m;++i) { if(i%6==1||i%6==2) h=1; else if(i%6==3||i%6==4) h=2; else h=3; a[1][i]=h; } a[2][1]=2; for(i=2;i<=m;++i) { if(i%6==2||i%6==3) h=3; else if(i%6==4||i%6==5) h=1; else h=2; a[2][i]=h; } max=3;

    }
    else if(m==2)
    {
        for(i=1;i<=n;++i)
        {
            if(i%3==1)
            h=1;
            else if(i%3==2)
            h=2;
            else
            h=3;
            for(j=1;j<=m;++j)
            {
               a[i][j]=h; 
               if(max<a[i][j])
               max=a[i][j];
            }
        }
    }
    else if(m==1)
    {
        for(i=1;i<=n;++i)
       { if(i%6==1||i%6==2)
            h=1;
            else if(i%6==3||i%6==4)
            h=2;
            else
            h=3;
            a[i][1]=h;
           if(max<a[i][1])
               max=a[i][1];
       }

    }
    else 
   { for(i=1;i<=n;++i)
    {   
        if(i%4==1)
        {
            l=1;
            c=0;
            for(j=1;j<=m;++j)
        {
            a[i][j]=l;
            c++;
            if(a[i][j]>max)
            max=a[i][j];
            if(c==2)
            {
                if(a[i][j-1]==1)
                 l=2;
                 else
                 l=1;
                 c=0;
            }
        }}
        else if(i%4==2)
        {
            h=3;
            d=0;
            for(j=1;j<=m;++j)
        {
            a[i][j]=h;
            d++;
            if(a[i][j]>max)
            max=a[i][j];
            if(d==2)
            {
                if(a[i][j-1]==3)
                 h=4;
                 else
                 h=3;
                 d=0;
            }
        }
        }
        else if(i%4==3)
        {
            l=2;
            c=0;
              for(j=1;j<=m;++j)
        {
            a[i][j]=l;
            c++;
            if(a[i][j]>max)
            max=a[i][j];
            if(c==2)
            {
                if(a[i][j-1]==1)
                 l=2;
                 else
                 l=1;
                 c=0;
            }
        }
        }
        else
        {
            h=4;
            d=0;
             for(j=1;j<=m;++j)
        {
            a[i][j]=h;
            d++;
            if(a[i][j]>max)
            max=a[i][j];
            if(d==2)
            {
                if(a[i][j-1]==3)
                 h=4;
                 else
                 h=3;
                 d=0;
            }
        }
        }
    }}

        cout<<max<<"\n";
        for(i=1;i<=n;++i)
        {
            for(j=1;j<=m;++j)
            {
                cout<<a[i][j]<<" ";
            }
            cout<<"\n";
        }

    }

}

I just simply generated a 50*50 matrix using the condition i.e., pigeonhole principle and for special cases I just written code manually. Refer to my code which I simply generated the matrix.

https://www.codechef.com/viewsolution/22456375

@jaggu1999 thanks for code ,but i don't understand how my solution is wrong here is the link i am fraustrated now, link; https://www.codechef.com/viewsolution/22481898

We all know that a number can have at most 4 neighbors, and no two neighbor can be the same so k=4 at max. Now for the pattern I applied the following sequence: 1 2 3 4 1 2 3 4.... 1 2 3 4 1 2 3 4.... 3 4 1 2 3 4 1 2.... 3 4 1 2 3 4 1 2.... 1 2 3 4 1 2 3 4.... and so on. Link to my solution: https://www.codechef.com/viewsolution/22373862

@sdssudhu, I used similar greedy appraoch to fill the table.

So I pre-processed for 50,50 and kept it. Now I just took a submatrix from it and filled for any n,m

Can you elaborate on this part? like how're are you using the submatrix?

Thanks.

@killerx

all you have to do is check n<m if(n<m) you van print the sub matrix as it is other wise you have to print it swapping m and n and print it correctly. eg

1. 1 1 2 ...
2. 2 3 3.....
3. ......

if n<m and say n=2 and m=3 you can print the above submatrix but if n=3 and m=2 you have to print

1. 1 2
2. 1 3
3. 2 3

hope you unerstand now.

@sdssudh @jaggu1999 Can anyone find a case for which my code is giving wrong output? Thanks. I also have used an approach like @sdssudh,

Link: https://www.codechef.com/viewsolution/22482748

I have found the mex for each position, and filled that at a[i][j], also for some cases like for 5*5 matrix, it was giving k=5, then I computed the solution of 50 cross 50 matrix, and printed out the submatrix.

@lakshitf Try

1
2 2

https://www.codechef.com/viewsolution/22505362 can anyone tell me what's wrong in this code?

@shristi_raj Try\

2
3 2
6 7

@petch Sorry I put the wrong code here, my submission is : https://www.codechef.com/viewsolution/22482748

Please help me to find the wrong test case.

@lakshitf

1
2 5

Your output is

4
1 1 2 2 1
2 3 3 4 1

But you can use actually use at most 3 numbers:

3
1 2 3 1 2 
1 2 3 1 2

Please can someone suggest me what's wrong in my code? I am not getting where am i going wrong.

https://www.codechef.com/viewsolution/22517943

this is my sample input and output: input:

8
1 1
1 2
2 1
2 2
2 3
3 2
3 3
3 4

output:

1
1
1
1 1
1
1
1
2
1 1
2 2
3
1 2 3
1 2 3
3
1 1
2 2
3 3
4
1 1 2
3 3 4
2 2 1
4
1 1 2 2
3 3 4 4
2 2 1 1