HackerRank Longest Mod Path problem solution

In this HackerRank Longest Mod Path problem solution, There are Q levels to Maxine’s nightmare castle, and each one has a different set of values for S, E, and M. Given the above information, help Maxine by finding and printing her maximum possible score for each level. Only you can help her wake up from this nightmare!

Problem solution in Python.

n = eval(input())
adj = [[] for i in range(n)]
for i in range(n):
    a, b, c = list(map(int, input().strip().split()))
    a -= 1; b -= 1
    adj[a].append((b, c))
    adj[b].append((a, -c))

dist = [None]*n
parents = [set() for i in range(n)] # set because of special case: cycle of length 2
dist[0] = 0
stack = [0]
while stack:
    i = stack.pop()
    for j, c in adj[i]:
        if j in parents[i]: continue
        ndist = dist[i] + c
        parents[j].add(i)
        if dist[j] is None:
            dist[j] = ndist
            stack.append(j)
        else:
            cycle = abs(dist[j] - ndist)

from fractions import gcd
for qq in range(eval(input())):
    s, e, m = list(map(int, input().strip().split()))
    a = gcd(cycle, m)
    print(m - a + (dist[e-1] - dist[s-1]) % a)

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 longestModPath function below.
     */
     static long gcd(long a, long b){
        if(b == 0)
            return a;
        return gcd(b, a%b);
     }
    static int[] longestModPath(int[][] corridor, int[][] queries) {
        /*
         * Write your code here.
         */
        HashMap<Integer,HashMap<Integer,Integer>> adj = new HashMap<Integer,HashMap<Integer,Integer>>();
        HashMap<Integer,long[]> toCycle = new HashMap<Integer,long[]>();
        HashMap<Integer,long[]> cycle = new HashMap<Integer,long[]>();
        HashSet<Integer> leaf = new HashSet<Integer>();
        long cyclesum = 0;
        for(int i = 0; i < corridor.length; i++)
            adj.put(i, new HashMap<Integer,Integer>());
        for(int i = 0; i < corridor.length; i++){
            int temp1 = corridor[i][0]-1;
            int temp2 = corridor[i][1] - 1;
            if(adj.get(temp1).keySet().contains(temp2))
               cyclesum = Math.abs(adj.get(temp2).get(temp1) + corridor[i][2]);
            adj.get(temp1).put(temp2,corridor[i][2]);
            adj.get(temp2).put(temp1,-corridor[i][2]);
        }
        HashSet<Integer> used = new HashSet<Integer>();
        HashMap<Integer,Integer> parent = new HashMap<Integer,Integer>();
        Queue<Integer> stuff = new LinkedList<Integer>();
        stuff.add(0);
        used.add(0);
        long[] distances = new long[corridor.length];
        while(stuff.size() > 0){
            int temp = stuff.remove();
            for(int child: adj.get(temp).keySet()){
               if(used.contains(child) && parent.get(temp) != child)
                  cyclesum = distances[temp] - distances[child] + adj.get(temp).get(child);
               else if(!used.contains(child)){
                  stuff.add(child);
                  used.add(child);
                  distances[child] = distances[temp] + adj.get(temp).get(child);
                  parent.put(child,temp);
               }
            }
        }
        int[] answers = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            long k = gcd(cyclesum,(long)queries[i][2]);
            if(k == 1)
                answers[i] = queries[i][2]-1;
            else{
                int S = queries[i][0]-1;
                int E = queries[i][1]-1;
                int mod = queries[i][2];
                answers[i] = (int)((distances[E] - distances[S])%mod+mod)%mod;
                answers[i] = answers[i] + (int)((mod - answers[i]-1)/k*k);
            }
        }
        return answers;
    }
    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 n = scanner.nextInt();
        scanner.skip("(rn|[nru2028u2029u0085])*");

        int[][] corridor = new int[n][3];

        for (int corridorRowItr = 0; corridorRowItr < n; corridorRowItr++) {
            String[] corridorRowItems = scanner.nextLine().split(" ");
            scanner.skip("(rn|[nru2028u2029u0085])*");

            for (int corridorColumnItr = 0; corridorColumnItr < 3; corridorColumnItr++) {
                int corridorItem = Integer.parseInt(corridorRowItems[corridorColumnItr]);
                corridor[corridorRowItr][corridorColumnItr] = corridorItem;
            }
        }

        int q = scanner.nextInt();
        scanner.skip("(rn|[nru2028u2029u0085])*");

        int[][] queries = new int[q][3];

        for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
            String[] queriesRowItems = scanner.nextLine().split(" ");
            scanner.skip("(rn|[nru2028u2029u0085])*");

            for (int queriesColumnItr = 0; queriesColumnItr < 3; queriesColumnItr++) {
                int queriesItem = Integer.parseInt(queriesRowItems[queriesColumnItr]);
                queries[queriesRowItr][queriesColumnItr] = queriesItem;
            }
        }

        int[] result = longestModPath(corridor, queries);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Problem solution in C++.

