We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Road Maintenance
  5. Discussions

Road Maintenance

Sort by

recency

|

7 Discussions

|

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Road Maintenance Problem Solution

  • thecodingsoluti2
     + 0 comments

    Here is Road Maintenance problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-road-maintenance-problem-solution.html

  • TChalla
     + 0 comments
    #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;
}

  • nitin29
     + 0 comments

    The following algorithm should work in O(N) complexity. When the road link count is 10000 then the total number of roads is n/2*(n-1) = 49995000. Lets say the road numbers run from 1-49995000 or to n/2*(n-1) . Start navigating the road links. Let’s say there is a link 1-2. Assign this link the next available road number, which is one in this case. So the road lookup will get the following entries 1-(1,2) and reverse. Also the road ending in a node DS will have the following entries 1-null, 2-(1).

    Let’s process link 2-3 this will add one more road, road #2. Now road look up has 2 entries, 1-(1,2), 2-(2,3). The road ending in a node DS will have the following entries 1-null, 2-(1), 3-(2). Since the start of this link node 2 has an entry in road ending in a node DS, so road 1 will be joined with road 2 to form a new road #3. Now road lookup has one more entry 3-(1,3). Also since this road ends in road #3 the corresponding entry in road ending in a node DS is updates to 3-(2,3). Also the road parts DS will have one entry now, 3-(1,2). This DS stores a link for all the single road parts for this road. The entry for road 2 in road ending in a node DS will also get updated 2-(1,2)

    We introduce one more DS here, road grouping. This DS will store the list of all the road with which the given road has at-least one common road, and hence are connected. At this point the DS will have the following entries. 1-(3), 2-(3), 3-(1,2). As you can see the entries in this DS are symmetrical. What this means that road #1 can be paired with 2. So one one pair of disconnected road is possible among the three roads. Lets process link 2-4. This will add one more road road #3. Now road look up has fourth entry 4-(2,4). The road ending in a node DS has one more entry 4-(4). Since the start of this road road #2 has an entry in this DS which point to 2 roads ending in #2 i.e road #1,2. These first roads will combine with road 4 and form a new road, road #5. The road look up will have the new entries as 5-(1,4) and 6-(3,4). The road parts DS will have a new entry for 5-(1,4). The road grouping will be updated with a blank entry for 4-null. The entry for 5 will be 5-(1,3,4), the following entries will be updated to 1-(3,5), 3-(1,2,5),4-(5).

    The second road will combine with 4 to form road #6. The road look up will have the new entry as 6-(3,4). The entry for 6 in road parts will be 6-(2,4). The entry for 6 in road grouping will be 6-(2,3,4,5), the following entries will be updated to 2-(3,6), 3-(1,2,5, 6), 4-(5, 6), 5-(1,3,4,6)

    Following will be the entries in road grouping 1-(3,5), 2-(3,6), 3-(1,2,5,6),4-(5,6),5-(1,3,4,6), (2,3,4,5). So from single road entries of 3, 2 can be selected in 3 ways. Road 3 can paired with 4. Road 5 can be paired with 2. Road 6 can be paired with with road 1. So a total of 6 possibilities.

  • Nagesh
     + 1 comment

    The problem is not clear. Can you please reword or elaborate?