In this post, we will solve Gridland Provinces HackerRank Solution. This problem (Gridland Provinces) is a part of HackerRank Problem Solving series.
Solution – Gridland Provinces – HackerRank Solution
C++
#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <functional>
#include <string>
#include <cstring>
#include <cstdint>
using namespace std;
int gNPaths = 0;
const unsigned int kHashSize = 4096*16;
vector< set<unsigned int> > gHashTab;
size_t gN = 0;
size_t gNx = 0;
inline void checkThis(const char *knightPath, const unsigned int hashp = 0){
auto hashx = (hashp)? hashp : std::_Hash_impl::hash(knightPath, gNx, 11);
auto hashy = std::_Hash_impl::hash(knightPath+gNx, gNx, 11);
auto hash2 = hashx^(hashy<<1);
auto hash = hashx%kHashSize;
if(gHashTab[hash].size()==0){
gHashTab[hash].insert(hash2);
++gNPaths;
return;
}
if(gHashTab[hash].size()!=0){
if(gHashTab[hash].count(hash2)) return;
gHashTab[hash].insert(hash2);
++gNPaths;
return;
}
}
void zigs(const string aS, const string bS){
const int n = aS.size();
string raS = aS;
reverse(raS.begin(), raS.end());
string rbS = bS;
reverse(rbS.begin(), rbS.end());
if(n<3) return;
char a[n+1];
char b[n+1];
strcpy(a, aS.c_str());
strcpy(b, bS.c_str());
char ra[n+1];
char rb[n+1];
strcpy(ra, raS.c_str());
strcpy(rb, rbS.c_str());
a[n]='\0';
b[n]='\0';
ra[n]='\0';
rb[n]='\0';
int kStart = 0;
for (; kStart < n; ++kStart){
if(a[kStart]!=a[0] || b[kStart]!=a[0]) break;
}
kStart = max(1,kStart);
int kEnd = n-1;
for (; kEnd != 0; --kEnd){
if(a[kEnd]!=a[n-1] || b[kEnd]!=a[n-1]) break;
}
kEnd+=2;
kEnd = min(n+1,kEnd);
char knightPath[gN+1];
char revKnightPath[gN+1];
knightPath[gN] ='\0';
revKnightPath[gN] ='\0';
char frontLoopTop[gN+1];
memcpy(frontLoopTop, ra, n);
memcpy(frontLoopTop+n, b, n);
frontLoopTop[gN] ='\0';
char frontLoopBottom[gN+1];
memcpy(frontLoopBottom, rb, n);
memcpy(frontLoopBottom+n, a, n);
frontLoopBottom[gN] ='\0';
char tailLoopTop[gN+1];
memcpy(tailLoopTop, a, n);
memcpy(tailLoopTop+n, rb, n);
tailLoopTop[gN] ='\0';
char tailLoopBottom[gN+1];
memcpy(tailLoopBottom, b, n);
memcpy(tailLoopBottom+n, ra, n);
tailLoopBottom[gN] ='\0';
char zigEvenUp[gN+1];
char zigEvenDown[gN+1];
bool goingEvenDown = true;
for (int k = 0; k < n; ++k){
if(goingEvenDown){
zigEvenDown[2*k] = a[k];
zigEvenDown[2*k+1] = b[k];
zigEvenUp[2*k] = b[k];
zigEvenUp[2*k+1] = a[k];
goingEvenDown = false;
}
else{
zigEvenDown[2*k] = b[k];
zigEvenDown[2*k+1] = a[k];
zigEvenUp[2*k] = a[k];
zigEvenUp[2*k+1] = b[k];
goingEvenDown = true;
}
}
zigEvenUp[gN] ='\0';
zigEvenDown[gN] ='\0';
for (int k = kStart; k < n; ++k)
{
memcpy(knightPath, frontLoopTop+n-k, 2*k);
memcpy(revKnightPath, frontLoopBottom+n-k, 2*k);
unsigned int hashx = 0;
unsigned int revHashx = 0;
if(2*k>n){
hashx = std::_Hash_impl::hash(knightPath, gNx, 11);
revHashx = std::_Hash_impl::hash(revKnightPath, gNx, 11);
}
for(int i=k+1;i<kEnd;++i){
bool zigEndsTop = true;
if(k%2 == 1){ //loop starts at the bottom
memcpy(knightPath+2*k, zigEvenDown+2*k, 2*(i-k));
memcpy(revKnightPath+2*k, zigEvenUp+2*k, 2*(i-k));
}
else{//loop starts at the bottom
memcpy(knightPath+2*k, zigEvenUp+2*k, 2*(i-k));
memcpy(revKnightPath+2*k, zigEvenDown+2*k, 2*(i-k));
}
if( i<n ){
if(i%2 == k%2){
memcpy(knightPath+2*i, tailLoopBottom+i, 2*(n-i));
memcpy(revKnightPath+2*i, tailLoopTop+i, 2*(n-i));
}
else{
memcpy(knightPath+2*i, tailLoopTop+i, 2*(n-i));
memcpy(revKnightPath+2*i, tailLoopBottom+i, 2*(n-i));
}
}
checkThis(knightPath, hashx);
checkThis(revKnightPath, revHashx);
}
}
}
void bigLoop(const string a, const string b){
const int n = a.size();
string knightPath = a + b;
reverse(knightPath.begin(),knightPath.begin()+n);
for(int i=0;i<gN;++i){
rotate(knightPath.begin(), knightPath.begin()+1, knightPath.end());
checkThis(knightPath.c_str());
}
}
void paths(const string a, const string b){
string ra = a;
reverse(ra.begin(), ra.end());
string rb = b;
reverse(rb.begin(), rb.end());
bigLoop(a, b);
unsigned int gNPathsAux = gNPaths;
if(ra == b) return;
zigs(a, b);
if(a!=ra || b!=rb){
bigLoop(ra, rb);
zigs(ra, rb);
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int nTests;
cin >> nTests;
for(int i=0;i<nTests;++i){
gHashTab.clear();
gHashTab.resize(kHashSize);
gNPaths = 0;
int n;
cin >> n;
string a,b;
cin >> a;
cin >> b;
gN = a.size()*2;
gNx = a.size();
paths(a,b);
cout << gNPaths << endl;
}
return 0;
}
Python
import os
import sys
PRIME = 1000000007*65535
PMAP = [int((1<<(5*i)) % PRIME) for i in range(1202)]
def chash(s, p = 0):
for c in s:
p = ((p<<5) + ord(c)) % PRIME
return p
def hmap(s):
ret = [0]
for c in s:
ret.append(((ret[-1]<<5)+ord(c)) % PRIME)
return ret
def hrange(l,i,j,s):
return (l[j] + ((s-l[i]) * PMAP[j-i])) % PRIME
def count(s1 : str, s2 : str, s1rev, s2rev):
ret = set()
n,n2 = len(s1),2*len(s1)
left_to_top = s2rev + s1
left_to_bot = s1rev + s2
right_from_top = s1 + s2rev
right_from_bot = s2 + s1rev
mid_even_tb = [ord(s1[i//2]) if ((i%4) in (0,3)) else ord(s2[i//2]) for i in range(n2)]
mid_odd_tb = [ord(s2[i//2]) if ((i%4) in (0,3)) else ord(s1[i//2]) for i in range(n2)]
left_to_top,left_to_bot,right_from_top,right_from_bot = map(hmap,(left_to_top,left_to_bot,right_from_top,right_from_bot))
mid_even_tb = [mid_even_tb[2*j+1] + mid_even_tb[2*j] * PMAP[1] for j in range(n)]
mid_odd_tb = [mid_odd_tb[2*j+1] + mid_odd_tb[2*j] * PMAP[1] for j in range(n)]
for left,mids,rights in (left_to_top,(mid_even_tb,mid_odd_tb),(right_from_top,right_from_bot)),(left_to_bot,(mid_odd_tb,mid_even_tb),(right_from_bot,right_from_top)):
for i in range(0,n+1):
mid = mids[i&1]
s = hrange(left,n-i,n+i,0)
for j in range(i, n):
ret.add(hrange(rights[j&1],j,n2-j,s))
s = (s * PMAP[2] + mid[j]) % PRIME
ret.add(s)
rights = rights[::-1]
return ret
def gridlandProvinces(s1, s2):
s1rev,s2rev = s1[::-1],s2[::-1]
return len(count(s1, s2, s1rev, s2rev).union(count(s1rev, s2rev, s1, s2)))
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
p = int(input())
for p_itr in range(p):
n = int(input())
s1 = input()
s2 = input()
result = gridlandProvinces(s1, s2)
fptr.write(str(result) + '\n')
fptr.close()
Java
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Solution2 {
private final static Scanner scanner =
new Scanner(System.in);
private final static long mod1 = 2147483607,
f1 = 107, f2 = 101;
private final static long[] arr1 = new long[10000],
arr2 = new long[10000];
private final static Set<Long> result = new HashSet<>();
public static void main(String[] args) {
for (int i = 0; i < arr1.length; ++i) {
arr1[i] = i > 0 ? arr1[i - 1] * f1 % mod1 : 1;
arr2[i] = i > 0 ? arr2[i - 1] * f2 % mod1 : 1;
}
for (int t = scanner.nextInt(); t > 0; --t) {
result.clear();
scanner.nextInt();
char[] c1 = scanner.next().toCharArray();
char[] c2 = scanner.next().toCharArray();
for (int i = 0; i < c1.length; ++i) {
process(c1, c2, i, false);
process(c2, c1, i, false);
process(c1, c2, i, true);
process(c2, c1, i, true);
}
reverse(c1);
reverse(c2);
for (int i = 0; i < c1.length; ++i) {
process(c1, c2, i, false);
process(c2, c1, i, false);
process(c1, c2, i, true);
process(c2, c1, i, true);
}
System.out.println(result.size());
}
}
static void process(char[] s1, char[] s2, int k, boolean b) {
long p1 = 0, p2 = 0, p3 = 0, p4 = 0;
for (int i = 0; i < k; ++i) {
p1 = (p1 + s1[i] * arr1[k - 1 - i]) % mod1;
p1 = (p1 + s2[i] * arr1[k + i]) % mod1;
p3 = (p3 + s1[i] * arr2[k - 1 - i]) % mod1;
p3 = (p3 + s2[i] * arr2[k + i]) % mod1;
}
if (b) {
p1 = (p1 + s2[k] * arr1[k * 2]) % mod1;
p1 = (p1 + s1[k] * arr1[k * 2 + 1]) % mod1;
p3 = (p3 + s2[k] * arr2[k * 2]) % mod1;
p3 = (p3 + s1[k] * arr2[k * 2 + 1]) % mod1;
char[] s = s1; s1 = s2; s2 = s;
++k;
}
for (int i = k; i < s1.length; ++i) {
p2 = (p2 + s1[i] * arr1[s1.length * 2 + k - 1 - i]) % mod1;
p2 = (p2 + s2[i] * arr1[i + k]) % mod1;
p4 = (p4 + s1[i] * arr2[s1.length * 2 + k - 1 - i]) % mod1;
p4 = (p4 + s2[i] * arr2[i + k]) % mod1;
}
result.add(((p1 + p2) % mod1) * mod1 + (p3 + p4) % mod1);
for (int i = k; i < s1.length - 1; i += 2) {
p1 = (p1 + s2[i] * arr1[i * 2]) % mod1;
p1 = (p1 + s1[i] * arr1[i * 2 + 1]) % mod1;
p1 = (p1 + s1[i + 1] * arr1[i * 2 + 2]) % mod1;
p1 = (p1 + s2[i + 1] * arr1[i * 2 + 3]) % mod1;
p2 = (p2 + s2[i] * (mod1 - arr1[i * 2])) % mod1;
p2 = (p2 + s2[i+1] * (mod1 - arr1[i * 2 + 1])) % mod1;
p2 = (p2 + s1[i] * (mod1 - arr1[s1.length * 2 - 1])) % mod1;
p2 = (p2 + s1[i+1] * (mod1 - arr1[s1.length * 2 - 2])) % mod1;
p2 = (p2 * f1 * f1) % mod1;
p3 = (p3 + s2[i] * arr2[i * 2]) % mod1;
p3 = (p3 + s1[i] * arr2[i * 2 + 1]) % mod1;
p3 = (p3 + s1[i + 1] * arr2[i * 2 + 2]) % mod1;
p3 = (p3 + s2[i + 1] * arr2[i * 2 + 3]) % mod1;
p4 = (p4 + s2[i] * (mod1 - arr2[i * 2])) % mod1;
p4 = (p4 + s2[i+1] * (mod1 - arr2[i * 2 + 1])) % mod1;
p4 = (p4 + s1[i] * (mod1 - arr2[s1.length * 2 - 1])) % mod1;
p4 = (p4 + s1[i+1] * (mod1 - arr2[s1.length * 2 - 2])) % mod1;
p4 = (p4 * f2 * f2) % mod1;
result.add(((p1 + p2) % mod1) * mod1 + (p3 + p4) % mod1);
}
}
private static void reverse(char[] str) {
for (int i = str.length / 2 - 1; i >= 0; --i) {
char t = str[i];
str[i] = str[str.length - 1 - i];
str[str.length - 1 - i] = t;
}
}
}
Note: This problem (Gridland Provinces) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.