#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

const int MAXN = 120 * 1000;

vector <pair <int, int> > adj[MAXN];
long long a[MAXN];
bool used[MAXN];
long long cycle = 0;

void dfs(int v, long long num) {
    a[v] = num;
    used[v] = true;
    for (int i = 0; i < sz(adj[v]); ++i) {
        int u = adj[v][i].fs;
        if (!used[u]) {
            dfs(u, num + adj[v][i].sc);
        } else if (a[v] + adj[v][i].sc - a[u] != 0) {
            cycle = a[v] + adj[v][i].sc - a[u];
        }
    }
}

int gcd(int a, int b) {
    return (a == 0 ? b : gcd(b % a, a));
}

int main () {

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int v1, v2, c;
        scanf("%d%d%d", &v1, &v2, &c);
        v1--, v2--;
        adj[v1].pb(mp(v2, c));
        adj[v2].pb(mp(v1, -c));
    }

    dfs(0, 0);
    
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        int s, e, m;
        scanf("%d%d%d", &s, &e, &m);
        s--, e--;
        
        int val = ((a[e] - a[s]) % m + m) % m;
        int cycle_val = (cycle % m  + m) % m;
        
        int d = gcd(cycle_val, m);

        int res = (val % d) + m - d;
        printf("%dn", res);
    }

    return 0;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

struct corridor{
    int from;
    int to;
    int cost;
};

long gcd(long a, long b){
    if(a == 0){
        return b;
    }
    if(b == 0){
        return a;
    }
    if((a&1) == 0){
        if((b&1) == 0){
            return 2*gcd(a>>1, b>>1);
        }
        else{
            return gcd(a>>1, b);
        }
    }
    else{
        if((b&1) == 0){
            return gcd(a, b>>1);
        }
        else{
            return gcd((a < b? b - a : a - b), (a < b? a : b));
        }
    }
}

