MINCOLOR - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kushagra Goel
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

There is a matrix of size N \times M. Two distinct cells of the matrix (x_1, y_1) and (x_2, y_2) are painted with colors \text{1} and \text{2} respectively.

You have to paint the remaining cells of the matrix such that:

  • No two adjacent cells are painted in same color.
  • Each color is an integer from 1 to 10^9 (both inclusive).
  • The number of distinct colors used is minimum (including \text{1} and \text{2}).

Note:

  1. You cannot repaint the cells (x_1, y_1) and (x_2, y_2).
  2. Two cells are adjacent if they share a common edge. Thus, for a cell (x,y) there are 4 adjacent cells. The adjacent cells are (x, y+1), (x, y-1), (x+1,y), and (x-1,y).

EXPLANATION:

Let us define the parity of a cell (x,y) as the parity of x+y. So, (5 , 1) is an even cell, whereas (4 , 1) is an odd cell. Consider a cell (x,y). Observe that if (x,y) is an even cell, then all the cells adjacent to (x,y) will be odd cells. Similarly, if (x,y) is an odd cell, then all the cells adjacent to (x,y) will be even cells. This property is useful while solving many grid related problems.

Consider the problem when none of the cells were already painted. In that case, we could have painted all the even cells by 1 and all the odd cells by 2. Note that the above coloring satisfies all the required properties.

Now if one of the cell (x, y) was already painted as 1, we could have assigned that color to all the cells having same parity as that of (x, y), and color 2 to the remaining opposite parity cells.

In the above problem, we are given two cells: (x_1, y_1) with color 1, and (x_2, y_2) with color 2. If the parity of both these cells are same, we can assign either color 1 or 2 to all the cells having same parity as these cells, and color 3 to all the remaining cells. We have used 3 distinct colors in this case.
If the parity of both these cells are different, we can assign color 1 to all the cells having same parity as that of (x_1, y_1), and color 2 to all the remaining cells (having same parity as that of (x_2, y_2)). We have used 2 distinct colors in this case.

TIME COMPLEXITY:

O(N \cdot M) for each test case.

SOLUTION:

Editorialist's Solution
#define ll long long
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>
using namespace std ;


void solve()
{
    ll n , m ;
    cin >> n >> m ;

    ll x1 , y1 , x2 , y2 ;
    cin >> x1 >> y1 >> x2 >> y2 ;

    x1-- ; y1-- ; x2-- ; y2-- ; // making the indices 0-based

    ll col[2] ; // col[0]: color on even-sum cells. col[1]: color on odd-sum cells. 

    ll p1 = (x1 + y1)%2 ; // parity of first cell
    ll p2 = (x2 + y2)%2 ; // parity of second cell

    if(p1 == 0 && p2 == 0)
    {
        col[0] = 1 ; // can use either 1 or 2. 
        col[1] = 3 ; // can't use 2 as it is used on an even-sum cell.
    }

    if(p1 == 0 && p2 == 1)
    {
        col[0] = 1 ;
        col[1] = 2 ; // the given colors can be used directly. 
    }

    if(p1 == 1 && p2 == 0)
    {
        col[0] = 2 ;
        col[1] = 1 ; // the given colors can be used directly. 
    }

    if(p1 == 1 && p2 == 1)
    {
        col[0] = 3 ; // can't use 1 or 2 as they are used on an odd-sum cell.
        col[1] = 1 ; // can use either 1 or 2. 
    }

    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < m ; j++)
        {
            if(i == x1 && j == y1)
            {
                cout << 1 << ' ';
                continue ;
            }

            if(i == x2 && j == y2)
            {
                cout << 2 << ' ';
                continue ;
            }

            cout << col[(i+j)%2] << ' ' ;
        }
        cout << '\n' ;
    }
    return ;
}

 
int main()
{   
    
    ll t = 1 ;
    cin >> t ;
    while(t--)
    {
        solve() ;
    }
    
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;
}
7 Likes


void solve(){
   int n,m;
   cin>>n>>m;
   
   vvi gg(n,vi(m,0));

   int x,y;

   for(int i=0;i<2;i++) {cin>>x>>y;  x--; y--; gg[x][y]=i+1;}
   
   for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(gg[i][j]==0){
            set<int> col;
            if(i-1>=0 && gg[i-1][j]) col.ins(gg[i-1][j]);
            if(j-1>=0 && gg[i][j-1]) col.ins(gg[i][j-1]);
            if(i+1<n && gg[i+1][j]) col.ins(gg[i+1][j]);
            if(j+1<m && gg[i][j+1]) col.ins(gg[i][j+1]);
                for(int k=1;k<=200;k++){
                    if(col.count(k)) continue;
                    else{
                        gg[i][j]=k;
                        break;
                    }
                }   
            }
        }
   }
   
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        cout<<gg[i][j]<<" ";
    }
    cout<<"\n";
  }
   
    
