# Road Maintenance

# Road Maintenance

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

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

+ 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; }

+ 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.

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

Sort 7 Discussions, By:

Please Login in order to post a comment