int* longestModPath(int n, int** corridors, int q, int** queries) {
    struct corridor sortcorr[2*n];
    for(int i = 0; i < n; i++){
        struct corridor temp = {corridors[i][0] - 1, corridors[i][1] - 1, corridors[i][2]};
        struct corridor temp2 = {corridors[i][1] - 1, corridors[i][0] - 1, -corridors[i][2]};
        sortcorr[2*i] = temp;
        sortcorr[2*i + 1] = temp2;
    }

    for(int i = 0; i < 2*n; i++){
        int curr = i;
        while(curr > 0){
            int next = (curr - 1)/2;
            if(sortcorr[curr].from > sortcorr[next].from){
                struct corridor temp = sortcorr[curr];
                sortcorr[curr] = sortcorr[next];
                sortcorr[next] = temp;
                curr = next;
            }
            else{
                break;
            }
        }
    }

    for(int i = 2*n - 1; i >= 0; i--){
        struct corridor temp = sortcorr[0];
        sortcorr[0] = sortcorr[i];
        sortcorr[i] = temp;

        int curr = 0;
        while(true){
            int next = curr;
            if(2*curr + 1 < i && sortcorr[2*curr + 1].from > sortcorr[next].from){
                next = 2*curr + 1;
            }
            if(2*curr + 2 < i && sortcorr[2*curr + 2].from > sortcorr[next].from){
                next = 2*curr + 2;
            }
            if(next != curr){
                struct corridor temp = sortcorr[curr];
                sortcorr[curr] = sortcorr[next];
                sortcorr[next] = temp;
                curr = next;
            }
            else{
                break;
            }
        }
    }
    int edgebounds[n + 1];
    edgebounds[0] = 0;
    for(int i = 0; i < n; i++){
        int index = edgebounds[i];
        while(index < 2*n && sortcorr[index].from == i){
            index++;
        }
        edgebounds[i + 1] = index;
    }

    long vals[n];
    long loopval = 0;
    int nodequeue[n];
    nodequeue[0] = 0;
    int queuedone = 0;
    int queuesize = 1;
    bool touched[n];
    for(int i = 0; i < n; i++){
        touched[i] = 0;
    }
    touched[0] = 1;

    while(queuedone < queuesize){
        int currnode = nodequeue[queuedone];
        for(int i = edgebounds[currnode]; i < edgebounds[currnode + 1]; i++){
            int nextnode = sortcorr[i].to;
            if(touched[nextnode] == 0){
                touched[nextnode] = 1;
                queuesize++;
                nodequeue[queuesize - 1] = nextnode;
                vals[nextnode] = vals[currnode] + sortcorr[i].cost;
            }
            else{
                long checkval = vals[currnode] + sortcorr[i].cost - vals[nextnode];
                if(loopval == 0 && checkval != 0){
                    loopval = (checkval > 0? checkval : -checkval);
                }
            }
        }
        queuedone++;
    }

    int *toreturn = malloc(q*sizeof(int));
    for(int i = 0; i < q; i++){
        int inode = queries[i][0] - 1;
        int enode = queries[i][1] - 1;
        long mod = queries[i][2];
        int common = gcd(mod, loopval);
        long disp = (vals[enode] - vals[inode])%common;
        disp = (disp + common)%common;
        toreturn[i] = disp + mod - common;
    }
    return toreturn;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '') { exit(EXIT_FAILURE); }

    int** corridor = malloc(n * sizeof(int*));

    for (int corridor_row_itr = 0; corridor_row_itr < n; corridor_row_itr++) {
        *(corridor + corridor_row_itr) = malloc(3 * (sizeof(int)));

        char** corridor_item_temp = split_string(readline());

        for (int corridor_column_itr = 0; corridor_column_itr < 3; corridor_column_itr++) {
            char* corridor_item_endptr;
            char* corridor_item_str = *(corridor_item_temp + corridor_column_itr);
            int corridor_item = strtol(corridor_item_str, &corridor_item_endptr, 10);

            if (corridor_item_endptr == corridor_item_str || *corridor_item_endptr != '') { exit(EXIT_FAILURE); }

            *(*(corridor + corridor_row_itr) + corridor_column_itr) = corridor_item;
        }
    }

    char* q_endptr;
    char* q_str = readline();
    int q = strtol(q_str, &q_endptr, 10);

    if (q_endptr == q_str || *q_endptr != '') { exit(EXIT_FAILURE); }

    int** queries = malloc(q * sizeof(int*));

    for (int queries_row_itr = 0; queries_row_itr < q; queries_row_itr++) {
        *(queries + queries_row_itr) = malloc(3 * (sizeof(int)));

        char** queries_item_temp = split_string(readline());

        for (int queries_column_itr = 0; queries_column_itr < 3; queries_column_itr++) {
            char* queries_item_endptr;
            char* queries_item_str = *(queries_item_temp + queries_column_itr);
            int queries_item = strtol(queries_item_str, &queries_item_endptr, 10);

            if (queries_item_endptr == queries_item_str || *queries_item_endptr != '') { exit(EXIT_FAILURE); }

            *(*(queries + queries_row_itr) + queries_column_itr) = queries_item;
        }
    }

    int queries_rows = q;

    int result_count = q;
    int* result = longestModPath(n, corridor, queries_rows, queries);

    for (int result_itr = 0; result_itr < result_count; result_itr++) {
        fprintf(fptr, "%d", *(result + result_itr));

        if (result_itr != result_count - 1) {
            fprintf(fptr, "n");
        }
    }

    fprintf(fptr, "n");

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}