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. HackerRank City
  5. Discussions

HackerRank City

Sort by

recency

|

36 Discussions

|

  • shanefostersmith
     + 0 comments

    Java solultion in O(n). Similar logic to what others have expressed: we need to keep track of the previous number of nodes, the previous sum of all paths, the previous sum of all nodes to a corner node, and the previous diagonal path sum (aka. the longest path). We these values, we can find the values of the new city size with a little bit of combinatorics. The trickiest part is dealing with the modulo imo. 

        int mod = 1000000007;
    if (A.size() == 1) {
        return 29*(A.get(0));
    }
    long prevAll = 29*A.get(0);
    long prevAllToCorner = 11*A.get(0);
    long prevCornerToCorner = 3*A.get(0);
    long prevNumNodes = 6;
    for (int s = 1; s < A.size(); s++) {
        int currWeight = A.get(s);
        
        // Start with sum between inner two nodes and between previous nodes
        long currSum = ((4*prevAll)%mod + currWeight)%mod;
        
        // Inner Two Nodes to Previous Nodes (or quadrants) (times four)
        long closerInner = ((currWeight*prevNumNodes)%mod + prevAllToCorner) % mod;
        long fartherInner = ((2*currWeight*prevNumNodes)%mod + prevAllToCorner) % mod;
        long totalInnerToQuadrants = (4*(closerInner + fartherInner) %mod) %mod;
        currSum = (currSum + totalInnerToQuadrants) % mod;
        
        // Previous Nodes to Previous Nodes
        long threeQuadrantNodes = (3*prevNumNodes)%mod;
        long oneCornerUsage = (prevAllToCorner*threeQuadrantNodes)%mod;
        long totalCornerUsage = (4*oneCornerUsage)%mod;
        currSum = (currSum + totalCornerUsage) % mod;
        
        // Total inner edge path usage (aka. new inner edges) between previous nodes
        long sqrNodes = (prevNumNodes*prevNumNodes)%mod;
        long innerBetween2 = (2*(currWeight * sqrNodes)%mod)%mod;
        long innerBetween3 = (3*(currWeight * sqrNodes)%mod)%mod;
        long totalInBetween = ((2*innerBetween2)%mod + (4*innerBetween3)%mod)%mod;
        currSum = (currSum + totalInBetween) % mod;
        
        // Find new sum of all nodes to a corner node
        long currAllToCorner = prevAllToCorner;
        
        // One quad uses two edge inner path
        long closerQuad = (prevAllToCorner + prevNumNodes*(2*currWeight))%mod;
        currAllToCorner = (currAllToCorner + closerQuad)%mod;
        
        // Two quads use three edge inner path
        long furtherQuads = (prevAllToCorner + prevNumNodes*(3*currWeight))%mod;
        currAllToCorner = (currAllToCorner + (2*furtherQuads)%mod)%mod;
        
        // Inner nodes to upper corner
        long innerNodesToCorner = 3*currWeight;
        currAllToCorner = (currAllToCorner + innerNodesToCorner)%mod;
        
        // How many times the previous corner to corner path will be used
        long cornerToCornerUsage = ((threeQuadrantNodes+2)%mod*prevCornerToCorner)%mod;
        currAllToCorner = (currAllToCorner + cornerToCornerUsage)%mod;
        
        // Update DP values
        prevNumNodes = (4*prevNumNodes + 2)%mod;
        prevCornerToCorner = (2*prevCornerToCorner + 3*currWeight)%mod;
        prevAll = currSum;
        prevAllToCorner = currAllToCorner;
    }
    return (int) prevAll;
    }

  • zoyashah41306
     + 0 comments

    HackerRank-city is an acyclic connected graph (or tree). It’s not an ordinary place; the construction of the whole tree takes place in 𝑛−1n−1 steps. The process is described below: starting with a single node, new nodes are added one by one, each connecting to an existing node with an edge, ensuring no cycles form. This methodical growth models efficient network creation, optimizing connectivity and minimizing redundancy. Custom mugs featuring HackerRank-city's unique tree construction process celebrate this intricate design, serving as perfect keepsakes for enthusiasts of graph theory and algorithmic problem-solving, symbolizing their dedication to mastering complex computational concepts.

  • dehaka
     + 0 comments

    O(n)

    unsigned long hackerrankCity(vector<int> A) {
    int mod = 1000000007;
    unsigned long P = 1, L = 0, D = 0, H = 0;
    for (int i=1; i <= A.size(); i++) {
        H = (4*H + 12*P*D + 16*((P*P) % mod)*A[i-1] + 8*D + 12*P*A[i-1] + A[i-1]) % mod;
        D = (3*P*L + 8*P*A[i-1] + 4*D + 2*L + 3*A[i-1]) % mod;
        P = (4*P + 2) % mod;
        L = (2*L + 3*A[i-1]) % mod;
    }
    return H;
}

  • maqusss
     + 0 comments

    My O(n) solution:

    collect following 4 parameters at each of n steps:

    1. number of nodes
    2. distance of diagonal (top left most node and bottom right most node)
    3. sum of distances between right most bottom node and every other node
    4. sum of distances between each pair of nodes.

    Initially (before first step) there is 1 node, and other values are zeros. Calculate values for current step from previous step values in O(1).

  • yashparihar729
     + 0 comments

    here is my solution in java, javascript, python, C, C++, Csharp HackerRank City Problem Solution