Discussion on Hexagonal Grid Challenge

Sort 35 Discussions, By:

5 years ago+ 1 comment

Since, a lot of coders are struggling to visualize the problem, here's an attempt to simplify it. Most of the queries are about valid/invalid testcases. I think the root cause of confusion is that the problem is being understood in "hexagonal frame" while implemented in "rectangular frame".

Let's transform it for better understanding. The 2xN hexagonal grid and 2x1 valid dominoes given in problem statement are as follows:

Direct transformation from hexagon to rectangle gives the following structure :

Now, the upper row can be shifted slightly towards right to give regular rectangular grid :

Notice the corresponding changes in the valid dominoes ! This not only explains validity of testcases but also simplifies the implementation to great extent.

Query : Why is 10 01 accepted but not 01 10 ?

Here's the grid representation of above input :

a) 10                   b) 01
   01                      10

As it can be seen, the first input requires domino with "forward slash /" structure, which is a valid domino (2nd in above pic). Hence, it can be filled. On the other hand, second input requires domino with "backward slash \" structure, which doesn't exist.

8 years ago+ 1 comment

Plz increase constraints simple recursive solution without memoization passed :P

5 years ago+ 0 comments

Does Any Simpler Solution Exist Than This ??:

import java.util.*;

public class Solution {

    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
        int tc=sc.nextInt();
        for(int t=0;t<tc;t++)
        {
            int n=sc.nextInt();
            int[] a=new int[n];
            int[] b=new int[n];
            int[] c=new int[n+n];//to merge both the stream
            String s1=sc.next();
            String s2=sc.next();
            int count=0;
            for(int i=0,j=0;i<n;i++,j+=2)
            {
                if(s1.charAt(i)=='0')
                    a[i]=0;
                else
                    a[i]=1;
                
                if(s2.charAt(i)=='0')
                    b[i]=0;
                else
                    b[i]=1;
                
                if(a[i]==1)
                count++;
                if(b[i]==1)
                count++;
                
  //merging both the stream in alternate fashion 
              c[j]=a[i];
              c[j+1]=b[i];  
           }
  //if No of 1's is Even Then solution May Exist         
 if(count%2==0)
  {
  for(int i=1;i<n+n;i++)
    if(c[i-1]==0 && c[i]==0) //for '--' pattern
       c[i-1]=c[i]=1;
    else if(i!=1 && c[i]==0 && c[i-2]==0) //for '/' pattern 
       c[i-2]=c[i]=1;
            
            int flag=0;
            for(int i=0;i<n+n;i++) //searching for 0 
            {
                if(c[i]==0)
                {
                    flag=1;
                    break;
                }
            }
            
            if(flag==0)
                System.out.println("YES");
            else
                System.out.println("NO"); 
     }
             else
                System.out.println("NO"); 
        }
    }
}

Note that This Can be Optimized further but here no need as n<=10 is given xD

5 years ago+ 1 comment

No DP, No recursion, O(n) solution

static boolean solve(int s, int e) {
    int c = 0;
    for (int i = s; i < e; i++) {
      if ((a[i] == 1 && b[i] == 1) || (i - 1 >= 0 && a[i] == 1 && b[i - 1] == 1)) {
        if (c % 2 != 0)
          return false;
        else
          c = 0;
      }
      if (a[i] != 1)
        c++;
      if (b[i] != 1)
        c++;

    }
    if (c % 2 != 0)
      return false;
    else
      return true;
  }

6 years ago+ 1 comment

The solution was very simple. The problem I had was visualising the problem. It's not two strings/arrays that are one under the other, but a single stream of places in a snake-like arrangement. Once you realize that, the "DP" problem is keeping track of how many spaces and how many blocks there have been. O(n)

Load more conversations