Hexagonal Grid
Hexagonal Grid
+ 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 is10 01
accepted but not01 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.
+ 1 comment Plz increase constraints simple recursive solution without memoization passed :P
+ 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
+ 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; }
+ 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)
Sort 35 Discussions, By:
Please Login in order to post a comment