HackerRank City problem solution

In this HackerRank City problem solution, we have an acyclic connected graph or tree and the construction of the whole tree takes place in N steps. it has initially 1 node and at each step, we need to create 3 duplicates of the current tree and 2 new nodes to connect all 4 copies in the H shape. we need to calculate the sum of distances between each pair of nodes.

HackerRank City problem solution in Python.

#!/bin/python3

import os
import sys

#
# Complete the hackerrankCity function below.
#
def hackerrankCity(A):
    n=len(A)
    N=1
    dist=0
    sumd=A[0]*11#sum of all distances to the right bottom corner points
    dp=29*A[0]#dp is the sum of all distances
    for i in range(1,n):
        N=N*4+2
        dp=4*dp+sumd*(12*N+8)+A[i]*(16*N**2+12*N+1)
        dist=2*dist+3*A[i-1]
        sumd=4*sumd+A[i]*(8*N+3)+(3*N+2)*dist
        dp%=(10**9+7)
        sumd%=(10**9+7)
        N%=(10**9+7)
        dist%=(10**9+7)
    return dp

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    A_count = int(input())

    A = list(map(int, input().rstrip().split()))

    result = hackerrankCity(A)

    fptr.write(str(result) + 'n')

    fptr.close()

City problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the hackerrankCity function below.
     */
    static int hackerrankCity(int[] A) {
        int n = A.length;
        long[] cluster_size = new long[n + 1];
        long[] total = new long[n + 1];
        long[] p = new long[n + 1];
        long[] line = new long[n + 1];

        long m = (long)1e9 + 7;

        cluster_size[0] = 1;
        p[0] = 0;
        total[0] = 0;
        line[0] = 0;

        for (int i = 1; i <= n; i++) {
            long a = A[i - 1];
            long k = cluster_size[i - 1];
            cluster_size[i] = (k * 4 + 2) % m;
            line[i] = (line[i - 1] * 2 + 3 * a) % m;

            p[i] = (p[i - 1]
                + p[i - 1] + k * (2 * a + line[i - 1]) % m
                + 2 * (k * (line[i - 1] + 3 * a) % m + p[ i - 1]) % m
                + line[i - 1] * 2 + 3 * a % m
                ) % m;
            
            total[i] = (4 * total[i - 1] % m
                + 4 * (p[i - 1] + k * a) % m
                + 4 * (p[i - 1] + k * a * 2) % m
                + 2 * ((p[i - 1] * k) % m * 2 + ((k * k) % m) * a * 2) % m
                + 4 * ((p[i - 1] * k) % m * 2 + ((k * k) % m) * a * 3) % m
                + a) % m;

        }

        return (int)(total[n] % m);
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int ACount = Integer.parseInt(scanner.nextLine().trim());

        int[] A = new int[ACount];

        String[] AItems = scanner.nextLine().split(" ");

        for (int AItr = 0; AItr < ACount; AItr++) {
            int AItem = Integer.parseInt(AItems[AItr].trim());
            A[AItr] = AItem;
        }

        int result = hackerrankCity(A);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define M 1000000007L

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int N;
    scanf("%d", &N);
    
    long s = 0, t = 0, n = 1, d = 0;
    long newS, newT, newN, newD;
    
    for (int i = 0; i < N; i++) {
        int a;
        scanf("%d", &a);
        newT = (4 * t + (16 * (n * n % M) + 12 * n + 1) % M * a % M + 12 * (s * n % M) + 8 * s) % M;
        newD = (2 * d + 3 * a) % M;
        newN = (4 * n + 2) % M;
        newS = (4 * s + 8 * (a * n % M) + 3 * (n * d % M) + 3 * a + 2 * d) % M;
        t = newT;
        d = newD;
        n = newN;
        s = newS;
    }
    
    printf("%ld", t);
    
    return 0;
}

Problem solution in C.

#include <stdio.h>


const int MOD = 1000000007;
int n, ne;

int main() {
 
    long long nv = 1;
    long long sd = 0;
    long long dtc = 0;
    long long diam = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d",&ne);
        long long nnv = nv * 4 + 2;
        long long nsd = 4 * sd + 4 * dtc * (2 + 3 * nv % MOD) % MOD + 4 * ne * nv % MOD * (nv * 3 + 2) % MOD +
            ne * (2 * nv + 1) % MOD * (2 * nv + 1) % MOD;
        long long ndtc = 4 * dtc + 8 * ne * nv % MOD + 3 * ne + (3 * nv + 2) * diam % MOD;
        long long ndiam = 2 * diam + 3 * ne;
        nv = nnv % MOD;
        sd = nsd % MOD;
        dtc = ndtc % MOD;
        diam = ndiam % MOD;
    }
    printf("%lldn",sd);
    return 0;
}