Table of Contents
Separate the chocolate – 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++ replace HackerRank Solution
#include <cstdio>
#include <string>
#include <map>
#include <cstring>
#include <cassert>
using namespace std;
typedef unsigned long long llu;
struct node {
int num; // black - white
char a[9]; //the number of the grid even-white odd-black
char no; //the forbideen color the 0-white 1-black 2-both can
char vwb; //the valid color 0-white 1-black 2-both 3-neither
char dwb; //0-dead white (Never can appear a white grid) 1-dead black 3-neither dead
};
int m,n,last,now,pp,un;
llu ans;
char s[10][10];
inline bool operator<(const node &a,const node &b) {
if (a.no < b.no) {
return true;
}
if (a.no > b.no) {
return false;
}
if (a.dwb < b.dwb) {
return true;
}
if (a.dwb > b.dwb) {
return false;
}
if (a.vwb < b.vwb) {
return true;
}
if (a.vwb > b.vwb) {
return false;
}
if (a.num<b.num) {
return true;
}
if (a.num>b.num) {
return false;
}
for (int i = 0;i < n;++i) {
if (a.a[i] < b.a[i]) {
return true;
}
if (a.a[i] > b.a[i]) {
return false;
}
}
return false;
}
map<node,llu> save[2];
inline bool iswhite(int x) {
return !(x & 1);
}
inline bool isblack(int x) {
return (x & 1);
}
void makelone(node &temp,int y,int x,int n) {
int i,j,z = (y << 1) + x;
temp.a[y] = z;
z = (y << 1);
for (i = y + 1;i < n;++i) {
if (temp.a[i] == z) {
break;
}
}
for (j = i,i <<= 1; j < n; ++j) {
if (temp.a[j] == z) {
temp.a[j] = i;
}
}
z = (y << 1) | 1;
for (i = y + 1;i < n;++i) {
if (temp.a[i] == z) {
break;
}
}
for (j = i,i = (i << 1) | 1;j < n;++j) {
if (temp.a[j] == z) {
temp.a[j] = i;
}
}
}
void makeunion(node &temp,int x,int y,int n) {
if (x < y) {
x ^= y ^= x ^= y;
}
for (int i = 0; i < n;++i) {
if (temp.a[i] == x) {
temp.a[i] = y;
}
}
}
void makewhite(int x,int y,node temp,llu ans,int add) {
bool yes;
int i,j,k,ll,uu;
map<node,llu>::iterator t;
if ((temp.no == 0) || (temp.dwb == 0)) {
return;
}
temp.num += add;
if ((temp.num + un < -pp) || (temp.num - un > pp)) {
return;
}
yes = (temp.dwb == 1);
if ((x) && (temp.a[y] == ((y << 1) | 1))) { //above is the head of black
for (i = y + 1;i < n;++i) {
if (temp.a[i] == temp.a[y]) {
break;
}
}
if (i >= n) {
if ((temp.vwb != 1) && (temp.vwb != 2)) { //make black dead
return;
}
yes = true;
}
}
ll = ((y) && iswhite(temp.a[y - 1]))?temp.a[y - 1]:(-1);
uu = ((x) && iswhite(temp.a[y]))?temp.a[y]:(-1);
k = x?n:(y + 1);
if (uu < 0) {
makelone(temp, y,0 ,k);
if (ll >= 0) {
temp.a[y] = ll;
}
}
else if ((ll >= 0) && (ll != uu)) {
makeunion(temp,ll,uu,k);
}
for (i = j = 0;i < k;++i) {
if ((temp.a[i]== (i<<1)) && (++j > 1)) {
break;
}
}
if (j == 1) {
temp.vwb = ((temp.vwb == 1) || (temp.vwb == 2))?2:0;
}
else { //j > 1
temp.vwb = ((temp.vwb == 1) || (temp.vwb == 2))?1:3;
}
temp.dwb = yes?1:3;
temp.no = ((uu >= 0) && (y + 1 < n) && ((temp.a[y + 1] & 1) == 0))?0:2;
save[now][temp] += ans;
}
void makeblack(int x,int y,node temp,llu ans,int add) {
bool yes;
int i,j,k,ll,uu;
map<node,llu>::iterator t;
if ((temp.no == 1) || (temp.dwb == 1)) {
return;
}
temp.num += add;
if ((temp.num + un < -pp) || (temp.num - un > pp)) {
return;
}
yes = (temp.dwb == 0);
if ((x) && (temp.a[y]==(y << 1))) { //above is the head of white
for (i = y + 1;i < n;++i) {
if (temp.a[i] == temp.a[y]) {
break;
}
}
if (i >= n) {
if ((temp.vwb != 0) && (temp.vwb != 2)) { ///make black dead
return;
}
yes = true;
}
}
ll = ((y) && isblack(temp.a[ y - 1]))?temp.a[y - 1]:(-1);
uu = ((x) && isblack(temp.a[y]))?temp.a[y]:(-1);
k = x?n:(y + 1);
if (uu < 0) {
makelone(temp,y,1,k);
if (ll >= 0) {
temp.a[y] = ll;
}
}
else if ((ll >= 0) && (ll != uu)) {
makeunion(temp,ll,uu,k);
}
for (i = j = 0;i < k;++i) {
if ((temp.a[i]==((i << 1) | 1)) && (++j > 1)) {
break;
}
}
if (j == 1) {
temp.vwb = ((temp.vwb==0) || (temp.vwb==2))?2:1;
}
else { //j>1
temp.vwb = ((temp.vwb==0) || (temp.vwb==2))?0:3;
}
temp.dwb = yes?0:3;
temp.no = ((uu >= 0) && (y + 1 < n) && ((temp.a[ y + 1] & 1) == 1))?1:2;
save[now][temp] += ans;
}
int main() {
int z;
node temp;
scanf("%d%d%d",&m,&n,&pp);
assert(0 <= m && m <= 8);
assert(0 <= n && n <= 8);
assert(0 <= pp <= m*n);
memset(temp.a,0,sizeof(temp.a));
temp.num = 0;
temp.no = temp.vwb = 2;
temp.dwb = 3;
save[0].clear();
un = 0;
for (int i = 0;i < m;++i) {
scanf("%s",s[i]);
for (int j = 0; j < n; ++j) {
if (s[i][j] == 'T') {
++temp.num;
}
else if (s[i][j] == 'D') {
--temp.num;
}
else {
++un;
}
}
}
save[last = 0][temp] = 1;
//printf("un = %d\n",un);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n;++j) {
save[now = 1 ^ last].clear();
if (s[i][j] == 'U') {
--un;
}
for (map<node,llu>::iterator t = save[last].begin();t != save[last].end();++t) {
if (s[i][j] == 'T') {
makeblack(i,j,t->first,t->second, 0);
}
else if (s[i][j] == 'D') {
makewhite(i,j,t->first,t->second, 0);
}
else {
makeblack(i,j,t->first,t->second, 1);
makewhite(i,j,t->first,t->second, -1);
}
}
last = now;
}
}
ans = 0;
//printf("un = %d\n",un);
assert(un == 0);
for (map<node,llu>::iterator t = save[last].begin();t != save[last].end();++t) {
if (t->first.vwb == 2) {
assert((t->first.num >= -pp) && (t->first.num <= pp));
//printf("%d %llu\n",t->first.num, t->second);
ans += t->second;
}
}
printf("%llu\n",ans);
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int T = 0;
static int D = 1;
static int U = -1;
static class Cell {
int piece; //0..1
int groupIndex; //0...
public Cell(int piece, int groupIndex) {
this.piece = piece;
this.groupIndex = groupIndex;
}
public String toString() {
if(piece == 0) {
return "" + (char)('a' + groupIndex);
} else {
return "" + (char)('A' + groupIndex);
}
}
public boolean equals(Object o) {
Cell other = (Cell)o;
return piece == other.piece && groupIndex == other.groupIndex;
}
public int hashCode() {
return 31 * piece + groupIndex;
}
public Cell copy() {
return new Cell(piece, groupIndex);
}
}
static class LineState {
Cell[] cells;
boolean isHidingGroup = false;
public LineState(Cell[] cells) {
this.cells = cells.clone();
}
public LineState(int template, int width) {
cells = new Cell[width];
for (int i = 0; i < width; i++) {
cells[i] = new Cell(template % 2, -1);
template /= 2;
}
}
public boolean isMatch(int[] constraint) {
for (int i = 0; i < cells.length; i++) {
if(constraint[i] >= 0 && constraint[i] != cells[i].piece) {
return false;
}
}
return true;
}
public int countOnes() {
int c = 0;
for (int i = 0; i < cells.length; i++) {
c += cells[i].piece;
}
return c;
}
public boolean isOfTwoPieces() {
if(isHidingGroup && isUniform()) return true;
for (int i = 0; i < cells.length; i++) {
if(cells[i].groupIndex > 0) return false;
}
return true;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (Cell c: cells) {
sb.append(c);
}
if(isHidingGroup) sb.append("!");
return sb.toString();
}
public boolean equals(Object o) {
LineState other = (LineState)o;
return toString().equals(other.toString());
}
public LineState copy() {
Cell[] cs = new Cell[cells.length];
for (int i = 0; i < cs.length; i++) {
cs[i] = cells[i].copy();
}
LineState copy = new LineState(cs);
copy.isHidingGroup = isHidingGroup;
return copy;
}
boolean isUniform() {
int p = cells[0].piece;
for (int i = 1; i < cells.length; i++) {
if(cells[i].piece != p) return false;
}
return true;
}
public void revalidate() {
int g0 = 20;
int g1 = 20;
for (int i = 0; i < cells.length; i++) {
int g = cells[i].groupIndex;
if(g >= 0) continue;
int p = cells[i].piece;
if(p == 0) {
for (int j = i; j < cells.length && cells[j].piece == p && cells[j].groupIndex < 0; j++) {
cells[j].groupIndex = g0;
}
g0++;
} else {
for (int j = i; j < cells.length && cells[j].piece == p && cells[j].groupIndex < 0; j++) {
cells[j].groupIndex = g1;
}
g1++;
}
}
int[] m0 = new int[cells.length + 20];
int[] m1 = new int[cells.length + 20];
for (int i = 0; i < m0.length; i++) {
m0[i] = -1;
m1[i] = -1;
}
g0 = 0;
g1 = 0;
for (int i = 0; i < cells.length; i++) {
int g = cells[i].groupIndex;
if(g < 0) continue;
if(cells[i].piece == 0) {
if(m0[g] >= 0) {
cells[i].groupIndex = m0[g];
} else {
m0[g] = g0;
cells[i].groupIndex = g0;
g0++;
}
} else {
if(m1[g] >= 0) {
cells[i].groupIndex = m1[g];
} else {
m1[g] = g1;
cells[i].groupIndex = g1;
g1++;
}
}
}
}
}
int width;
int height;
int diff;
int[][] constraint;
Map<String, LineState> states = new HashMap<>();
Map<String, Set<String>> transfers = new HashMap<>();
Map<String, Map<Integer,Long>> counts = new HashMap<>();
public void setSize(int width, int height, int diff) {
this.width = width;
this.height = height;
this.diff = diff;
}
public void setConstraint(int[][] constraint) {
this.constraint = constraint;
}
public List<LineState> createState() {
List<LineState> states = new ArrayList<>();
int t = 0;
Cell[] cells = new Cell[width];
int[] way = new int[width + 1];
int[] wayCount = new int[width + 1];
Cell[][] ways = new Cell[width + 1][width + 1];
ways[0][0] = new Cell(0, 0);
ways[0][1] = new Cell(1, 0);
wayCount[0] = 2;
way[t] = -1;
while(true) {
while(way[t] == wayCount[t] - 1) {
if(t == 0) return states;
t--;
}
way[t]++;
cells[t] = ways[t][way[t]];
t++;
wayCount[t] = 0;
if(t < width) {
int p = cells[t-1].piece;
ways[t][0] = new Cell(p, cells[t-1].groupIndex); //same
wayCount[t]++;
List<Cell> gStack = new ArrayList<>();
int g = -1;
for (int i = 0; i < t; i++) {
int j = gStack.indexOf(cells[i]);
if(j >= 0) {
while(gStack.size() > j + 1) gStack.remove(gStack.size() - 1);
} else {
gStack.add(cells[i]);
if(cells[i].piece == 1 - p) {
if(cells[i].groupIndex > g) g = cells[i].groupIndex;
}
}
}
for (Cell c: gStack) {
if(c.piece == 1 - p) {
ways[t][wayCount[t]] = c;
wayCount[t]++;
}
}
ways[t][wayCount[t]] = new Cell(1-p, g+1);
wayCount[t]++;
} else {
states.add(new LineState(cells));
}
way[t] = -1;
}
}
//to - template
public LineState transfer(LineState from, LineState to) {
if(from.isHidingGroup) {
if(width == 1 && from.cells[0].piece == to.cells[0].piece) {
to = to.copy();
to.isHidingGroup = true;
to.revalidate();
return to;
}
return null;
}
for (int i = 0; i < from.cells.length - 1; i++) {
int p = from.cells[i].piece;
if(p == from.cells[i + 1].piece && p == to.cells[i].piece
&& p == to.cells[i + 1].piece) {
return null; //square 2x2
}
}
from = from.copy();
to = to.copy();
for (int i = 0; i < from.cells.length; i++) {
to.cells[i].groupIndex = -1;
}
for (int i = 0; i < from.cells.length; i++) {
int p = from.cells[i].piece;
int g1 = from.cells[i].groupIndex;
int g2 = to.cells[i].groupIndex;
if(p == to.cells[i].piece && g1 != g2) {
if(g2 >= 0) {
for (int j = 0; j < from.cells.length; j++) {
int ga = (g1 < g2) ? g1 : g2;
int gb = (g1 > g2) ? g1 : g2;
if(p == from.cells[j].piece && gb == from.cells[j].groupIndex) {
from.cells[j].groupIndex = ga;
}
if(p == to.cells[j].piece && gb == to.cells[j].groupIndex) {
to.cells[j].groupIndex = ga;
}
}
} else {
to.cells[i].groupIndex = g1;
int j = i + 1;
while(j < from.cells.length && to.cells[j].piece == p) {
to.cells[j].groupIndex = g1;
j++;
}
j = i - 1;
while(j >= 0 && to.cells[j].piece == p) {
to.cells[j].groupIndex = g1;
j--;
}
}
}
}
Set<Cell> accounted = new HashSet<>();
for (int i = 0; i < from.cells.length; i++) {
if(from.cells[i].piece == to.cells[i].piece) {
accounted.add(from.cells[i]);
}
}
Set<Cell> unaccounted = new HashSet<>();
for (int i = 0; i < from.cells.length; i++) {
if(!accounted.contains(from.cells[i]) && !unaccounted.contains(from.cells[i])) {
unaccounted.add(from.cells[i]);
}
}
if(unaccounted.size() > 1) return null;
to.revalidate();
if(unaccounted.size() == 1) {
if(!to.isUniform()) {
return null;
} else {
to.isHidingGroup = true;
}
}
return to;
}
public void build() {
int p2 = 1;
for (int i = 0; i < width; i++) p2 *= 2;
List<LineState> states = createState();
for (LineState s: states) {
this.states.put(s.toString(), s);
if(s.isUniform()) {
LineState s1 = s.copy();
s1.isHidingGroup = true;
this.states.put(s1.toString(), s1);
}
}
for (LineState s: this.states.values()) {
Set<String> ts = new HashSet<>();
for (int i = 0; i < p2; i++) {
LineState t = new LineState(i, width);
t = transfer(s, t);
if(t != null) ts.add(t.toString());
}
transfers.put(s.toString(), ts);
}
for (int i = 0; i < p2; i++) {
LineState t = new LineState(i, width);
t.revalidate();
if(!t.isMatch(constraint[0])) continue;
Map<Integer, Long> v = new HashMap<>();
v.put(t.countOnes(), 1l);
counts.put(t.toString(), v);
}
for (int i = 0; i < height - 1; i++) {
counts = addRow(counts, constraint[i+1]);
}
long sum = sum(counts, diff, width * height);
System.out.println(sum);
}
Map<String, Map<Integer,Long>> addRow(Map<String, Map<Integer,Long>> counts, int[] cs) {
Map<String, Map<Integer,Long>> next = new HashMap<>();
for (String s: counts.keySet()) {
Map<Integer, Long> vs = counts.get(s);
for (String n: transfers.get(s)) {
LineState t = states.get(n);
if(!t.isMatch(cs)) continue;
int dk = t.countOnes();
if(!next.containsKey(n)) {
Map<Integer, Long> v = new HashMap<>();
for (int k: vs.keySet()) {
v.put(k + dk, vs.get(k));
}
next.put(n, v);
} else {
Map<Integer, Long> v = next.get(n);
for (int k: vs.keySet()) {
if(!v.containsKey(k + dk)) {
v.put(k + dk, vs.get(k));
} else {
v.put(k + dk, v.get(k + dk) + vs.get(k));
}
}
}
}
}
return next;
}
long sum(Map<String, Map<Integer,Long>> counts, int diff, int size) {
long result = 0;
for (String s: counts.keySet()) {
LineState state = states.get(s);
if(state.isOfTwoPieces()) {
for (int k: counts.get(s).keySet()) {
int k1 = size - k;
if(Math.abs(k - k1) <= diff) {
long d = counts.get(s).get(k);
result += d;
}
}
}
}
return result;
}
public void run() {
Scanner in = new Scanner(System.in);
int m = in.nextInt(), n = in.nextInt(), k = in.nextInt();
if(m == 0 || n == 0) {
System.out.println(1);
return;
}
// in.next();
setSize(n, m, k);
int[][] cs = new int[m][n];
for (int i = 0; i < m; i++) {
String s = in.next();
for (int j = 0; j < n; j++) {
char ch = s.charAt(j);
cs[i][j] = ch == 'T' ? T : ch == 'D' ? D : U;
}
}
setConstraint(cs);
build();
}
public static void main(String[] args) {
new Solution().run();
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
from collections import defaultdict
M, N, K = (int(s) for s in raw_input().split())
sa=[]
D=[]
T=[]
max_d=-1
max_t=-1
for i in range(M):
sa.append(raw_input())
if (N>M):
sa=map(''.join ,zip(*sa))
N,M=M,N
if (N==1):
sa=map(''.join ,zip(*sa))
N,M=M,N
for i in range(M):
s=sa[i][:N]
sd = s
st = s
sd = sd.replace("U","0")
sd = sd.replace("D","1")
sd = sd.replace("T","0")
if int(sd,2)!=0:
max_d=i
D.append(int(sd,2))
st = st.replace("U","0")
st = st.replace("D","0")
st = st.replace("T","1")
if int(sd,2)!=0:
max_t=i
T.append(int(st,2))
if (N%2==0)and(M%2==0):
max_K = (N+M-1)
else:
max_K = (N+M+1)
max_K = max(max_K,4)
do_K = (K<max_K)
def transfer(prev_comb, comb_compact):
temp_comb_compact=comb_compact
comb=[]
for _ in range(N):
comb.append(2*(temp_comb_compact%2)-1)
temp_comb_compact /=2
if prev_comb:
label0_prev=-min(min(prev_comb),0)
label1_prev=max(max(prev_comb),0)
else:
prev_comb=[0]*N
label0_prev=0
label1_prev=0
N_full=N+label0_prev+label1_prev+1
N_half=N+label0_prev
label = [0]*N_full
adj = [[] for _ in range(N_full)]
for i in range(N-1):
if comb[i]*comb[i+1]>0:
adj[i].append(i+1)
adj[i+1].append(i)
if (prev_comb[i]*prev_comb[i+1]>0)and(comb[i]*prev_comb[i]>0):
return []
for i in range(N):
prev_level = prev_comb[i]
if comb[i]*prev_level>0:
adj[i].append(N_half+prev_level)
adj[N_half+prev_level].append(i)
plus_label=0
minus_label=0
for i in range(N):
if not(label[i])and(comb[i]!=0):
if comb[i]>0:
plus_label += 1
current_label = plus_label
elif comb[i]<0:
minus_label -= 1
current_label =minus_label
label[i] = current_label
q=[]
q.append(i)
while q:
node = q.pop()
for node_neighbour in adj[node]:
if not label[node_neighbour]:
label[node_neighbour] = current_label
q.append(node_neighbour)
if (label0_prev>0)and(max(label[N:N_half])==0)and((label0_prev>1)or((label0_prev==1)and(minus_label!=0))):
return []
if (label1_prev>0)and(min(label[N_half+1:N_full])==0)and((label1_prev>1)or((label1_prev==1)and(plus_label!=0))):
return []
return (tuple(label[:N]))
transfer_matrix=[]
transfer_matrix_end=[]
label_to_index={}
number_of_comb=[]
end_labels =[]
def build_transfer_matrix():
N_labels = 0
pow2N=pow(2,N)
queue_to_process = []
for comb in range(pow2N):
labeled_comb = transfer([], comb)
if labeled_comb:
label_to_index[labeled_comb] = N_labels
if (max(labeled_comb)<=1)and(min(labeled_comb)>=-1):
end_labels.append(N_labels)
queue_to_process.append([labeled_comb, N_labels])
N_labels+=1
transfer_matrix.append([])
transfer_matrix_end.append([])
if (comb&T[0]!=0)or(~comb&D[0]!=0):
number_of_comb.append(0)
else:
number_of_comb.append(1)
while queue_to_process:
prev = queue_to_process.pop()
prev_label = prev[0]
prev_index = prev[1]
for comb in range(pow2N):
labeled_comb = transfer(prev_label, comb)
if labeled_comb:
if labeled_comb not in label_to_index:
label_to_index[labeled_comb] = N_labels
if (max(labeled_comb)<=1)and(min(labeled_comb)>=-1):
end_labels.append(N_labels)
queue_to_process.append([labeled_comb, N_labels])
next_index = N_labels
N_labels+=1
transfer_matrix.append([])
transfer_matrix_end.append([])
number_of_comb.append(0)
else:
next_index = label_to_index[labeled_comb]
if (comb == 0)or(comb==pow2N-1):
transfer_matrix_end[prev_index].append([next_index,comb])
else:
transfer_matrix[prev_index].append([next_index,comb])
build_transfer_matrix()
if do_K:
K_lt = [2*bin(i).count("1")-N for i in range(pow(2,N))]
prev_number_of_comb= number_of_comb
number_of_comb=[[0]*(2*max_K+1) for _ in range(len(number_of_comb))]
for comb in range(pow(2,N)):
number_of_comb[comb][K_lt[comb]+max_K]=prev_number_of_comb[comb]
for row in range(1,M):
prev_number_of_comb= number_of_comb
number_of_comb=[[0]*(2*max_K+1) for _ in range(len(number_of_comb))]
for prev_id in range(len(transfer_matrix)):
for K_id in range(2*max_K+1):
if prev_number_of_comb[prev_id][K_id]:
for next_id,next_comb in transfer_matrix[prev_id]:
if (next_comb&T[row]==0)and(~next_comb&D[row]==0)and(abs(K_id-max_K+K_lt[next_comb])<=max_K):
number_of_comb[next_id][K_id+K_lt[next_comb]]+=prev_number_of_comb[prev_id][K_id]
if row==M-1:
for prev_id in range(len(transfer_matrix_end)):
for K_id in range(2*max_K+1):
if transfer_matrix_end[prev_id]:
for next_id,next_comb in transfer_matrix_end[prev_id]:
if (next_comb&T[M-1]==0)and(~next_comb&D[M-1]==0) and (abs(K_id-max_K+K_lt[next_comb])<=max_K):
number_of_comb[next_id][K_id+K_lt[next_comb]]+=prev_number_of_comb[prev_id][K_id]
final_sum=0
for end_id in end_labels:
for K_id in range(2*max_K+1):
if abs(K_id-max_K)<=K:
final_sum+=number_of_comb[end_id][K_id]
print final_sum
else:
for row in range(1,M):
prev_number_of_comb= number_of_comb
number_of_comb=[0]*len(number_of_comb)
for prev_id in range(len(transfer_matrix)):
if prev_number_of_comb[prev_id]:
for next_id,next_comb in transfer_matrix[prev_id]:
if (next_comb&T[row]==0)and(~next_comb&D[row]==0):
number_of_comb[next_id]+=prev_number_of_comb[prev_id]
if row==M-1:
for prev_id in range(len(transfer_matrix_end)):
if transfer_matrix_end[prev_id]:
for next_id,next_comb in transfer_matrix_end[prev_id]:
if (next_comb&T[M-1]==0)and(~next_comb&D[M-1]==0):
number_of_comb[next_id]+=prev_number_of_comb[prev_id]
final_sum=0
for end_id in end_labels:
final_sum+=number_of_comb[end_id]
print final_sum
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 123455
typedef struct _node{
int mask;
int group;
int r1;
int r2;
long long c;
struct _node *next;
} node;
void insert(node **hash,int m,int g,int r1,int r2,long long c);
long long find(node **hash,int m,int g,int r1,int r2);
int hash_f(int m,int g,int r1,int r2);
long long solve(int l,int m,int g,int r1,int r2,int all);
int count(int i);
char table[8][9];
int N,M,T[8]={0},D[8]={0},dp[256][256],dl[256]={0};
node *hash[8][HASH_SIZE]={0};
int main(){
int K,i,j,k;
scanf("%d%d%d",&N,&M,&K);
for(i=0;i<N;i++)
scanf("%s",&table[i][0]);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
if(table[i][j]=='T')
T[i]|=(1<<j);
else if(table[i][j]=='D')
D[i]|=(1<<j);
for(i=0;i<(1<<M);i++)
for(j=0;j<(1<<M);j++){
for(k=1;k<M;k++)
if((i&(1<<k))==((i&(1<<(k-1)))<<1)&&(i&(1<<k))==(j&(1<<k))&&(i&(1<<k))==((j&(1<<(k-1)))<<1))
break;
if(k==M)
dp[i][dl[i]++]=j;
}
printf("%lld",solve(N,0,0,-K,K,0));
return 0;
}
void insert(node **hash,int m,int g,int r1,int r2,long long c){
int bucket=hash_f(m,g,r1,r2)%HASH_SIZE;
node *t=hash[bucket];
t=(node*)malloc(sizeof(node));
t->mask=m;
t->group=g;
t->r1=r1;
t->r2=r2;
t->c=c;
t->next=hash[bucket];
hash[bucket]=t;
return;
}
long long find(node **hash,int m,int g,int r1,int r2){
int bucket=hash_f(m,g,r1,r2)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->mask==m && t->group==g && t->r1==r1 && t->r2==r2)
return t->c;
t=t->next;
}
return -1;
}
int hash_f(int m,int g,int r1,int r2){
return m+g*256+(r1+64)*256+r2+64;
}
long long solve(int l,int m,int g,int r1,int r2,int all){
int i,j,k,G,ct,cg,mtg,mgg,diff,temp,temp2,tm[8],gm[8],ts,gs,group[8],group2[8],tma[4],gma[4],tmm[4],gmm[4];
long long t;
if(all){
if(!l){
if(g || r1>0 || r2<0)
return 0;
return 1;
}
if(M>1)
return 0;
if(m){
if(D[l-1])
return 0;
return solve(l-1,m,g,r1-1,r2-1,all);
}
else{
if(T[l-1])
return 0;
return solve(l-1,m,g,r1+1,r2+1,all);
}
}
if(r1>l*M || r2<-l*M)
return 0;
if(r2>l*M)
r2=l*M;
if(r1<-l*M)
r1=-l*M;
if(l!=N && l){
t=find(&hash[l][0],m,g,r1,r2);
if(t!=-1)
return t;
}
else if(l==N){
for(i=t=0;i<(1<<M);i++){
if((D[l-1]&i) || (T[l-1]&(~i)))
continue;
diff=2*count(i)-M;
for(j=ts=gs=0;j<M;j++)
if(j && (i&(1<<j))==((i&(1<<(j-1)))<<1))
group[j]=group[j-1];
else{
if(i&(1<<j))
group[j]=ts++;
else
group[j]=gs++;
}
for(j=temp2=0,ts=1;j<M;j++,ts*=4)
temp2+=group[j]*ts;
t+=solve(l-1,i,temp2,r1-diff,r2-diff,0);
}
return t;
}
if(l){
G=g;
mtg=mgg=0;
for(j=0;j<M;g/=4,j++){
group[j]=g%4;
if(m&(1<<j)){
if(group[j]>mtg)
mtg=group[j];
}
else{
if(group[j]>mgg)
mgg=group[j];
}
}
for(i=t=0;i<dl[m];i++){
if((D[l-1]&dp[m][i]) || (T[l-1]&(~dp[m][i])))
continue;
temp2=all=ct=cg=0;
diff=2*count(dp[m][i])-M;
memset(tm,-1,sizeof(tm));
memset(gm,-1,sizeof(gm));
memset(tma,0,sizeof(tma));
memset(gma,0,sizeof(gma));
memset(tmm,-1,sizeof(tma));
memset(gmm,-1,sizeof(gma));
for(j=0,ts=gs=4;j<M;j++)
if(j && (dp[m][i]&(1<<j))==((dp[m][i]&(1<<(j-1)))<<1))
group2[j]=group2[j-1];
else{
if(dp[m][i]&(1<<j))
group2[j]=ts++;
else
group2[j]=gs++;
}
for(j=0;j<M;j++)
if((dp[m][i]&(1<<j))==(m&(1<<j))){
if(m&(1<<j)){
if(tmm[group[j]]==-1 && group2[j]>=4){
tmm[group[j]]=group[j];
temp=group2[j];
for(k=0;k<M;k++)
if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
group2[k]=group[j];
}
else if(tmm[group[j]]==-1)
tmm[group[j]]=group2[j];
else if(tmm[group[j]]!=-1 && group2[j]>=4){
temp=group2[j];
for(k=0;k<M;k++)
if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
group2[k]=tmm[group[j]];
}
else if(tmm[group[j]]!=-1 && tmm[group[j]]!=group2[j]){
temp=tmm[group[j]];
tmm[group[j]]=group2[j];
for(k=0;k<M;k++)
if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
group2[k]=group2[j];
}
}
else{
if(gmm[group[j]]==-1 && group2[j]>=4){
gmm[group[j]]=group[j];
temp=group2[j];
for(k=0;k<M;k++)
if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
group2[k]=group[j];
}
else if(gmm[group[j]]==-1)
gmm[group[j]]=group2[j];
else if(gmm[group[j]]!=-1 && group2[j]>=4){
temp=group2[j];
for(k=0;k<M;k++)
if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
group2[k]=gmm[group[j]];
}
else if(gmm[group[j]]!=-1 && gmm[group[j]]!=group2[j]){
temp=gmm[group[j]];
gmm[group[j]]=group2[j];
for(k=0;k<M;k++)
if(group2[k]==temp && ((dp[m][i]&(1<<k))>>k)==((m&(1<<j))>>j))
group2[k]=group2[j];
}
}
}
for(j=ts=gs=0;j<M;j++)
if(dp[m][i]&(1<<j))
if(tm[group2[j]]==-1){
tm[group2[j]]=ts++;
group2[j]=ts-1;
}
else
group2[j]=tm[group2[j]];
else
if(gm[group2[j]]==-1){
gm[group2[j]]=gs++;
group2[j]=gs-1;
}
else
group2[j]=gm[group2[j]];
for(j=0;j<M;j++)
if(m&(1<<j)){
if((m&(1<<j))==(dp[m][i]&(1<<j)))
tma[group[j]]=1;
}
else{
if((m&(1<<j))==(dp[m][i]&(1<<j)))
gma[group[j]]=1;
}
for(j=0;j<M;j++)
if(m&(1<<j)){
if(!tma[group[j]]){
if(dp[m][i])
temp2=1;
else
all=1;
}
}
else{
if(!gma[group[j]]){
if(dp[m][i]!=((1<<M)-1))
temp2=1;
else
all=1;
}
}
for(j=0;j<=mtg;j++){
if(!tma[j])
ct++;
}
for(j=0;j<=mgg;j++){
if(!gma[j])
cg++;
}
if(ct>1 || cg>1 || temp2)
continue;
for(j=temp=0,ts=1;j<M;j++,ts*=4)
temp+=group2[j]*ts;
t+=solve(l-1,dp[m][i],temp,r1-diff,r2-diff,all);
}
insert(&hash[l][0],m,G,r1,r2,t);
return t;
}
if(g || r1>0 || r2<0)
return 0;
return 1;
}
int count(int i){
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