return;}

any edge case?

Can someone help me understand what I am missing in this approach?
https://www.codechef.com/viewsolution/60620245

Case 4 seems to be failing with this approach.
In brief, I have initialize empty matrix with 0 and marked the positions for x1,x2,y2,y1. after that I am checking adjacent cells for each index, if any of them has only 1, I am entering 2, only 2, then 1 and if both then 4.

Those who are using brute force method in which we check all four adjcent side are getting WA in one of the test cases that means there is some type of edge case, so I think only correct answer is editors. But still it will be helpfull if anyone can tell us what is edge case.

Whoever is getting wrong answer, try this test case
2 3
2 3
1 3
Many people’s code failed for this one

3 Likes

I passed this testcase perfectly !! Stilling getting WA
here is my solution : Solution: 60661260 | CodeChef
if you run this code and see the output u will easily understand what I am doing.

also, for the testcase provided by you. I m getting following output
2 1 2
1 2 1

try the test case
2 3
2 3
1 3

1 Like

Try this
3 3
3 3
1 3
your code is giving wrong answer for this

try
3 3
3 3
1 3
and
2 3
2 3
1 3

1 Like

thnx a lot, though I myself figured out that my code was wrong for adjusting the neighbor cells of the 2nd cell (provided in input) by colour 3

Still many many thanx for investing ur time time and pointing my mistake correctly.

I really liked this problem as compared to other “easy” problems that I have solved before. Nice problem :slight_smile:

If anyone can provide some test case where my code fails. It passes all the sample test cases as well as for those mentioned in the comments here.
Here is the code.

Can someone please let me know what’s wrong in my code?

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){
		    int n=sc.nextInt();
		    int m=sc.nextInt();
		    int x=sc.nextInt()-1;
		    int y=sc.nextInt()-1;
		    int z=sc.nextInt()-1;
		    int w=sc.nextInt()-1;
		    long a[][]=new long[n][m];
		    a[x][y]=1;
		    a[z][w]=2;
		    int f=0;
		    if((x-y)==(z-w)){f=1;}
		    if(f==0){
		      
		            for(int j=y-1;j>=0;j--){
		                if(a[x][j+1]==1){
		                    a[x][j]=2;
		                }
		                else{
		                    a[x][j]=1;
		                }
		            }
		            for(int j=y+1;j<m;j++){
		                if(a[x][j-1]==1){
		                    a[x][j]=2;
		                }
		                else{
		                    a[x][j]=1;
		                }
		            }
		            for(int j=w-1;j>=0;j--){
		                if(a[z][j+1]==1){
		                    a[z][j]=2;
		                }
		                else{
		                    a[z][j]=1;
		                }
		            }
		            for(int j=w+1;j<m;j++){
		                if(a[z][j-1]==1){
		                    a[z][j]=2;
		                }
		                else{
		                    a[z][j]=1;
		                }
		            }
		            for(int i=z-1;i>=0;i--){
		                if(a[i+1][0]==1){
		                    a[i][0]=2;
		                }
		                else{
		                    a[i][0]=1;
		                }
		            }
		            for(int i=z+1;i<n;i++){
		                if(a[i-1][0]==1){
		                    a[i][0]=2;
		                }
		                else{
		                    a[i][0]=1;
		                }
		            }
		           
		            for(int i=0;i<n;i++){
		                for(int j=1;j<m;j++){
		                    if(a[i][j-1]==1){
		                        a[i][j]=2;
		                    }
		                    else{
		                        a[i][j]=1;
		                    }
		                }
		            }
		            
		       }
		       else{
		           for(int i=y-1;i>=0;i--){
		               if(a[x][i+1]==1){
		                   a[x][i]=3;
		               }
		               else{
		                   a[x][i]=1;
		               }
		           }
		           for(int i=y+1;i<m;i++){
		               if(a[x][i-1]==1){
		                   a[x][i]=3;
		               }
		               else{
		                   a[x][i]=1;
		               }
		           }
		           for(int i=w-1;i>=0;i--){
		               if(a[z][i+1]==2){
		                   a[z][i]=3;
		               }
		               else{
		                   a[z][i]=2;
		               }
		           }
		           for(int i=w+1;i<m;i++){
		               if(a[z][i-1]==2){
		                   a[z][i]=3;
		               }
		               else{
		                   a[z][i]=2;
		               }
		           }
		           
		           for(int i=x-1;i>=0;i--){
		               if(a[i+1][0]==1){
		                   a[i][0]=3;
		               }
		               else{
		                   a[i][0]=1;
		               }
		           }
		           for(int i=x+1;i<n;i++){
		               if(a[i-1][0]==1){
		                   a[i][0]=3;
		               }
		               else{
		                   a[i][0]=1;
		               }
		           }
		          
		           
		          for(int i=0;i<n;i++){
		              for(int j=1;j<m;j++){
		                  if(a[i][j-1]==1){
		                      if(i!=z || j!=w)
		                      { a[i][j]=3;}
		                  }
		                  else if(a[i][j-1]==3){
		                      if(i!=z || j!=w)
		                      { a[i][j]=1;}
		                  }
		              }
		          }
		          
		       }
		       
		       
		            for(int i=0;i<n;i++){
		                for(int j=0;j<m;j++){
		                    System.out.print(Long.toString(a[i][j])+" ");
		                }
		                System.out.println();
		            }
		        
		       
		    }
		    
		}
	}

