MINCOLOR - Editorial

gaurav25720 · March 17, 2022, 6:08pm

Can anyone tell me the mistake in this code?


public class Solution {
	public static void main (String[] args) 
	{
		Scanner s = new Scanner(System.in);
	    int t=s.nextInt();
	    while(t-->0) {
	    	int n= s.nextInt();
	    	int m= s.nextInt();
	    	int [][] arr= new int [n][m];
	    	int a= s.nextInt()-1;
	    	int b= s.nextInt()-1;
	    	int c= s.nextInt()-1;
	    	int d= s.nextInt()-1;
	    	arr[a][b]= 1;
	    	arr[c][d]= 2;
	    	if((a-c)%2!=(b-d)%2) {
	    		if(a%2==b%2) {
	    			for(int i=0; i<n; i++)
	    				for(int j=0; j<m; j++) {
	    					if((i+j)%2==0) {
	    						arr[i][j]=1;
	    					}
	    					else {
	    						arr[i][j]=2;
	    					}
	    				}
	    		}else {
	    			for(int i=0; i<n; i++)
	    				for(int j=0; j<m; j++) {
	    					if((i+j)%2==0) {
	    						arr[i][j]=2;
	    					}
	    					else {
	    						arr[i][j]=1;
	    					}
	    				}
	    		}
	    	}
	    	else {
	    		if(a-1>=0) {
	    			arr[a-1][b]=4;
	    		}
	    		if(b-1>=0) {
	    			arr[a][b-1]=4;
	    		}
	    		if(a<n-1) {
	    			arr[a+1][b]=4;
	    		}
	    		if(b<m-1) {
	    			arr[a][b+1]=4;
	    		}
	    		if((a-c)%2==(b-d)%2) {
		    		if(a%2!=b%2) {
		    			for(int i=0; i<n; i++)
		    				for(int j=0; j<m; j++) {
		    					if(arr[i][j]!=0) {
		    						continue;
		    					}
		    					if((i+j)%2==0) {
		    						arr[i][j]=1;
		    					}
		    					else {
		    						arr[i][j]=2;
		    					}
		    				}
		    		}else {
		    			for(int i=0; i<n; i++)
		    				for(int j=0; j<m; j++) {
		    					if(arr[i][j]!=0) {
		    						continue;
		    					}
		    					if((i+j)%2==0) {
		    						arr[i][j]=2;
		    					}
		    					else {
		    						arr[i][j]=1;
		    					}
		    				}
		    		}
		    	}
	    	}
	    	for(int i=0; i<n; i++) {
	    		for(int j=0; j<m; j++) {
	    			System.out.print(arr[i][j]+" ");
	    		}
	    		System.out.println();
	    	}
	    }
    }  
```}

kar_shoham · March 17, 2022, 6:08pm

My code failed for the 4th test case.

#include <bits/stdc++.h>

#define lint long long int

using namespace std;

void solve(){

    lint n, m;

    lint x1, y1, x2, y2;

    cin>>n>>m;

    cin>>x1>>y1;

    cin>>x2>>y2;

    x1--, y1--, x2--, y2--;

    // keep an array of size 4 containing all the 4 adj elements

    // 0 if no adj on that side (first check if available or not else error)

    lint ans[n][m]= {0};

    for(int i=0; i<n; i++){

        for(int j=0; j<m; j++) ans[i][j] = 0;

    }

    lint t[4] = {0};

    lint temp;

    lint check[10] = {0};

    ans[x1][y1] = 1;

    ans[x2][y2] = 2;

    for(lint i=0; i<n; i++){

        for(lint j=0; j<m; j++){

            if(i==x1 &&j==y1) continue;

            else if(i==x2 && j==y2) continue;

            else{

                temp = i-1;

                if(temp >= 0){

                    temp = ans[temp][j];

                    if(temp == 0){

                        t[0] = -1;

                    }

                    else{

                        t[0] = temp;

                    }

                }

                else{

                    t[0] = 0;

                }

                temp = i+1;

                if(temp < n){

                    temp = ans[temp][j];

                    if(temp == 0){

                        t[1] = -1;

                    }

                    else{

                        t[1] = temp;

                    }

                }

                else{

                    t[1] = 0;

                }

                temp = j-1;

                if(temp >= 0){

                    temp = ans[i][temp];

                    if(temp == 0){

                        t[2] = -1;

                    }

                    else{

                        t[2] = temp;

                    }

                }

                else{

                    t[2] = 0;

                }

                temp = j+1;

                if(temp < m){

                    temp = ans[i][temp];

                    if(temp == 0){

                        t[3] = -1;

                    }

                    else{

                        t[3] = temp;

                    }

                }

                else{

                    t[3] = 0;

                }

                for(lint k=0; k<4; k++){

                    if(t[k]>0) check[t[k]]=1;

                }

                for(lint k=1; k<10; k++){

                    if(check[k]==0){

                        ans[i][j] = k;

                        break;

                    }

                }

                for(lint k=1; k<10; k++) check[k] = 0;

            }

        }

    }

    for(lint i=0; i<n; i++){

        for(lint j=0; j<m; j++) cout<<ans[i][j]<<" ";

        cout<<endl;

    }

}

int main(){

    int t;

    cin>>t;

    while(t--) solve();

    return 0;

}

kar_shoham · March 17, 2022, 6:08pm

Case 4 failed for me as well.
#include <bits/stdc++.h>

#define lint long long int

using namespace std;

void solve(){

lint n, m;

lint x1, y1, x2, y2;

cin>>n>>m;

cin>>x1>>y1;

cin>>x2>>y2;

x1--, y1--, x2--, y2--;

// keep an array of size 4 containing all the 4 adj elements

// 0 if no adj on that side (first check if available or not else error)

lint ans[n][m]= {0};

for(int i=0; i<n; i++){

    for(int j=0; j<m; j++) ans[i][j] = 0;

}

lint t[4] = {0};

lint temp;

lint check[10] = {0};

ans[x1][y1] = 1;

ans[x2][y2] = 2;

for(lint i=0; i<n; i++){

    for(lint j=0; j<m; j++){

        if(i==x1 &&j==y1) continue;

        else if(i==x2 && j==y2) continue;

        else{

            temp = i-1;

            if(temp >= 0){

                temp = ans[temp][j];

                if(temp == 0){

                    t[0] = -1;

                }

                else{

                    t[0] = temp;

                }

            }

            else{

                t[0] = 0;

            }

            temp = i+1;

            if(temp < n){

                temp = ans[temp][j];

                if(temp == 0){

                    t[1] = -1;

                }

                else{

                    t[1] = temp;

                }

            }

            else{

                t[1] = 0;

            }

            temp = j-1;

            if(temp >= 0){

                temp = ans[i][temp];

                if(temp == 0){

                    t[2] = -1;

                }

                else{

                    t[2] = temp;

                }

            }

            else{

                t[2] = 0;

            }

            temp = j+1;

            if(temp < m){

                temp = ans[i][temp];

                if(temp == 0){

                    t[3] = -1;

                }

                else{

                    t[3] = temp;

                }

            }

            else{

                t[3] = 0;

            }

            for(lint k=0; k<4; k++){

                if(t[k]>0) check[t[k]]=1;

            }

            for(lint k=1; k<10; k++){

                if(check[k]==0){

                    ans[i][j] = k;

                    break;

                }

            }

            for(lint k=1; k<10; k++) check[k] = 0;

        }

    }

}

for(lint i=0; i<n; i++){

    for(lint j=0; j<m; j++) cout<<ans[i][j]<<" ";

    cout<<endl;

}

}

int main(){

int t;

cin>>t;

while(t--) solve();

return 0;

}

i_am_ris0 · March 18, 2022, 9:54am

Even I have checked your code thouroughly and unable to spot a mistake. The logic and output seems fine.

@lavish_adm Please take a look at this

priyanshu_28 · March 18, 2022, 10:28am

yes

suman_18733097 · March 18, 2022, 11:46am

Try this test case:

tyagi_titans · March 18, 2022, 1:57pm

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.
link - CodeChef: Practical coding for everyone

suman_18733097 · March 18, 2022, 2:28pm

tyagi_titans · March 18, 2022, 3:25pm

Thank you

anirudh4 · March 18, 2022, 4:03pm

a dfs solution for the problem

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef tree<long long, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset; 
#define sor(vec) sort(vec.begin(), vec.end())
#define rever(vec) reverse(vec.begin(), vec.end())
#define trav(x , p) for(auto &x : p)
#define ull  unsigned long long
#define MAXN 200005
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<(int)b;i++)
const ll mod =998244353; 
#define dbg(i,j,k)  cout<<"("<<i<<","<<j<<")"<<" "<<k<<" "
#define dbgp(i,j)   cout<<i<<" "<<j<<endl
#define print cout<<"**"<<endl;
 const int inf=1e9+7;
 void vcin(vector<ll> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
 void vcout(vector<ll> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
const ll MOD = 1e9+7;
double eps = 0.0000001;
#define endl "\n";
 //member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
// cout<<"Case #"<<p<<": "<<ans<<endl;

void dfs(int i,int j,vector<vector<bool>>&vis, vector<vector<int>>&grid,int curr)
{
     int n=grid.size();
     int m=grid[0].size();
     if(i<0 || j<0 ||i>=n ||j>=m || vis[i][j])
     return ;
     vis[i][j]=true;
     if(grid[i][j]==0)
     grid[i][j]=curr;
     dfs(i+1,j+1,vis,grid,curr);
     dfs(i-1,j+1,vis,grid,curr);
     dfs(i+1,j-1,vis,grid,curr);
     dfs(i-1,j-1,vis,grid,curr);
}

 void solve()
{
   int n,m;
   cin>>n>>m;
   vector<vector<int>> grid(n,vector<int>(m));
   int x1,y1;
   cin>>x1>>y1;
   int x2,y2;
   cin>>x2>>y2;
   vector<vector<bool>> vis(n,vector<bool>(m,false));
  // vis[x1-1][y1-1]=true;
   vis[x2-1][y2-1]=true;
   dfs(x1-1,y1-1,vis,grid,1);
   vis[x2-1][y2-1]=false;
   dfs(x2-1,y2-1,vis,grid,2);
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<m;j++)
       {
           if(grid[i][j])
           {
               cout<<grid[i][j]<<" ";
           }
           else
           cout<<3<<" ";
       }
       cout<<endl;
   }
}
 



int32_t main()  

{ 
  
  
	 ios::sync_with_stdio(false);
     std::cin.tie(nullptr);
     
        int  t;
         cin>>t;
         
       
   
         while(t--)
         {
           solve();
         }
      
 
}

smaf · March 18, 2022, 7:05pm

Why I am getting Runtime error ( SIGABRT ) in this code?
What is wrong with this code?

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool isvalid(int n,int m,int x,int y){
    return (x<n && x>=0 && y<m && y>=0);
}
int32_t main(){
    int caseno;cin>>caseno;
    while(caseno--){
        int n,m;cin>>n>>m;
        vector<vector<int> >vec(n,vector<int>(m));
        vector<vector<int> > vec2(n,vector<int>(m));
        int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;
        x1--;x2--;y1--;y2--;
        for(int i=0;i<n;i++){
            int ft=1,f2=2;
            if(i%2==0){
                swap(ft,f2);
            }
            for(int j=0;j<m;j++){
                if(j%2==0){
                    vec[i][j]=ft;
                }
                else{
                    vec[i][j]=f2;
                }
            }
        }
        for(int i=0;i<n;i++){
            int ft=1,f2=2;
            if(i%2!=0){
                swap(ft,f2);
            }
            for(int j=0;j<m;j++){
                if(j%2==0){
                    vec2[i][j]=ft;
                }
                else{
                    vec2[i][j]=f2;
                }
            }
        }
        if(vec[x1][y1]==1 && vec[x2][y2]==2){
            for(auto it: vec){
                for(auto i: it){
                    cout<<i<<" ";
                }
                cout<<"\n";
            }
        }
        else if(vec2[x1][y1]==1 && vec2[x2][y2]==2){
            for(auto it: vec2){
                for(auto i: it){
                    cout<<i<<" ";
                }
                cout<<"\n";
            }
        }
        else{
            vec[x1][x2]=1;vec[x2][y2]=2;
            for(int i=0;i<4;i++){
                int nx=x1+dx[i];int ny=y1+dy[i];
                if(isvalid(n,m,nx,ny)){
                    vec[nx][ny]=3;
                }
            }
            for(int i=0;i<4;i++){
                int nx=x2+dx[i];int ny=y2+dy[i];
                if(isvalid(n,m,nx,ny)){
                    vec[nx][ny]=3;
                }
            }
            for(auto it: vec){
                for(auto i: it){
                    cout<<i<<" ";
                }
                cout<<"\n";
            }
        }
    }
}

kpchouhan7 · March 19, 2022, 6:20am

Where does my code fail?. It’s working fine on 3/5 test cases.

here’s the code - Code

pandey_adm · March 19, 2022, 12:32pm

Test case :

Output :

2 2 1 2 1 
3 1 2 1 3 
2 3 1 3 2

I have a feeling that little tweaks can make it AC; do reply back after that.

pandey_adm · March 19, 2022, 5:49pm

It fails on this test case :

Output :

2 1 2 1 2 
1 2 1 2 1 
2 1 2 1 2

It didn’t satisfy A[2][2] = 1. This might not be the only mistake.

Also, tell us why should it be right ?

pandey_adm · March 20, 2022, 1:45pm

should be

else 
    {
        k = 3;
        x = 2;
    }

I think you’ll know why. Look at this ACed code.

pandey_adm · March 20, 2022, 1:49pm

Elaborate on that, please. Backtracking is a technique not an algorithm, so it is hard to understand what you mean.

pandey_adm · March 20, 2022, 3:41pm

Replace (a - b) % 2 with (a + b) % 2 to get AC. Check the behaviour of % when first operand is negative.

pandey_adm · March 20, 2022, 3:45pm

All is cool. It was a coding error on his side.

pandey_adm · March 20, 2022, 4:31pm

Thanks for explaining your code, makes it easier.
You are over looking the fact that one of the cells could be 4 (marked by you).

Consider following test case :

@kar_shoham your code is similar and fails on this case.

jatin0308_adm · April 12, 2022, 6:36pm

hey @smaf ,
In your code line number 64 you have written vec[x1][x2] (but it should be vec[x1][y1]) . Rest is all good.