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

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