What is wrong with my code?? I am passing all sample test cases.

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
    int n,m,x1,y1,x2,y2,k,x;
    cin>>n>>m;
    cin>>x1>>y1;
    cin>>x2>>y2;
    if((x1+y1)%2!=(x2+y2)%2)
    {
        if((x1+y1)%2==0)
        {
            k=1;
            x=2;
        }
        else
        {
            k=2;
            x=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                // if(i==x1&&j==y1)
                // {
                //     cout<<"1 ";
                //     swap(k,x);
                //     continue;
                // }
                // if(i==x2&&j==y2)
                // {
                //     cout<<"2 ";
                //     swap(k,x);
                //     continue;
                // }
                cout<<k<<" ";
                swap(k,x);
            }
            if(m%2==0)  swap(k,x);
            cout<<"\n";
        }
    }
    else
    {
        if((x1+y1)%2==0)
        {
            k=1;
            x=3;
        }
        else
        {
            k=2;
            x=3;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i==x1&&j==y1)
                {
                    cout<<"1 ";
                    swap(k,x);
                    continue;
                }
                if(i==x2&&j==y2)
                {
                    cout<<"2 ";
                    swap(k,x);
                    continue;
                }
                cout<<k<<" ";
                swap(k,x);
            }
            if(m%2==0)  swap(k,x);
            cout<<"\n";
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; cin >> t;
    while (t--) 
    {
    solve();
    }

    return 0;
}

I did the exact same and still could not find any test case where the answer would fail.

here can we also use backtracking?

Looks like codechef plagiarism checker is not doing its job once again, I have found a lot so submissions which are identical but they have still gained significant amount of rating to say the least
here are some submissions :
https://www.codechef.com/viewsolution/60638933
https://www.codechef.com/viewsolution/60618641
https://www.codechef.com/viewsolution/60638093

1 Like

if we color the cells like a chessboard(suppose black = 1 and white = 2) but in such a way that (x1,y1) == black always, Then the task becomes very easy
if (x2,y2) != 2 then change (x2,y2+1),(x2,y2−1),(x2+1,y2), and (x2−1,y2) to 3 or whatever not equals to 1 or 2
Now the problem is how to be assured that our coloring will satisfy (x1,y1) == black ‘always’ .Close observation says that we should start coloring by 1 if (y1 % 2 == 0 and x1%2 == 0) or (y1 % 2 != 0 and x1%2 != 0) otherwise we will start by 2.
here’s a sample code in c

    int n,m; scan_i_2(n,m);
    int x1,y1 ; scan_i_2(x1,y1);
    int x2,y2; scan_i_2(x2,y2);
    int array[n+2][m+2] ;
    int start =( (y1 % 2 == 0 and x1%2 == 0) or (y1 % 2 != 0 and x1%2 != 0) )? 1 : 2;
    int temp = start;
    for (int i = 1; i <= n; i++)
    {
        if(start > 2)
            start = 1;
        temp = start;
        for (int x = 1; x <= m; x++)
        {
            array[i][x] = temp ;     
            temp = 3-temp;
        } 
        start++;
    }
    if(array[x2][y2] != 2)
    {
        array[x2][y2] = 2;
        array[x2][y2+1] = 3;
        array[x2][y2-1] = 3;
        array[x2-1][y2] = 3;
        array[x2+1][y2] = 3;
    }

Running plagiarism checks is a time taking process, and it takes us about 15-20 days to reduce the ratings of the cheaters.

1 Like

Got it. Thank you