CHEFPATH - editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Prateek Gupta
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica

DIFFICULTY:

SIMPLE

PREREQUISITES:

Hamiltonian Path, Hamiltonian Cycle

PROBLEM:

Given an NxM maze, find out if there is a path starting at some cell (a,b), passing through all the cells of the maze and then ends in a cell (c,d) which is adjacent to the starting cell (i.e. they have a border in common). Along the path one can move from the current cell only in one of the 4 directions (up, down, left, right).

QUICK EXPLANATION:

Since the ending cell must be adjacent to the starting cell, the found path can be immediately extended one more step, into a cycle which passes through all the cells of the maze. Such a cycle is called a Hamiltonian cycle. Note that in this case it doesn’t matter which is the starting cell.

An NxM maze has a Hamiltonian cycle if and only if:

  • min{N,M}=1 and max{N,M}=2, OR
  • min{N,M}>=2 and at least one of N and M is even.

EXPLANATION:

If N=1 or M=1, and max{N,M}>=3 it is obvious that no Hamiltonian cycle exists in the maze (because the cells at the endpoints only have one neighbor). However, a solution does exist when min{N,M}=1 and max{N,M}=2 (the two cells are adjacent to each other).

Let’s now consider the case min{N,M}>=2 and at least one of N or M is even. Let’s assume now that N is even (if it’s not then M must be even, so we just swap the values of N and M between them). We can start the cycle at the cell (1,1), then move right to (1,M). From there we move down to (2,M) and then left to (2,2). From (2,2) we move down to (3,2), right to (3,M), then down to (4,M) and left to (4,2). We continue this procedure until we reach the cell (N,2). From here we move left to (N,1) and then all the way up to (1,1).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

3 Likes
2

Pls point out the bug in my code.Thanks a lot… #include<stdio.h>
int main()
{
int t,flag;
long long int n,m;
scanf("%d",&t);
while(t–)
{

scanf("%lld %lld",&n,&m);
if(n==1&&m==1)
{
flag=0;
}
else if((n==1&&m==2)||(m==1&&n==2))
{
flag=1;
}
else if((n%2==0) || (m%2==0))
{
flag=1;
}
else
{
flag=0;
}
if(flag)
{
printf(“Yes\n”);
}
else
{
printf(“No\n”);
}

}

return 0;
}

3

Please, Someone tell me what is wrong with my code.#include<iostream> using namespace std; int main(){ int t; cin>>t; while(t--){ long long int n,m; cin>>n>>m; if(n==1){ if(m==2) cout<<"YES"<<endl; else cout<<"NO"<<endl; } else if(m==1){ if(n==2) cout<<"YES"<<endl; else cout<<"NO"<<endl; } else if(n%2!=0&&m%2!=0) cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }

1 Like
4

you are printing “YES” it should be"Yes"…silly one happens:)…

5

Can someone tell me whats wrong with this code?

#include
#include
#include
using namespace std;

int main() {
unsigned long long int t,n,m;
cin>>t;
bool check;
while(t–)
{ check=false;
cin>>n>>m;
if(n%2==0 && m%2==0)
check=true;
else if(n%2==0 || m%2==0)
check=true;
if(n==1 || m==1)
{ long long int sum=(abs)(n-m);

		if(sum>1)
			check=false;
	}
	if(check)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
}
return 0;

}

6

@rohitkoush “Yes” should be printed instead of “YES”, same is the case for “No”.

7

Please have a look on my code and please clear where I did not satisfy the HAMILTONIAN CYCLE’S CONDITION ??.. It would be great if anyone answers it ! .Sorry for the long code , Iam a beginner!
Thanks in advance!
#include
using namespace std;

int main() {
int t,n,m;
cin>>t;
for(int i=0;i<t;i++)
{

cin>>n>>m;
if(n==1 || m==1)
{
if(n==1 && m==1)
{
cout<<“No”<<"\n";
}

                    if(n==1 && m==2)
                    {
                            cout<<"Yes"<<"\n";
                    }
                    
                    
                    if(n==1 && m>2)
                    {
                            cout<<"No"<<"\n";
                    }
                    
                    if(m==1 && n==2)
                    {
                            cout<<"Yes"<<"\n";
                    }
                    
                    if(m==1 && n>2)
                    {
                            cout<<"No";
                    }
            }
            
            
            if(n==2 || m==2)
            
            { 
            	if(m==2 && n==2)
            {
                    cout<<"Yes"<<"\n";
            }
            
            if(n==2 && m>2 )
            {cout<<"Yes"<<"\n";
            }
            
                    if(m==2 && n>2)
                    {cout<<"Yes"<<"\n";
                            
                    }
            
            }
                                   
    if(n>2 && m>2)
    {
            if(n%2!=0 && m%2!=0)
            {
                    cout<<"No"<<"\n";
            }
            
            if(n%2==0 && m%2==0)
            {
                    cout<<"Yes"<<"\n";
            }
            
            if(n%2!=0 && m%2==0)
            {
                    cout<<"Yes"<<"\n";
            }
            
            if(n%2==0 && m%2!=0)
        {
            cout<<"Yes"<<"\n";
        }
    
    }
    }

}

8

hi, can someone help point out the issue with the below code?

InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);

    int tc = Integer.valueOf(br.readLine().trim());
    for(int i=0;i<tc;i++){
        String s[] = br.readLine().split(" ");
        long n = Long.valueOf(s[0].trim());
        long m = Long.valueOf(s[1].trim());

        if((m==1 && n!=2) || (m!=2 && n==1)){
            System.out.println("No");
        }

        if((m==1 && n==2) || (m==2 && n==1)){
            System.out.println("Yes");
        }

        if(m%2 ==1 && n%2==1)
            System.out.println("No");
        else
            System.out.println("Yes");
    }
9

What is Hamiltonian Matching?

10

Can anyone find the failing test case for my program above. It gave WA.
Submission link

11

plz someone tall me what is means of this line plz…

If N=1 or M=1, and max{N,M}>=3

12

@rohit1495

This means that if the matrix is a row matrix (one row and number of columns > 2)

[1 1 … 1]

or a column matrix (one column and number of rows > 2)

[

1

1

.

.

.

1

]

13

@ravichandrae, try n = 6, m = 1.

14

@tihor14, try running your code locally. It prints 2 answers for each case.

15

Hello @prateekg603

" assert(n >= 1 && n <= 1000000000000000000LL); " Why is this included when we know for sure that the input lies in this range?

Thanks & Regards
Amaresh

16

What is wrong with my code? i am getting wrong answer, even though offline execution shows my code is correct

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String args[]) {
	try
	{
		int numberOfTestCase;
		Scanner input= new Scanner(System.in);
		numberOfTestCase=Integer.parseInt(input.nextLine());
		for(int loop=1;loop<=numberOfTestCase;loop++)
		{
			int row,column;
			row=Integer.parseInt(input.next());
			column=Integer.parseInt(input.next());
			if(row%2!=0&&column%2!=0)
			{
				if((row==1&&column==1))
				{
					System.out.println("Yes");
				}
				else
					System.out.println("No");
			}
			else
			{
				if((row==1&&column!=2)||(column==1&&row!=2))
					System.out.println("No");
				else
					System.out.println("Yes");
			}
		}
		input.close();
	}
	catch(Exception e)
	{
		return;
	}
}
}
17

Why will be the answer or 3 3 be No

18

Why will be the answer for 3 3 be No

19

for the case n=1 and m>2, flag should be zero. Similarly the opposite case.

1 Like
20

gotcha!its accepted now.thanks@lickecs for your effort.

1 Like