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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Road Maintenance
  5. Discussions

Road Maintenance

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 5 Discussions, By:

votes

Please Login in order to post a comment

  • alur_pawan
    6 years ago+ 0 comments

    Okay, I had a really hard time trying to understand the sample input, and on reading bretvh's discussion, I have understood it. It seems that people could not understand, and so I will try to explain it to people so they get what you are supposed to do.

    The first is pretty clear...He does [1,2] and then does [2,3], which does NOT have any path in common.

    Now, for the example [1,2], and [3,4], this is what happens.

    He does [1,2].

    He then teleports to the city 3. From city 3, he maintains [3,2] AND [2,4]. These two add up to [3,4].

    So, he has done [1,2] and [3,4] without any path being repeated. This is thus counted in the total

    1|
    Permalink
  • bretvh
    6 years ago+ 1 comment

    I do not understand this problem, could someone please help me understand it. First, problem statement indicates that for N cities there are N -1 bidirectional roads. In the explanation of the sample problem there are N cities and 6 possible "routes"(a term which is undefined) using, what to me looks like more than N-1 roads, perhaps some are roads and some are paths or perhaps they are routes... the problem also states that there is guaranteed that there is a path from any city to any other city...and that a path is one or more connected roads...Ok. The given roads, in the sample problem, are [1,2], [2,3], [2,4] which are bidirectional roads. We have a constraint that says a path cannot contain the two same roads(I assume this means [1,2] + [2,1] is invalid) so I assume we have paths: [1,2], [2,1], [2,3], [3,2], [2,4], [4,2], [1,2]+[2,3], [1,2]+[2,4], [3,2]+[2,4], [3,2]+[2,1], [4,2]+[2,1], [4,2]+[2,3] and they satisfy the constraint that there is a path from any city to any other city...so the explanation claims that there is a route [1,2]+[3,4] but it does not appear connected and and to go [1,2]+[2,3]+[3,2]+[2,4] violates the constraint that a path cannot contain the same two roads...perhaps a route is one or more paths and is not subject to the constraint of a path?? is that the case? BUT here is the kicker!!! You need M paths not M routes...so what am I missing? Are the 6 routes discussed [1,2],[1,3],[1,4],[2,3],[2,4],[3,4] or are they roads?? and can they be used as paths to construct other paths?? and why are available to use? confusing. Finally, why not [1,3]+[3,4]??

    1|
    Permalink
  • TChalla
    1 year ago+ 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|
    Permalink
  • nitin29
    5 years ago+ 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.

    0|
    Permalink
  • Nagesh
    5 years ago+ 1 comment

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

    0|
    Permalink

No more comments

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature