Table of Contents
Clues on a Binary Path – 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++ Clues on a Binary Path HackerRank Solution
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int N = 99;
const int L = 13;
int n, m, l;
bool used[(1 << 20) + 100];
bool canMake[N][(1 << 10) + 100];
bool f[N][N][L][(1 << 10) + 100];
vector< pair<int, int> > g[N];
int main() {
scanf("%d%d%d", &n, &m, &l);
for (int i = 1; i <= m; i++) {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
g[u].pb(mp(v, c));
g[v].pb(mp(u, c));
}
queue<int> q_start, q_ver, q_len, q_mask;
for (int i = 1; i <= n; i++) {
f[i][i][0][0] = true;
q_start.push(i);
q_ver.push(i);
q_len.push(0);
q_mask.push(0);
}
int maxMoves = (l + 1) / 2;
while (!q_start.empty()) {
int start = q_start.front();
int ver = q_ver.front();
int len = q_len.front();
int mask = q_mask.front();
q_start.pop(); q_ver.pop(); q_len.pop(); q_mask.pop();
if (len == maxMoves) {
continue;
}
for (int i = 0; i < (int)g[ver].size(); i++) {
int to = g[ver][i].F;
int bit = g[ver][i].S;
int newMask = mask;
if (bit == 1) {
newMask += (1 << len);
}
if (f[start][to][len + 1][newMask] == false) {
f[start][to][len + 1][newMask] = true;
q_start.push(start);
q_ver.push(to);
q_len.push(len + 1);
q_mask.push(newMask);
}
}
}
int maxMask = (1 << maxMoves);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int mask = 0; mask < maxMask; mask++) {
if (f[i][j][maxMoves][mask]) {
canMake[j][mask] = true;
}
}
}
}
int lengthOfFirstPart = l - maxMoves;
int maxMask2 = (1 << lengthOfFirstPart);
for (int ver = 1; ver <= n; ver++) {
for (int m1 = 0; m1 < maxMask2; m1++) {
if (f[1][ver][lengthOfFirstPart][m1]) {
for (int m2 = 0; m2 < maxMask; m2++) {
if (canMake[ver][m2]) {
used[(m1 << maxMoves) + m2] = true;
}
}
}
}
}
int ans = 0;
int maxMaskOverall = (1 << l);
for (int i = 0; i < maxMaskOverall; i++) {
if (used[i]) {
++ans;
}
}
printf("%d\n", ans);
return 0;
}
Java Clues on a Binary Path HackerRank Solution
import java.io.*;
import java.util.StringTokenizer;
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int n = in.nextInt();
int m = in.nextInt();
int d = in.nextInt();
if (
!(1 <= n && n <= 70) ||
!(0 <= m && m <= n * (n - 1)) ||
!(1 <= d && d <= 20))
throw new RuntimeException();
int[] x = new int[m];
int[] y = new int[m];
int[] w = new int[m];
for (int i = 0; i < m; ++i) {
x[i] = in.nextInt(); x[i]--;
y[i] = in.nextInt(); y[i]--;
if (!(0 <= x[i] && x[i] < n) || !(0 <= y[i] && y[i] < n))
throw new RuntimeException();
w[i] = in.nextInt();
if (!(0 <= w[i] && w[i] <= 1))
throw new RuntimeException();
}
int l = (d + 1) / 2;
int[][] dp = new int[n][1 << l];
int[][] ndp = new int[n][1 << l];
for (int i = 0; i < n; ++i)
for (int j = 0; j < (1 << l); ++j)
dp[i][j] = ndp[i][j] = 0;
dp[0][0] = 1;
for (int i = 0; i < n; ++i)
dp[i][0] |= 2;
for (int c = 0; c < l; ++c) {
for (int i = 0; i < m; ++i) {
int u = x[i];
int v = y[i];
int b = w[i];
for (int t = 0; t < (1 << c); ++t) {
ndp[u][(t << 1) | b] |= dp[v][t];
ndp[v][(t << 1) | b] |= dp[u][t];
}
}
if (c + 1 < l) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (1 << (c + 1)); ++j) {
dp[i][j] = ndp[i][j];
ndp[i][j] = 0;
}
}
}
}
Boolean[] can = new Boolean[1 << d];
for (int i = 0; i < (1 << d); ++i)
can[i] = false;
int r = d - l;
for (int v = 0; v < n; ++v) {
for (int t = 0; t < (1 << r); ++t) {
int c = (l == r ? ndp[v][t] : dp[v][t]);
if ((c & 1) == 0)
continue;
for (int s = 0; s < (1 << l); ++s) {
if ((ndp[v][s] & 2) > 0)
can[(t << l) ^ s] = true;
}
}
}
int res = 0;
for (int i = 0; i < (1 << d); ++i)
if (can[i])
res++;
out.println(res);
out.close();
}
}
class InputReader {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String nextLine() {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(nextLine());
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
Python 3 Clues on a Binary Path HackerRank Solution
Suggest in comments
Python 2 Clues on a Binary Path HackerRank Solution
Suggest in comments
C Clues on a Binary Path HackerRank Solution
Suggest in comments
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
