HackerRank Road Maintenance Problem Solution Yashwant Parihar, August 4, 2023August 1, 2024 In this Post, we will solve HackerRank Road Maintenance Problem Solution. Byteland has N cities (numbered from 1 to N) and N-1 bidirectional roads. A path is comprised of 1 or more connected roads. It is guaranteed that there is a path from any city to any other city.Steven is a road maintenance worker in Byteland. He is required to maintain exactly M paths on any given workday. He cannot work on the same road twice in one day (so no 2 paths can contain the same 2 roads). Steven can start his workday in any city and, once he has finished maintaining a path, teleport to his next starting city.Given M. help Steven determine how many different possible M-path sets will allow him to perform his maintenance duties. Then print the answer modulo 109 + 7.Input FormatThe first line contains 2 space-separated integers, N (the number of cities) and M (the number of roads to maintain).Each line i of the N – 1 subsequent lines contains 2 space-separated integers, A, Bi describing a bidirectional road between cities A, and B₁. Output FormatFind the number of different M-path sets that will allow Steven to complete M orders, and print the answer % (10 power 9 +7). Sample Input 4 2 1 2 2 3 2 4 Sample Output 6 HackerRank Road Maintenance Problem Solution Road Maintenance C 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; } Road Maintenance C++ Solution #include <bits/stdc++.h> using namespace std; #define pb push_back #define foreach(i,x) for(type(x)i = x.begin(); i != x.end(); i++) #define FOR(ii, aa, bb) for(int ii = aa; ii <= bb; ii++) #define type(x) __typeof(x.begin()) typedef long long ll; const int mod = (int) 1e9 + 7; const int N = 2e5 + 5; int n, m, x, y, dp[N][11][11], temp[N][11][11]; vector<int> v[N]; void dfs(int node, int root) { dp[node][0][0] = 1; foreach(it, v[node]) { if(*it == root) continue; dfs(*it, node); FOR(i, 0, 10){ FOR(j, 0, 10) { temp[node][i][j] = dp[node][i][j]; dp[node][i][j] = 0; } } FOR(i, 0, m){ FOR(j, 0, m - i){ FOR(k, 0, m){ dp[node][i + j][k] = (dp[node][i + j][k] + temp[node][i][k] * (ll) dp[*it][j][0]) % mod; dp[node][i + j][k + 1] = (dp[node][i + j][k + 1] + temp[node][i][k] * (ll) dp[*it][j][1]) % mod; if(k) dp[node][i + j + 1][k - 1] = (dp[node][i + j + 1][k - 1] + temp[node][i][k] * (ll) dp[*it][j][1] % mod * k) % mod; dp[node][i + j + 1][k] = (dp[node][i + j + 1][k] + temp[node][i][k] * (ll) dp[*it][j][1] % mod) % mod; } } } } FOR(i, 0, m) dp[node][i][1] = (dp[node][i][1] + dp[node][i][0]) % mod; } int main() { cin >> n >> m; FOR(i, 2, n) { cin >> x >> y; v[x].pb(y); v[y].pb(x); } dfs(1, 0); cout << dp[1][m][0] << endl; return 0; } Road Maintenance Java 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; } } } } } 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)); } } c C++ HackerRank Solutions java CcppHackerrank Solutionsjava