Table of Contents
Road Maintenance – 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++ Road Maintenance HackerRank Solution
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#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))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt() : x(0) {}
ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;
int M;
vector<vector<int> > g;
vector<mint> memo;
mint rec(int i, int j, int p, int d1s, int m) {
if(d1s > M)
return mint();
if(j == g[i].size())
return m == 0 ? 1 : 0;
if(g[i][j] == p)
return rec(i, j + 1, p, d1s, m);
int c = g[i][j];
mint &r = memo[(c * (M + 1) + d1s) * (M + 1) + m];
if(r.x != -1)
return r;
r = mint();
rer(n, 0, m) {
r +=
rec(c, 0, i, 0, n) *
rec(i, j + 1, p, d1s, m - n);
}
rer(n, 0, m - 1) {
r +=
rec(c, 0, i, 1, n) *
rec(i, j + 1, p, d1s + 1, m - 1 - n);
}
if(d1s > 0) rer(n, 0, m) {
r +=
rec(c, 0, i, 1, n) *
rec(i, j + 1, p, d1s - 1, m - n) *
d1s;
}
return r;
}
int main() {
int N;
while(~scanf("%d%d", &N, &M)) {
g.assign(N, vi());
for(int i = 0; i < N - 1; ++ i) {
int u, v;
scanf("%d%d", &u, &v), -- u, -- v;
g[u].push_back(v);
g[v].push_back(u);
}
mint undef; undef.x = -1;
memo.assign(N * (M + 1) * (M + 1), undef);
mint ans = rec(0, 0, -1, 0, M);
printf("%d\n", ans.get());
}
return 0;
}
Java Road Maintenance HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class D {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), m = ni();
int[] from = new int[n - 1];
int[] to = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
from[i] = ni() - 1;
to[i] = ni() - 1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] par = pars[0], ord = pars[1], dep = pars[2];
int mod = 1000000007;
int[][] fif = enumFIF(100, mod);
long[] sel = new long[100];
long i2 = invl(2, mod);
for(int i = 0;i < 100;i++){
long u = fif[0][i] * (long)fif[1][i/2] % mod;
for(int j = 0;j < i/2;j++)u = u * i2 % mod;
sel[i] = u;
}
long[][] seab = new long[100][100];
for(int i = 0;i < 100;i++){
for(int j = 0;j <= i;j++){
seab[i][j] = C(i, j, mod, fif) * sel[i-j] % mod;
}
}
long[][] dp0 = new long[n][m+1];
long[][] dp1 = new long[n][m+1];
for(int i = n-1;i >= 0;i--){
int cur = ord[i];
long[][] ldp = new long[m+1][2*m+1];
ldp[0][0] = 1;
for(int e : g[cur]){
if(par[cur] != e){
long[][] nldp = new long[m+1][2*m+1];
for(int j = 0;j <= m;j++){
for(int k = 0;k <= 2*m;k++){
if(ldp[j][k] == 0)continue;
for(int l = 0;j+l <= m;l++){
nldp[j+l][k] += dp0[e][l] * ldp[j][k];
nldp[j+l][k] %= mod;
if(k+1 <= 2*m){
nldp[j+l][k+1] += dp1[e][l] * ldp[j][k];
nldp[j+l][k+1] %= mod;
}
}
}
}
ldp = nldp;
}
}
for(int j = 0;j <= m;j++){
for(int k = 0;k <= 2*m;k++){
for(int ab = k%2;ab <= k;ab+=2){
int nj = j+(k+ab)/2;
if(nj <= m){
dp0[cur][nj] += ldp[j][k] * seab[k][ab];
dp0[cur][nj] %= mod;
}else{
break;
}
}
for(int ab = (k%2)^1;ab <= k+1;ab+=2){
int nj = j+(k+ab)/2;
if(nj <= m){
long w = k-1 >= 0 ? k * seab[k-1][ab] : 0;
if(ab-1 >= 0)w += seab[k][ab-1];
dp1[cur][nj] += ldp[j][k] * (w%mod);
dp1[cur][nj] %= mod;
}else{
break;
}
}
}
}
// tr(cur);
// tr(dp0[cur]);
// tr(dp1[cur]);
}
out.println(dp0[0][m]);
}
public static long C(int n, int r, int mod, int[][] fif) {
if (n < 0 || r < 0 || r > n)
return 0;
return (long) fif[0][n] * fif[1][r] % mod * fif[1][n - r] % mod;
}
public static long invl(long a, long mod) {
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
return p < 0 ? p + mod : p;
}
public static int[][] enumFIF(int n, int mod) {
int[] f = new int[n + 1];
int[] invf = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = (int) ((long) f[i - 1] * i % mod);
}
long a = f[n];
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
invf[n] = (int) (p < 0 ? p + mod : p);
for (int i = n - 1; i >= 0; i--) {
invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod);
}
return new int[][] { f, invf };
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new D().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Road Maintenance HackerRank Solution
Suggest in comments
Python 2 Road Maintenance HackerRank Solution
Suggest in comments
C Road Maintenance HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _node{
int x;
int w;
struct _node *next;
} lnode;
#define MOD 1000000007
void insert_edge(int x,int y,int w);
void dfs(int x);
int M,trace[100000]={0};
long long dp[6][6][100000]={0};
lnode *table[100000]={0};
int main(){
int N,x,y,i;
long long ans;
scanf("%d%d",&N,&M);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
dfs(0);
for(i=ans=0;i<=M;i++)
ans=(ans+dp[i][M][0])%MOD;
printf("%lld",ans);
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs(int x){
int i,j,k,l;
long long t[6][6];
lnode *p;
trace[x]=1;
dp[0][0][x]=1;
for(p=table[x];p;p=p->next)
if(!trace[p->x]){
dfs(p->x);
memset(t,0,sizeof(t));
for(i=0;i<=M;i++)
for(j=0;i+j<=M+1;j++)
for(k=0;k<=i;k++)
for(l=0;l<=j;l++){
if(i+j<=M){
t[k][i+j]=(t[k][i+j]+dp[k][i][x]*dp[l][j][p->x])%MOD;
if(k)
t[k-1][i+j]=(t[k-1][i+j]+dp[k][i][x]*dp[l][j][p->x]%MOD*k)%MOD;
if(k+1<=i+j)
t[k+1][i+j]=(t[k+1][i+j]+dp[k][i][x]*dp[l][j][p->x]%MOD*l)%MOD;
}
if(i+j && k)
t[k-1][i+j-1]=(t[k-1][i+j-1]+dp[k][i][x]*dp[l][j][p->x]%MOD*k*l)%MOD;
if(i+j+1<=M)
t[k+1][i+j+1]=(t[k+1][i+j+1]+dp[k][i][x]*dp[l][j][p->x])%MOD;
}
for(i=0;i<=M;i++)
for(j=0;j<=M;j++)
dp[i][j][x]=t[i][j]%MOD;
}
return;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
