You are not logged in. Please login at www.codechef.com to post your questions!

×

DIFNEIGH - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Evgeniy Artemov
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Pigeonhole principle, Constructive algorithms and Case-based Analysis.

PROBLEM:

Given two integers $N$ and $M$, find out any matrix with $N$ rows and $M$ columns using as less distinct numbers as possible, such that for all cell, all values of neighbors of that cell are pairwise distinct.

SUPER QUICK EXPLANATION

  • In all cases, it can be seen that if $K$ is the maximum number of neighbors for any cell, It is not possible to have any valid table using less than $K$ distinct numbers due to Pigeonhole principle.
  • Turns out, it is always possible to make a valid table using $K$ numbers. One possible construction is noticing that ith position in the row should have values different than (i-2)th position and (i+2)th position in the same row. Same goes for columns. Constructions exist based on this condition only.

EXPLANATION

Considering a $N*M$ table, we can see that if the maximum number of neighbors any cell has in a table is $K$, there cannot exist any valid table using less than $K$ distinct values. The reason is, that if we take $K$ values out of distinct $ < K$ values, It is guaranteed to have at least one value occurring more than once, which means that the values of neighbors of that particular cell are not pairwise distinct. Hence, the table is invalid. Refer Pigeonhole principle for proof.

Thus, we need to find a way to fill the table using $K$ values.

General case

In general case where we have $K = 4$, occurs when both $N, M \geq 3$.

Here, in every row or column, we need the first element to differ from the third element in the row, the second element should differ from the fourth element, the third element should differ from the fifth element and so on. If we choose the fifth element to be the same as the first element, it shall make no difference.

It is recommended to try a few ways to fill a $4*4$ table and then trying to extend it either way.

Here, it is possible to have different constructions than the one mentioned here, so feel free to share yours.

One possible way to fill a $4*4$ table is

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

Now, it can be easily seen, that we can just keep appending rows and columns without causing any conflict for any cell, thus efficiently generating our table.

View Content

Special cases

Assuming $N \leq M$. Values $N$ and $M$ can be swapped if otherwise.

  • If $N$ equals one. Here, if $M \leq 2$ each cell has at most one neighbor, and thus, we can just assign 1 to both cells. If $M > 2$, we need the first element to differ from third, second from fourth and so on. So, we can just assign the first four values as 1 1 2 2 and from the fifth element, ith value is assigned same value as (i-4)th element.

  • If $N$ equals two. Here too, if $M == 2$, valid table exist with $K = 2$. Otherwise, we need at least three distinct values. A simple construction being ith element in both rows being assigned as (i-3)th element, first three elements being 1 2 3.

This covers all cases where $K < 4$. All other case have $N, M \geq 3$ which implies $K == 4$ as seen above.

Time Complexity

Time complexity is $O(N*M)$ per test case.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 14 Jan, 16:05

taran_1407's gravatar image

6★taran_1407
3.9k2791
accept rate: 22%

edited 14 Jan, 19:34

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 14 Jan, 23:58

shoom's gravatar image

6★shoom
2434
accept rate: 25%

This was exactly my thought process to come to the pattern. Nice!!

(15 Jan, 00:08) vijju123 ♦♦4★

yeah same here...

(15 Jan, 00:17) l_returns5★
Answer is hidden as author is suspended. Click here to view.

answered 14 Jan, 23:17

karangreat234's gravatar image

4★karangreat234
(suspended)
accept rate: 0%

4

I think it is...
1 2 3 4 1 2...
1 2 3 4 1 2...
3 4 1 2 3 4...
3 4 1 2 3 4...

(14 Jan, 23:30) l_returns5★

oh yea, I forgot : D

(14 Jan, 23:41) karangreat2344★
1

Yes, this pattern rocks :)

(15 Jan, 00:06) vijju123 ♦♦4★

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

link

answered 14 Jan, 21:05

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

I did

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

answered 14 Jan, 21:55

l_returns's gravatar image

5★l_returns
1.4k19
accept rate: 24%

edited 14 Jan, 21:56

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.

link

answered 14 Jan, 21:08

bad_jim's gravatar image

5★bad_jim
1515
accept rate: 25%

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";
        }

    }

}

link

answered 14 Jan, 23:10

agentproton's gravatar image

3★agentproton
1
accept rate: 0%

Please give ONLY submission link and remove this code.

(15 Jan, 00:07) vijju123 ♦♦4★

For testcase $n = 6$, $m = 1$ you are using three different numbers, although two numbers are sufficient:

1
1
2
2
1
1
(15 Jan, 17:06) eartemov5★

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

link

answered 14 Jan, 23:13

jaggu1999's gravatar image

3★jaggu1999
11
accept rate: 0%

@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

link

answered 14 Jan, 23:31

agentproton's gravatar image

3★agentproton
1
accept rate: 0%

@agentproton try
1
5 1

(15 Jan, 21:43) eobardthawne3★

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

link

answered 15 Jan, 09:28

akash19jain's gravatar image

4★akash19jain
726
accept rate: 12%

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

link

answered 15 Jan, 15:59

killerx's gravatar image

3★killerx
1
accept rate: 0%

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

link

answered 15 Jan, 16:20

portgas_d_raf's gravatar image

3★portgas_d_raf
11
accept rate: 0%

edited 15 Jan, 16:23

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

link

answered 15 Jan, 19:28

lakshitf's gravatar image

3★lakshitf
01
accept rate: 0%

edited 16 Jan, 20:10

@lakshitf Try

1
2 2
link

answered 15 Jan, 20:20

petch's gravatar image

4★petch
181
accept rate: 14%

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

link

answered 16 Jan, 02:02

shristi_raj's gravatar image

4★shristi_raj
0
accept rate: 0%

@shristi_raj Try\

2
3 2
6 7
link

answered 16 Jan, 06:35

petch's gravatar image

4★petch
181
accept rate: 14%

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

link

answered 16 Jan, 20:09

lakshitf's gravatar image

3★lakshitf
01
accept rate: 0%

@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
link

answered 17 Jan, 07:28

petch's gravatar image

4★petch
181
accept rate: 14%

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
link

answered 17 Jan, 17:15

officialnitish's gravatar image

2★officialnitish
11
accept rate: 0%

edited 17 Jan, 17:58

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,668
×649
×202
×109
×51
×30
×11

question asked: 14 Jan, 16:05

question was seen: 2,879 times

last updated: 17 Jan, 17:58