Gridland Provinces – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Gridland Provinces HackerRank Solution
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
unsigned long long readTimeStampCounter() {
unsigned a = 123456789, b = 987654321;
#ifdef __GNUC__
asm(
"rdtsc;\n\t"
: "=d" (a), "=a" (b)
);
#else
__asm {
rdtsc;
mov a, edx;
mov b, eax;
};
#endif
return (unsigned long long)a << 32 | b;
}
unsigned xor128() {
static unsigned x = 123456789, y = 362436069,
z = (unsigned)(readTimeStampCounter() >> 32), w = (unsigned)readTimeStampCounter();
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
struct PolynomialHash {
static const int NumMods = 2;
static const unsigned Mods[NumMods];
typedef unsigned long long ull;
struct Hash {
unsigned hs[NumMods];
Hash() { for(int k = 0; k < NumMods; ++ k) hs[k] = 0; }
bool operator==(const Hash &that) const {
bool res = true;
for(int k = 0; k < NumMods; ++ k)
res &= hs[k] == that.hs[k];
return res;
}
bool operator<(const Hash &that) const {
for(int k = 0; k < NumMods; ++ k)
if(hs[k] != that.hs[k])
return hs[k] < that.hs[k];
return false;
}
//string debugstr;
};
static unsigned seeds[NumMods];
static std::vector<Hash> powh;
static void initSeeds() {
for(int k = 0; k < NumMods; ++ k) {
unsigned x;
do x = xor128(); while(x == 0 || x >= Mods[k]);
seeds[k] = x;
}
}
static void precomputePowerTable(int newSize) {
if((int)powh.size() >= newSize) return;
if(seeds[0] == 0) initSeeds();
int oldSize = powh.size();
powh.resize(newSize);
if(oldSize == 0)
for(int k = 0; k < NumMods; ++ k) powh[0].hs[k] = 1;
for(int i = std::max(1, oldSize); i < newSize; i ++) for(int k = 0; k < NumMods; ++ k)
powh[i].hs[k] = (ull)powh[i - 1].hs[k] * seeds[k] % Mods[k];
}
};
const unsigned PolynomialHash::Mods[PolynomialHash::NumMods] = { 2147483647U, 2147483629U };
unsigned PolynomialHash::seeds[PolynomialHash::NumMods];
std::vector<PolynomialHash::Hash> PolynomialHash::powh;
struct SubstringHash : PolynomialHash {
std::vector<Hash> preh;
string debugS;
template<typename V>
void init(const V &v, int n) {
debugS = v;
precomputePowerTable(n + 1);
preh.resize(n + 1);
preh[0] = Hash();
for(int i = 0; i < n; i ++) for(int k = 0; k < NumMods; ++ k)
preh[i + 1].hs[k] = ((ull)preh[i].hs[k] * seeds[k] % Mods[k] + v[i]) % Mods[k];
}
Hash hash(int j) const {
return preh[j];
}
Hash hash(int i, int j) const {
if(i == 0) return hash(j);
Hash res;
for(int k = 0; k < NumMods; ++ k) {
unsigned x = preh[j].hs[k] + Mods[k] - (unsigned)((ull)preh[i].hs[k] * powh[j - i].hs[k] % Mods[k]);
res.hs[k] = x >= Mods[k] ? x - Mods[k] : x;
}
//res.debugstr = debugS.substr(i, j - i);
return res;
}
Hash append(const Hash &h, const Hash &g, int glen) const {
Hash res;
for(int k = 0; k < NumMods; ++ k) {
unsigned x = (unsigned)((ull)h.hs[k] * powh[glen].hs[k] % Mods[k]) + g.hs[k];
res.hs[k] = x >= Mods[k] ? x - Mods[k] : x;
}
//res.debugstr = h.debugstr + g.debugstr;
//assert(glen == g.debugstr.size());
return res;
}
};
int main() {
PolynomialHash::initSeeds();
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ++ ii) {
int N;
scanf("%d", &N);
vector<string> S(2);
cin >> S[0] >> S[1];
SubstringHash app;
string tmp(N * 2, '.');
app.init(tmp, N * 2);
vector<SubstringHash::Hash> hashes;
rep(my, 2) {
rep(mx, 2) {
string zigzag[2];
rep(i, N) {
rep(j, 2) {
rep(p, 2)
zigzag[p] += S[(j + i + p) % 2][i];
}
}
SubstringHash zigzagh[2];
rep(p, 2)
zigzagh[p].init(zigzag[p], N * 2);
SubstringHash sh[2], revh[2];
rep(i, 2) {
sh[i].init(S[i], N);
reverse(S[i].begin(), S[i].end());
revh[i].init(S[i], N);
reverse(S[i].begin(), S[i].end());
}
rep(i, N) rer(j, i + 1, N) {
SubstringHash::Hash h;
h = app.append(h, revh[0].hash(N - i - 1, N), i + 1);
h = app.append(h, sh[1].hash(0, i + 1), i + 1);
h = app.append(h, zigzagh[i % 2].hash((i + 1) * 2, j * 2), (j - i - 1) * 2);
int p = (j - i) % 2;
h = app.append(h, sh[p].hash(j, N), N - j);
h = app.append(h, revh[1-p].hash(0, N - j), N - j);
hashes.push_back(h);
}
rep(k, 2)
reverse(S[k].begin(), S[k].end());
}
S[0].swap(S[1]);
}
sort(hashes.begin(), hashes.end());
hashes.erase(unique(hashes.begin(), hashes.end()), hashes.end());
int ans = (int)hashes.size();
printf("%d\n", ans);
}
return 0;
}
Java Gridland Provinces HackerRank Solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.util.Random;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Writer;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author Egor Kulikov (egor@egork.net)
*/
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
GridlandProvinces solver = new GridlandProvinces();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++) {
solver.solve(i, in, out);
}
out.close();
}
static class GridlandProvinces {
public void solve(int testNumber, InputReader in, OutputWriter out) {
// sss = new HashSet<>();
int n = in.readInt();
String[] s = IOUtils.readStringArray(in, 2);
LongSet set = new LongHashSet();
addAll(n, s, set);
for (int i = 0; i < 2; i++) {
s[i] = StringUtils.reverse(s[i]);
}
addAll(n, s, set);
out.printLine(set.size());
// System.err.println(sss.size());
}
protected void addAll(int n, String[] s, LongSet set) {
StringHash[] simple = new StringHash[2];
for (int i = 0; i < 2; i++) {
simple[i] = new SimpleStringHash(s[i]);
}
StringHash[] reverse = new StringHash[2];
for (int i = 0; i < 2; i++) {
reverse[i] = new SimpleStringHash(StringUtils.reverse(s[i]));
}
StringHash[] snail = new StringHash[2];
// String[] sn = new String[2];
for (int i = 0; i < 2; i++) {
StringBuilder current = new StringBuilder(2 * n);
for (int j = 0; j < n; j++) {
current.append(s[i ^ (j & 1)].charAt(j));
current.append(s[1 - (i ^ (j & 1))].charAt(j));
}
snail[i] = new SimpleStringHash(current.toString());
// sn[i] = current.toString();
}
for (int i = 0; i <= n; i++) {
for (int j = i; j <= n; j++) {
for (int k = 0; k < 2; k++) {
// String ss = reverse(s[k]).substring(n - i, n) + s[1 - k].substring(0, i) + sn[1 - (k ^ (i & 1))]
// .substring(2 * i, 2 * j) + s[1 - (k ^ ((j - i) & 1))].substring(j, n) + reverse(s[(k ^ (
// (j - i) & 1))]).substring(0, n - j);
// sss.add(ss);
// System.err.println(ss);
StringHash hash = new CompositeStringHash(new SubstringStringHash(reverse[k], n - i, n),
new CompositeStringHash(new SubstringStringHash(simple[1 - k], 0, i),
new CompositeStringHash(new SubstringStringHash(snail[1 - (k ^ (i & 1))], 2 *
i, 2 * j),
new CompositeStringHash(
new SubstringStringHash(simple[1 - (k ^ ((j - i) & 1))
], j, n),
new SubstringStringHash(reverse[(k ^ ((j - i) & 1))], 0,
n - j)))));
set.add(hash.hash(0));
}
}
}
}
}
static interface LongReversableCollection extends LongCollection {
}
static interface StringHash {
long hash(int from, int to);
long hash(int from);
int length();
}
static class LongHashSet extends LongAbstractStream implements LongSet {
private static final Random RND = new Random();
private static final int[] SHIFTS = new int[4];
private static final byte PRESENT_MASK = 1;
private static final byte REMOVED_MASK = 2;
private int size;
private int realSize;
private long[] values;
private byte[] present;
private int step;
private int ratio;
static {
for (int i = 0; i < 4; i++) {
SHIFTS[i] = RND.nextInt(31) + 1;
}
}
public LongHashSet() {
this(3);
}
public LongHashSet(int capacity) {
capacity = Math.max(capacity, 3);
values = new long[capacity];
present = new byte[capacity];
ratio = 2;
initStep(capacity);
}
public LongHashSet(LongCollection c) {
this(c.size());
addAll(c);
}
public LongHashSet(long[] arr) {
this(new LongArray(arr));
}
private void initStep(int capacity) {
step = RND.nextInt(capacity - 2) + 1;
while (IntegerUtils.gcd(step, capacity) != 1) {
step++;
}
}
public LongIterator longIterator() {
return new LongIterator() {
private int position = size == 0 ? values.length : -1;
public long value() throws NoSuchElementException {
if (position == -1) {
advance();
}
if (position >= values.length) {
throw new NoSuchElementException();
}
if ((present[position] & PRESENT_MASK) == 0) {
throw new IllegalStateException();
}
return values[position];
}
public boolean advance() throws NoSuchElementException {
if (position >= values.length) {
throw new NoSuchElementException();
}
position++;
while (position < values.length && (present[position] & PRESENT_MASK) == 0) {
position++;
}
return isValid();
}
public boolean isValid() {
return position < values.length;
}
public void remove() {
if ((present[position] & PRESENT_MASK) == 0) {
throw new IllegalStateException();
}
present[position] = REMOVED_MASK;
}
};
}
public int size() {
return size;
}
public void add(long value) {
ensureCapacity((realSize + 1) * ratio + 2);
int current = getHash(value);
while (present[current] != 0) {
if ((present[current] & PRESENT_MASK) != 0 && values[current] == value) {
return;
}
current += step;
if (current >= values.length) {
current -= values.length;
}
}
while ((present[current] & PRESENT_MASK) != 0) {
current += step;
if (current >= values.length) {
current -= values.length;
}
}
if (present[current] == 0) {
realSize++;
}
present[current] = PRESENT_MASK;
values[current] = value;
size++;
}
private int getHash(long value) {
int hash = LongHash.hash(value);
int result = hash;
for (int i : SHIFTS) {
result ^= hash >> i;
}
result %= values.length;
if (result < 0) {
result += values.length;
}
return result;
}
private void ensureCapacity(int capacity) {
if (values.length < capacity) {
capacity = Math.max(capacity * 2, values.length);
rebuild(capacity);
}
}
private void rebuild(int capacity) {
initStep(capacity);
long[] oldValues = values;
byte[] oldPresent = present;
values = new long[capacity];
present = new byte[capacity];
size = 0;
realSize = 0;
for (int i = 0; i < oldValues.length; i++) {
if ((oldPresent[i] & PRESENT_MASK) == PRESENT_MASK) {
add(oldValues[i]);
}
}
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private InputReader.SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
if (Character.isValidCodePoint(c)) {
res.appendCodePoint(c);
}
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void printLine(int i) {
writer.println(i);
}
}
static interface LongIterator {
public long value() throws NoSuchElementException;
public boolean advance();
public boolean isValid();
}
static interface LongSet extends LongCollection {
}
static interface LongStream extends Iterable<Long>, Comparable<LongStream> {
public LongIterator longIterator();
default public Iterator<Long> iterator() {
return new Iterator<Long>() {
private LongIterator it = longIterator();
public boolean hasNext() {
return it.isValid();
}
public Long next() {
long result = it.value();
it.advance();
return result;
}
};
}
default public int compareTo(LongStream c) {
LongIterator it = longIterator();
LongIterator jt = c.longIterator();
while (it.isValid() && jt.isValid()) {
long i = it.value();
long j = jt.value();
if (i < j) {
return -1;
} else if (i > j) {
return 1;
}
it.advance();
jt.advance();
}
if (it.isValid()) {
return 1;
}
if (jt.isValid()) {
return -1;
}
return 0;
}
}
static class StringUtils {
public static String reverse(String sample) {
StringBuilder result = new StringBuilder(sample);
result.reverse();
return result.toString();
}
}
static class SubstringStringHash extends AbstractStringHash {
private final StringHash base;
private final int from;
private final int to;
public SubstringStringHash(StringHash base, int from) {
this(base, from, base.length());
}
public SubstringStringHash(StringHash base, int from, int to) {
this.base = base;
this.from = from;
this.to = to;
}
public long hash(int from, int to) {
if (to + this.from > this.to) {
throw new IndexOutOfBoundsException();
}
return base.hash(from + this.from, to + this.from);
}
public int length() {
return to - from;
}
}
static interface LongCollection extends LongStream {
public int size();
default public void add(long value) {
throw new UnsupportedOperationException();
}
default public LongCollection addAll(LongStream values) {
for (LongIterator it = values.longIterator(); it.isValid(); it.advance()) {
add(it.value());
}
return this;
}
}
static class SimpleStringHash extends AbstractStringHash {
private static long[] firstReversePower = new long[0];
private static long[] secondReversePower = new long[0];
private final long[] firstHash;
private final long[] secondHash;
public SimpleStringHash(CharSequence string) {
int length = string.length();
ensureCapacity(length);
firstHash = new long[length + 1];
secondHash = new long[length + 1];
long firstPower = 1;
long secondPower = 1;
for (int i = 0; i < length; i++) {
firstHash[i + 1] = (firstHash[i] + string.charAt(i) * firstPower) % AbstractStringHash.FIRST_MOD;
secondHash[i + 1] = (secondHash[i] + string.charAt(i) * secondPower) % AbstractStringHash.SECOND_MOD;
firstPower *= AbstractStringHash.MULTIPLIER;
firstPower %= AbstractStringHash.FIRST_MOD;
secondPower *= AbstractStringHash.MULTIPLIER;
secondPower %= AbstractStringHash.SECOND_MOD;
}
}
private void ensureCapacity(int length) {
if (firstReversePower.length >= length) {
return;
}
length = Math.max(length + 1, firstReversePower.length << 1);
long[] oldFirst = firstReversePower;
long[] oldSecond = secondReversePower;
firstReversePower = new long[length];
secondReversePower = new long[length];
System.arraycopy(oldFirst, 0, firstReversePower, 0, oldFirst.length);
System.arraycopy(oldSecond, 0, secondReversePower, 0, oldSecond.length);
firstReversePower[0] = secondReversePower[0] = 1;
for (int i = Math.max(oldFirst.length, 1); i < length; i++) {
firstReversePower[i] = firstReversePower[i - 1] * AbstractStringHash.FIRST_REVERSE_MULTIPLIER %
AbstractStringHash.FIRST_MOD;
secondReversePower[i] = secondReversePower[i - 1] * AbstractStringHash.SECOND_REVERSE_MULTIPLIER %
AbstractStringHash.SECOND_MOD;
}
}
public long hash(int from, int to) {
return (((firstHash[to] - firstHash[from] + AbstractStringHash.FIRST_MOD) * firstReversePower[from] %
AbstractStringHash.FIRST_MOD) << 32) +
((secondHash[to] - secondHash[from] + AbstractStringHash.SECOND_MOD) * secondReversePower[from] %
AbstractStringHash.SECOND_MOD);
}
public int length() {
return firstHash.length - 1;
}
}
static class LongHash {
private LongHash() {
}
public static int hash(long c) {
return (int) ((c >>> 32) ^ c);
}
}
static abstract class AbstractStringHash implements StringHash {
public static final long MULTIPLIER;
protected static final long FIRST_REVERSE_MULTIPLIER;
protected static final long SECOND_REVERSE_MULTIPLIER;
public static final long FIRST_MOD;
public static final long SECOND_MOD;
static {
Random random = new Random(System.currentTimeMillis());
FIRST_MOD = IntegerUtils.nextPrime((long) (1e9 + random.nextInt((int) 1e9)));
SECOND_MOD = IntegerUtils.nextPrime((long) (1e9 + random.nextInt((int) 1e9)));
MULTIPLIER = random.nextInt((int) 1e9 - 257) + 257;
FIRST_REVERSE_MULTIPLIER = IntegerUtils.reverse(MULTIPLIER, FIRST_MOD);
SECOND_REVERSE_MULTIPLIER = IntegerUtils.reverse(MULTIPLIER, SECOND_MOD);
}
public long hash(int from) {
return hash(from, length());
}
}
static interface LongList extends LongReversableCollection {
public abstract long get(int index);
public abstract void addAt(int index, long value);
public abstract void removeAt(int index);
default public LongIterator longIterator() {
return new LongIterator() {
private int at;
private boolean removed;
public long value() {
if (removed) {
throw new IllegalStateException();
}
return get(at);
}
public boolean advance() {
at++;
removed = false;
return isValid();
}
public boolean isValid() {
return !removed && at < size();
}
public void remove() {
removeAt(at);
at--;
removed = true;
}
};
}
default public void add(long value) {
addAt(size(), value);
}
}
static class LongArray extends LongAbstractStream implements LongList {
private long[] data;
public LongArray(long[] arr) {
data = arr;
}
public int size() {
return data.length;
}
public long get(int at) {
return data[at];
}
public void addAt(int index, long value) {
throw new UnsupportedOperationException();
}
public void removeAt(int index) {
throw new UnsupportedOperationException();
}
}
static abstract class LongAbstractStream implements LongStream {
public String toString() {
StringBuilder builder = new StringBuilder();
boolean first = true;
for (LongIterator it = longIterator(); it.isValid(); it.advance()) {
if (first) {
first = false;
} else {
builder.append(' ');
}
builder.append(it.value());
}
return builder.toString();
}
public boolean equals(Object o) {
if (!(o instanceof LongStream)) {
return false;
}
LongStream c = (LongStream) o;
LongIterator it = longIterator();
LongIterator jt = c.longIterator();
while (it.isValid() && jt.isValid()) {
if (it.value() != jt.value()) {
return false;
}
it.advance();
jt.advance();
}
return !it.isValid() && !jt.isValid();
}
public int hashCode() {
int result = 0;
for (LongIterator it = longIterator(); it.isValid(); it.advance()) {
result *= 31;
result += it.value();
}
return result;
}
}
static class IntegerUtils {
public static int gcd(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
public static long power(long base, long exponent, long mod) {
if (base >= mod) {
base %= mod;
}
if (exponent == 0) {
return 1 % mod;
}
long result = power(base, exponent >> 1, mod);
result = result * result % mod;
if ((exponent & 1) != 0) {
result = result * base % mod;
}
return result;
}
public static long reverse(long number, long module) {
return power(number, module - 2, module);
}
public static boolean isPrime(long number) {
if (number < 2) {
return false;
}
for (long i = 2; i * i <= number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static long nextPrime(long from) {
if (from <= 2) {
return 2;
}
from += 1 - (from & 1);
while (!isPrime(from)) {
from += 2;
}
return from;
}
}
static class CompositeStringHash extends AbstractStringHash {
private static long[] firstPower = new long[0];
private static long[] secondPower = new long[0];
private final StringHash first;
private final StringHash second;
public CompositeStringHash(StringHash first, StringHash second) {
this.first = first;
this.second = second;
ensureCapacity(first.length() + 1);
}
private void ensureCapacity(int length) {
if (firstPower.length >= length) {
return;
}
length = Math.max(length + 1, firstPower.length << 1);
long[] oldFirst = firstPower;
long[] oldSecond = secondPower;
firstPower = new long[length];
secondPower = new long[length];
System.arraycopy(oldFirst, 0, firstPower, 0, oldFirst.length);
System.arraycopy(oldSecond, 0, secondPower, 0, oldSecond.length);
firstPower[0] = secondPower[0] = 1;
for (int i = Math.max(oldFirst.length, 1); i < length; i++) {
firstPower[i] = firstPower[i - 1] * AbstractStringHash.MULTIPLIER % AbstractStringHash.FIRST_MOD;
secondPower[i] = secondPower[i - 1] * AbstractStringHash.MULTIPLIER % AbstractStringHash.SECOND_MOD;
}
}
public long hash(int from, int to) {
long firstFirst;
long firstSecond;
long secondFirst;
long secondSecond;
if (to <= first.length()) {
secondFirst = 0;
secondSecond = 0;
} else {
long value = second.hash(Math.max(0, from - first.length()), to - first.length());
secondFirst = value >>> 32;
secondSecond = value & ((1L << 32) - 1);
}
if (from >= first.length()) {
firstFirst = 0;
firstSecond = 0;
} else {
long value = first.hash(from, Math.min(to, first.length()));
firstFirst = value >>> 32;
firstSecond = value & ((1L << 32) - 1);
}
return (((firstFirst + secondFirst * firstPower[Math.max(0, first.length() - from)]) %
AbstractStringHash.FIRST_MOD) << 32) +
((firstSecond + secondSecond * secondPower[Math.max(0, first.length() - from)]) %
AbstractStringHash.SECOND_MOD);
}
public int length() {
return first.length() + second.length();
}
}
static class IOUtils {
public static String[] readStringArray(InputReader in, int size) {
String[] array = new String[size];
for (int i = 0; i < size; i++) {
array[i] = in.readString();
}
return array;
}
}
}
Python 3 Gridland Provinces HackerRank Solution
class Solution:
def __init__(self):
self.size = int(input())
self.array = []
self.array.append(input().strip())
self.array.append(input().strip())
self.hash = set()
def add_to_hash(self, results):
for set_str in results:
self.hash.add(hash(set_str))
self.hash.add(hash(set_str[::-1]))
def calculate(self):
if len(set(self.array[0]+self.array[1]))==1:
return 1
results = self.get_circles(self.array[0]+self.array[1][::-1])
full_string1 = self.array[1][::-1]+self.array[0]
full_string2 = self.array[0][::-1]+self.array[1]
full_zigzags=self.get_zigzag('',1,0,+1)
self.add_to_hash(results)
results=set(full_zigzags.keys())
for i in range(1,self.size):
for zig,diverge in full_zigzags.items():
if diverge < i:
continue
j = self.size -i
if i%2 == 0:
new_str = full_string2[j:-j]+zig[i*2:]
else:
new_str = full_string1[j:-j]+zig[i*2:]
results.add(new_str)
self.add_to_hash(results)
full_zigzags=self.get_zigzag('',0,0,+1)
results=set(full_zigzags.keys())
for i in range(1,self.size):
for zig,diverge in full_zigzags.items():
if diverge < i:
continue
j = self.size -i
if i%2 == 0:
new_str = full_string1[j:-j]+zig[i*2:]
else:
new_str = full_string2[j:-j]+zig[i*2:]
results.add(new_str)
self.add_to_hash(results)
return len(self.hash)
def get_circles(self,loop):
circles = set()
circles.add(loop)
for i in range(self.size*2-1):
loop = loop[1:]+loop[0]
circles.add(loop)
return circles
def get_zigzag(self,seed,row,col,right):
output = list(seed)
steps = 0
zigzags = {}
while col >=0 and col <self.size:
output.append(self.array[row][col])
steps+=1
row = 0 if row == 1 else 1
if steps < self.size*2:
zigzags[self.add_circle_diversion(row,col,right,''.join(output))]=steps//2
output.append(self.array[row][col])
steps+=1
col+=right
zigzags[''.join(output)]=self.size
return zigzags
def add_circle_diversion(self, row, col, right, built_str):
built_str+=self.array[row][col::right]
remaining = 2*self.size-len(built_str)
if remaining == 0:
return built_str
row = 0 if row == 1 else 1
built_str+=self.array[row][::-1*right][:remaining]
return built_str
def main():
cases = int(input())
for i in range(cases):
my_object = Solution()
print(my_object.calculate())
def get_int_list(in_str):
return [int(i) for i in in_str.strip().split()]
if __name__ == "__main__":
main()
Python 2 Gridland Provinces HackerRank Solution
#!/bin/python
from __future__ import print_function
import os
import sys
def snake(s1, s2):
j = 0
res = ''
for a, b in zip(s1, s2):
if j == 0:
res += a + b
else:
res += b + a
j = 1-j
return res
def rev(s):
res = ''.join(list(reversed(s)))
return res
def rotations(s):
return {s[i:] + s[:i] for i in range(len(s))}
#
# Complete the gridlandProvinces function below.
#
def gridlandProvinces(s1, s2):
print (s1, s2)
res = set()
res = res.union(rotations(s1 + rev(s2)))
res = res.union(rotations(s2 + rev(s1)))
n = len(s1)
def special(a, b, i):
return a[i:] + rev(b[i:]) + snake(rev(b[:i]), rev(a[:i]))
for i in range(n):
res.add(special(s1,s2,i))
res.add(special(s2,s1,i))
res.add(special(rev(s1), rev(s2), i))
res.add(special(rev(s2), rev(s1), i))
# for x in sorted(res):
# print(x)
return len(res)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
p = int(raw_input())
for p_itr in xrange(p):
n = int(raw_input())
s1 = raw_input()
s2 = raw_input()
result = gridlandProvinces(s1, s2)
fptr.write(str(result) + '\n')
fptr.close()
C Gridland Provinces HackerRank Solution
/*
3
1
a
a
3
dab
abd
5
ababa
babab
1
8
2
*/
#include <stdio.h>
#include <stdlib.h>
#define MOD1 1000000007
#define MOD2 1000000009
#define HASH_SIZE 123455
typedef struct _node{
int x;
int y;
struct _node *next;
} node;
void solve(int i,int j);
void insert(int x,int y);
void freehash();
long long modInverse(long long a,long long mod);
char a[2][601];
int hash_count,N;
long long tr1[1200],tl1[1200],br1[1200],bl1[1200],dr1[1200],dl1[1200],ur1[1200],ul1[1200],mod1[1201],inmod1[1201];
long long tr2[1200],tl2[1200],br2[1200],bl2[1200],dr2[1200],dl2[1200],ur2[1200],ul2[1200],mod2[1201],inmod2[1201];
node *hash[HASH_SIZE]={0};
int main(){
int T,i,j;
long long t1,t2;
scanf("%d",&T);
while(T--){
hash_count=0;
scanf("%d%s%s",&N,&a[0][0],&a[1][0]);
for(i=0,t1=t2=1;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i){
tl1[i]=((a[0][i]-'a')*t1+tl1[i-1])%MOD1;
bl1[i]=((a[1][i]-'a')*t1+bl1[i-1])%MOD1;
tl2[i]=((a[0][i]-'a')*t2+tl2[i-1])%MOD2;
bl2[i]=((a[1][i]-'a')*t2+bl2[i-1])%MOD2;
}
else{
tl1[i]=a[0][i]-'a';
bl1[i]=a[1][i]-'a';
tl2[i]=a[0][i]-'a';
bl2[i]=a[1][i]-'a';
}
for(i=N-1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2){
tl1[2*N-i-1]=((a[1][i]-'a')*t1+tl1[2*N-i-2])%MOD1;
bl1[2*N-i-1]=((a[0][i]-'a')*t1+bl1[2*N-i-2])%MOD1;
tl2[2*N-i-1]=((a[1][i]-'a')*t2+tl2[2*N-i-2])%MOD2;
bl2[2*N-i-1]=((a[0][i]-'a')*t2+bl2[2*N-i-2])%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i!=N-1){
tr1[N-i-1]=((a[0][i]-'a')*t1+tr1[N-i-2])%MOD1;
br1[N-i-1]=((a[1][i]-'a')*t1+br1[N-i-2])%MOD1;
tr2[N-i-1]=((a[0][i]-'a')*t2+tr2[N-i-2])%MOD2;
br2[N-i-1]=((a[1][i]-'a')*t2+br2[N-i-2])%MOD2;
}
else{
tr1[N-i-1]=a[0][i]-'a';
br1[N-i-1]=a[1][i]-'a';
tr2[N-i-1]=a[0][i]-'a';
br2[N-i-1]=a[1][i]-'a';
}
for(i=0;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2){
tr1[i+N]=((a[1][i]-'a')*t1+tr1[i+N-1])%MOD1;
br1[i+N]=((a[0][i]-'a')*t1+br1[i+N-1])%MOD1;
tr2[i+N]=((a[1][i]-'a')*t2+tr2[i+N-1])%MOD2;
br2[i+N]=((a[0][i]-'a')*t2+br2[i+N-1])%MOD2;
}
for(i=0,t1=t2=1;i<N;i++){
if(i%2){
ul1[2*i]=((a[0][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[1][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[0][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[1][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
else
if(!i){
ul1[2*i]=a[1][i]-'a';
dl1[2*i]=a[0][i]-'a';
ul2[2*i]=a[1][i]-'a';
dl2[2*i]=a[0][i]-'a';
}
else{
ul1[2*i]=((a[1][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[0][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[1][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[0][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if(i%2){
ul1[2*i+1]=((a[1][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[0][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[1][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[0][i]-'a')*t2+dl2[2*i])%MOD2;
}
else{
ul1[2*i+1]=((a[0][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[1][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[0][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[1][i]-'a')*t2+dl2[2*i])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--)
if(i==N-1){
ur1[2*(N-1-i)]=a[1][i]-'a';
dr1[2*(N-1-i)]=a[0][i]-'a';
ur2[2*(N-1-i)]=a[1][i]-'a';
dr2[2*(N-1-i)]=a[0][i]-'a';
t1=t1*26%MOD1;
t2=t2*26%MOD2;
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
else{
if((N-i)%2==0){
ur1[2*(N-1-i)]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
else{
ur1[2*(N-1-i)]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if((N-i)%2==0){
ur1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
else{
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=0;i<=2*N;i++)
if(i){
mod1[i]=mod1[i-1]*26%MOD1;
inmod1[i]=modInverse(mod1[i],MOD1);
mod2[i]=mod2[i-1]*26%MOD2;
inmod2[i]=modInverse(mod2[i],MOD2);
}
else
mod1[i]=inmod1[i]=mod2[i]=inmod2[i]=1;
for(i=0;i<=N;i++)
for(j=i;j<=N;j++)
solve(i,j);
printf("%d\n",hash_count);
freehash();
}
return 0;
}
void solve(int i,int j){
long long t1,t2,t3,t4,t5,t6,t7,t8,t9;
long long tt1,tt2,tt3,tt4,tt5,tt6,tt7,tt8,tt9;
t1=tr1[N+i-1];
t2=br1[N+i-1];
if(i!=N){
t1=(t1-tr1[N-i-1]+MOD1)%MOD1;
t2=(t2-br1[N-i-1]+MOD1)%MOD1;
}
t1=t1*inmod1[N-i]%MOD1;
t2=t2*inmod1[N-i]%MOD1;
t3=tl1[2*N-j-1];
t4=bl1[2*N-j-1];
if(j){
t3=(t3-tl1[j-1]+MOD1)%MOD1;
t4=(t4-bl1[j-1]+MOD1)%MOD1;
}
t3=t3*inmod1[j]%MOD1;
t4=t4*inmod1[j]%MOD1;
if(!j)
t5=t6=0;
else{
t5=ul1[2*j-1];
t6=dl1[2*j-1];
if(i){
t5=(t5-ul1[2*i-1]+MOD1)%MOD1;
t6=(t6-dl1[2*i-1]+MOD1)%MOD1;
}
}
if(i==N)
t7=t8=0;
else{
t7=ur1[2*(N-i)-1];
t8=dr1[2*(N-i)-1];
if(j!=N){
t7=(t7-ur1[2*(N-j)-1]+MOD1)%MOD1;
t8=(t8-dr1[2*(N-j)-1]+MOD1)%MOD1;
}
}
tt1=tr2[N+i-1];
tt2=br2[N+i-1];
if(i!=N){
tt1=(tt1-tr2[N-i-1]+MOD2)%MOD2;
tt2=(tt2-br2[N-i-1]+MOD2)%MOD2;
}
tt1=tt1*inmod2[N-i]%MOD2;
tt2=tt2*inmod2[N-i]%MOD2;
tt3=tl2[2*N-j-1];
tt4=bl2[2*N-j-1];
if(j){
tt3=(tt3-tl2[j-1]+MOD2)%MOD2;
tt4=(tt4-bl2[j-1]+MOD2)%MOD2;
}
tt3=tt3*inmod2[j]%MOD2;
tt4=tt4*inmod2[j]%MOD2;
if(!j)
tt5=tt6=0;
else{
tt5=ul2[2*j-1];
tt6=dl2[2*j-1];
if(i){
tt5=(tt5-ul2[2*i-1]+MOD2)%MOD2;
tt6=(tt6-dl2[2*i-1]+MOD2)%MOD2;
}
}
if(i==N)
tt7=tt8=0;
else{
tt7=ur2[2*(N-i)-1];
tt8=dr2[2*(N-i)-1];
if(j!=N){
tt7=(tt7-ur2[2*(N-j)-1]+MOD2)%MOD2;
tt8=(tt8-dr2[2*(N-j)-1]+MOD2)%MOD2;
}
}
t9=t1;
if(i%2)
t9+=t6;
else
t9+=t5;
if((j-i)%2)
t9+=t3*mod1[j*2]%MOD1;
else
t9+=t4*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt1;
if(i%2)
tt9+=tt6;
else
tt9+=tt5;
if((j-i)%2)
tt9+=tt3*mod2[j*2]%MOD2;
else
tt9+=tt4*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t2;
if(i%2)
t9+=t5;
else
t9+=t6;
if((j-i)%2)
t9+=t4*mod1[j*2]%MOD1;
else
t9+=t3*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt2;
if(i%2)
tt9+=tt5;
else
tt9+=tt6;
if((j-i)%2)
tt9+=tt4*mod2[j*2]%MOD2;
else
tt9+=tt3*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t3;
if((N-j)%2)
t9+=t8;
else
t9+=t7;
if((j-i)%2)
t9+=t1*mod1[(N-i)*2]%MOD1;
else
t9+=t2*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt3;
if((N-j)%2)
tt9+=tt8;
else
tt9+=tt7;
if((j-i)%2)
tt9+=tt1*mod2[(N-i)*2]%MOD2;
else
tt9+=tt2*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t4;
if((N-j)%2)
t9+=t7;
else
t9+=t8;
if((j-i)%2)
t9+=t2*mod1[(N-i)*2]%MOD1;
else
t9+=t1*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt4;
if((N-j)%2)
tt9+=tt7;
else
tt9+=tt8;
if((j-i)%2)
tt9+=tt2*mod2[(N-i)*2]%MOD2;
else
tt9+=tt1*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
return;
}
void insert(int x,int y){
int bucket=(x+y)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return;
t=t->next;
}
t=(node*)malloc(sizeof(node));
t->x=x;
t->y=y;
t->next=hash[bucket];
hash[bucket]=t;
hash_count++;
return;
}
void freehash(){
int i;
node *t,*p;
for(i=0;i<HASH_SIZE;i++){
t=hash[i];
while(t){
p=t->next;
free(t);
t=p;
}
hash[i]=NULL;
}
return;
}
long long modInverse(long long a,long long mod){
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while (a > 1) {
q = a / mod;
t = mod; mod = a % mod; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
