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 5 Discussions, By:

  • 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?

  • alur_pawan
     + 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

  • bretvh
     + 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]??

No more comments