# Hexagonal Grid

### Problem Statement :

```You are given a hexagonal grid consisting of two rows, each row consisting of n cells. The cells of the first row are labelled a1,a2,...,an and the cells of the second row are labelled b1,b2,...,bn.

For example, for n=6:

Grid Shape

(Note that the b is connected with a(i+1).)

Your task is to tile this grid with 2*1 tiles that look like the following:

Orientations

As you can see above, there are three possible orientations in which a tile can be placed.

Your goal is to tile the whole grid such that every cell is covered by a tile, and no two tiles occupy the same cell. To add to the woes, certain cells of the hexagonal grid are blackened. No tile must occupy a blackened cell.

Is it possible to tile the grid?

Here's an example. Suppose we want to tile this grid:

Example Blank

Then we can do the tiling as follows:

Example Tiled

Input Format

The first line contains a single integer t, the number of test cases.

The first line of each test case contains a single integer n denoting the length of the grid.
The second line contains a binary string of length n. The ith character describes whether cell ai is blackened.
The third line contains a binary string of length n. The ith character describes whether cell bi is blackened.
A 0 corresponds to an empty cell and a 1 corresponds to blackened cell.

Constraints
1 <= t <= 100
1 <= n <= 10

Output Format

For each test case, print YES if there exists at least one way to tile the grid, and NO otherwise.```

### Solution :

```                            ```Solution in C :

In C++ :

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

char s[2][13];
int n;
bool can(char s[2][13],int x,int y) {
//printf("x = %d y = %d\n%s\n%s\n",x,y,s[0],s[1]);
if (y >= n) {
return can(s, x + 1, 0);
}
if (x > 1) {
return true;
}
if (s[x][y] == '1') {
return can(s, x, y + 1);
}
if ((y + 1 < n) && (s[x][y + 1] == '0')) {
s[x][y] = s[x][y + 1] = '1';
if (can(s, x, y + 1)) {
return true;
}
s[x][y] = s[x][y + 1] = '0';
}
if (x == 0) {
if (s[1][y] == '0') {
s[0][y] = s[1][y] = '1';
if (can(s, x , y + 1)) {
return true;
}
s[0][y] = s[1][y] = '0';
}
if ((y)  && (s[1][y - 1] == '0')) {
s[0][y] = s[1][y - 1] = '1';
if (can(s, x, y + 1)) {
return true;
}
s[0][y] = s[1][y - 1] = '0';
}
}
return false;
}

int main()  {
int z;
for (scanf("%d",&z);z;--z) {
scanf("%d%s%s",&n,s[0],s[1]);
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += s[0][i] - '1';
sum += s[1][i] - '1';
}
puts((((sum & 1) == 0) && can(s, 0, 0))?"YES":"NO");
}
return 0;
}

In Java :

import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

public class Solution {
StringTokenizer tokenizer;
PrintWriter out;

public void solve() throws IOException {
int T = nextInt();
for (int t = 0; t < T; t++) {
int N = nextInt();
boolean[][] map = new boolean[2][N];
for (int i = 0; i < N; i++) {
map[0][i] = line1.charAt(i) == '1';
map[1][i] = line2.charAt(i) == '1';
}
if (pack(map)) {
out.println("YES");
} else {
out.println("NO");
}
}
}

public boolean pack(boolean[][] map) {
boolean done = true;
for (int i = 0; i < map[0].length; i++) {
if (!map[0][i] || !map[1][i]) {
done = false;
break;
}
}

if (done) return true;

for (int i = 0; i < map[0].length; i++) {
if (!map[0][i]) {
if (!map[1][i]) {
map[0][i] = true;
map[1][i] = true;
done = done || pack(map);
map[0][i] = false;
map[1][i] = false;
}

if (i < map[0].length - 1 && !map[0][i+1]) {
map[0][i] = true;
map[0][i+1] = true;
done = done || pack(map);
map[0][i] = false;
map[0][i+1] = false;
}
break;
}

if (!map[1][i]) {
if (i < map[0].length - 1 && !map[0][i+1]) {
map[1][i] = true;
map[0][i+1] = true;
done = done || pack(map);
map[1][i] = false;
map[0][i+1] = false;
}
if (i < map[0].length - 1 && !map[1][i+1]) {
map[1][i] = true;
map[1][i+1] = true;
done = done || pack(map);
map[1][i] = false;
map[1][i+1] = false;
}
break;
}

}
return done;
}

/**
* @param args
*/
public static void main(String[] args) {
new Solution().run();
}

public void run() {
try {
tokenizer = null;
out = new PrintWriter(System.out);
solve();
out.close();
} catch (Exception e) {
e.printStackTrace();
System.exit(1);
}
}

int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}

long nextLong() throws IOException {
return Long.parseLong(nextToken());
}

double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}

String nextToken() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
}
}

}

In C :

#include <stdio.h>
#include <stdlib.h>
int dp1[4][2]={{0,3},{2,0},{1,2},{0,0}};
int count[4]={2,1,2,1};
int dp2[4][10],table[10];

int main(){
int T,N,i,j;
char str1[11],str2[11];
scanf("%d",&T);
while(T--){
scanf("%d%s%s",&N,str1,str2);
for(i=0;i<N;i++){
table[i]=0;
if(str1[i]-'0')
table[i]+=1;
if(str2[i]-'0')
table[i]+=2;
}
for(i=0;i<4;i++)
for(j=0;j<N;j++)
dp2[i][j]=-1;
solve(table[N-1],N-1);
if(dp2[table[N-1]][N-1])
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
int i;
if(row==0){
else
return;
}
if(row==1){
continue;
{
return;
}
}
return;
}
continue;
return;
}
}
return;
}

In Python3 :

def nextIndex(index):
return [index[0]+index[1], (index[1]+1)%2]
def onBoard(index, board):
return index[0] < len(board[0])
for t in range(int(input())):
n = int(input())
line1 = input()
line2 = input()
board = [line1,line2]
index = [0, 0]
sol = "YES"
while(index[0]<n):
if board[index[1]][index[0]] == "1":
index = nextIndex(index)
continue
index1 = nextIndex(index)
if not onBoard(index1, board):
#print("line 19 index",index1)
sol = "NO"
break
if board[index1[1]][index1[0]] == "0":
#board[index1[1]][index1[0]] = "1"
#board[index[1]][index[0]] = "1"
index = nextIndex(index1)
continue
index2 = nextIndex(index1)
if not onBoard(index2, board):
#print("line 29 index",index2)
sol = "NO"
break
if board[index2[1]][index2[0]] == "0":
#board[index2[1]][index2[0]] = "1"
#board[index[1]][index[0]] = "1"
index = nextIndex(index2)
continue
sol = "NO"
#print("line 37",index, index1, index2)
break

print(sol)```
```

## Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

## Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

## Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

## Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

## Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

## Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr