SnackDown Online Pre-elimination round A

It’s about the Is It a Snake problem asked in the contest.

My Code:

public static void dfs(int i, int x ){
	         
	          
	         
	          
	           while(true){
	        	   V[x][i]=true;
	        	   int in = x^1;
	        	
	        	   if(!V[in][i] && A[in].charAt(i)=='#') x=in;
	        	   else if(i+1<n && A[x].charAt(i+1)=='#') i++;
	        	   else break;
	           }
	         
	        
	    
}

Calling this function and checking if path exist.

for(int i=0;i<A.length;i++){
		
		  if(A[0].charAt(i)=='#'){
			  V = new boolean[2][n];
			  dfs(i,0);
			  boolean Good = true;
			  for(int j=0;j<n;j++)
				  if(A[0].charAt(j)=='#' && !V[0][j]) Good=false;
				  else if(A[1].charAt(j)=='#' && !V[1][j]) Good=false;
			  
			  if(Good) G=true;
			 
			  if(A[1].charAt(i)!='#') break;
			  
			  V = new boolean[2][n];
			  dfs(i,1);
			   Good = true;
			  for(int j=0;j<n;j++)
				  if(A[0].charAt(j)=='#' && !V[0][j]) Good=false;
				  else if(A[1].charAt(j)=='#' && !V[1][j]) Good=false;
			
			  if(Good) G=true;
			  
			  
			  
			  
			break;  
			
		  }  else if(A[1].charAt(i)=='#'){
			  V = new boolean[2][n];
			  dfs(i,1);
			  boolean Good = true;
			  for(int j=0;j<n;j++)
				  if(A[0].charAt(j)=='#' && !V[0][j]) Good=false;
				  else if(A[1].charAt(j)=='#' && !V[1][j]) Good=false;
			  
			  if(Good) G=true;
			  
			  break;
		  }
	}
	
	
	System.out.println(G?"yes":"no");

What’s wrong here ?

Its not just the connected components you need to look for if you are doing so. One of the example test cases given in the problem defy this idea. Have a look at it once. If you still have doubts you can post it here ! Cheers :slight_smile:

My approach was to traverse the rows of the plates twice.

Once by starting form the first occurrence of ‘#’ in the first row. And then once again from the first occurrence of ‘#’ in the second row. This will take n+n traversal which is O(n) complexity.

We traverse the plate in the following fashion:
Suppose we started from the ith position of first row, i.e the ith column of first row has the first occurrence of ‘#’ in that row. Now for every position j (i<=j<=n) we see if there’s a ‘#’ at the jth position of other row (i,e if we are at jth column of first row we check the jth column of second row), if yes then we move to other row. Else we stay at the same row. While moving we keep count of the total ‘#’ encountered on the path. If this count is equal to the total number of ‘#’ on the plate then the legend is true and we print ‘yes’.Else we again traverse from the first occurrence of ‘#’ in the second row in the same fashion and again check if this count = total count of the ‘#’.

Time Complexity : O(n).
My solution: https://www.codechef.com/viewsolution/13822184

1 Like