HackerRank City Problem Solution

In this post, we will solve HackerRank City Problem Solution. HackerRank-city is an acyclic connected graph (or tree). Its not an ordinary place, the construction of the whole tree takes place in N steps. The process is described below: • It initially has 1 node. • At each step, you must create 3 duplicates of the current tree, and create 2 new nodes to connect all 4 copies in the following H shape:

At each ith step, the tree becomes 4 times bigger plus 2 new nodes, as well as 5 new edges connecting everything together. The length of the new edges being added at step & is denoted by input A,
Calculate the sum of distances between each pair of nodes; as these answers may run large, print your answer modulo 1000000007.
Input Format
The first line contains an integer, N (the number of steps). The second line contains N space-separated integers describing A, A1,…, AN-2, AN-1.

Sample Input 0

1
1

Sample Output 0

Sample Input 1

2
2 1

Sample Output 1

Table of Contents

HackerRank City C Solution

#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("%lld\n",sd);
    return 0;
}

HackerRank City C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
long long mod = 1E9 + 7;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int steps;
    cin >> steps;
    long long c = 0;
    long long n = 1;
    long long g = 0;
    long long d = 0;
    long long next_c, next_n, next_g, next_d;
    for (int i = 0 ; i < steps; ++i)
    {
        int a; 
        cin >> a;
        next_c = (2 * c) % mod + 3 * a;
        next_n = (4 * n) % mod + 2;
        next_g = g 
                 + 2 * (n * (3 * a % mod + c) % mod + g)
                 + n * (2 * a + c) % mod + g
                 + 3 * a + (2 * c) % mod;
        next_d = (4 * d) % mod
                 + 4 * (3 * a * (n*n % mod) + 2 * (n * g) % mod)
                 + 2 * (2 * a * (n*n % mod) + 2 * (n * g) % mod)
                 + 4 * (3 * (a * n % mod) + 2 * g % mod)
                 + a;
        c = next_c % mod;
        n = next_n % mod;
        g = next_g % mod;
        d = next_d % mod;
    }
    
    cout << d << endl;
    return 0;
}

HackerRank City C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
    
    static ulong mod = 1000000007;

    /*
     * Complete the hackerrankCity function below.
     */
    static int hackerrankCity(int[] A) {
        int n = A.Length;
        ulong prevCount=1,prevDiagonal=0,prevJunction=0,prevSum=0;
        ulong curCount=1,curDiagonal=0,curJunction=0,curSum=0;
        for (int i = 0; i < n; i++) {
            ulong curA = (ulong)A[i];
            curCount = nextCount(prevCount);
            curDiagonal = nextDiagonal(prevDiagonal, curA);
            curJunction = nextJunction(prevJunction, curA, prevCount, prevDiagonal);
            curSum = nextSum(prevSum, curA, prevCount, prevJunction);
            prevCount = curCount;
            prevDiagonal = curDiagonal;
            prevJunction = curJunction;
            prevSum = curSum;
        }
        return (int)(prevSum % mod);
    }
    
    static ulong nextCount(ulong cur) {
        return ((4*cur)%mod+2)%mod;
    }
    
    static ulong nextDiagonal(ulong cur, ulong cost) {
        return ((2*cur)%mod+3*cost)%mod;
    }
    
    static ulong nextJunction(ulong cur, ulong cost, ulong count, ulong diagonal) {
        return (cost+((5*cost)%mod*count)%mod+(4*cur)%mod+((3*count)%mod+2)%mod*(diagonal+cost))%mod;
    }
    
    static ulong nextSum(ulong cur, ulong cost, ulong count, ulong junction) {
        return ((4*cur)%mod+(((3*cost)%mod)*count%mod+2*junction%mod)*4+cost+(2*count%mod*(2*junction%mod+2*count%mod*cost%mod)+4*count%mod*(2*junction%mod+3*count%mod*cost%mod)))%mod;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int ACount = Convert.ToInt32(Console.ReadLine());

        int[] A = Array.ConvertAll(Console.ReadLine().Split(' '), ATemp => Convert.ToInt32(ATemp))
        ;
        int result = hackerrankCity(A);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

HackerRank City Java Solution

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();
    }
}

HackerRank City JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function mult(a, b, m){
    let result = 0;
    a %= m;

    while(b > 0){
        if(b % 2 > 0){
            result = (result + a) % m;
        }

        a = (2 * a) % m;
        b = Math.floor(b/2);
    }

    return result
}

/*
 * Complete the hackerrankCity function below.
 */


function hackerrankCity(A) {
    const m = 1000000007;
    let C = 1;
    let E = 0;
    let Z = 0;
    let D = 0;
    A = [0, ...A]

    for(let i = 1; i < A.length; i++){
        const CX = C, EX = E, ZX = Z, DX = D
        C = ((4*CX)%m + 2) % m
        Z = ((2*ZX)%m + (3*A[i])%m)%m;
        E = ((4*EX)%m + (8*CX*A[i])%m + 3*A[i] + mult(3*CX, ZX, m) + ((2*ZX) % m) % m) % m
        D =  (((4 * DX) % m) + ((12*(A[i]%m)%m)*CX)%m + (8*EX)%m + (A[i])%m + mult(12*CX, EX, m) + 16*A[i]*mult(CX, CX, m)) % m
    }

    return D;

}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const ACount = parseInt(readLine(), 10);

    const A = readLine().split(' ').map(ATemp => parseInt(ATemp, 10));

    let result = hackerrankCity(A);

    ws.write(result + "\n");

    ws.end();
}

HackerRank City Python Solution

#!/bin/python3

import os
import sys

#
# Complete the hackerrankCity function below.
#

d = 1000000007
def hackerrankCity(A):
    s = 0
    sumv = 0
    sum = 0
    n = 1
    
    for a in A:
        sum = 4 * sum + 12 * sumv * n + 8 * sumv + 16 * n * n * a + (12 * n + 1) * a
        sum %= d
        sumv = 4 * sumv + (8 * n + 3) * a + (3 * n + 2) * s
        sumv %= d
        n = 4 * n + 2
        n %= d
        s = 2 * s + 3 * a
        s %= d
        
    return sum
    #
    # Write your code here.
    #

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()