HackerRank Road Maintenance Problem Solution
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 Format
The 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 Format
Find 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
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)); }
}
