HackerRank Toll Cost Digits Problem Solution

HackerRank Toll Cost Digits Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Toll Cost Digits Problem Solution.

The mayor of Farzville is studying the city’s road system to find ways of improving its traffic conditions. Farzville’s road system consists of n junctions connected by e bidirectional toll roads, where the ith toll road connects junctions ; and y. In addition, some junctions may not be reachable from others and there may be multiple roads connecting the same pair of junctions.
Each toll road has a toll rate that’s paid each time it’s used. This rate varies depending on the direction of travel:

  • If traveling from ; to y, then the toll rate is ri.
    If traveling from yi to xi then the toll rate is 1000-ri. It is guaranteed that 0 < ri < 1000.

For each digit d = {0,1,…, 9}, the mayor wants to find the number of ordered pairs of (x, y) junctions such that #y and a path exists from a toy where the total cost of the tolls (i.e., the sum of all toll rates on the path) ends in digit d. Given a map of Farzville, can you help the mayor answer this question? For each digit d from 0 to 9, print the the number of valid ordered pairs on a new line.
Note: Each toll road can be traversed an unlimited number of times in either direction.
Input Format
The first line contains two space-separated integers describing the respective values of n (the number of junctions) and e (the number of roads).
Each line i of the e subsequent lines describes a toll road in the form of three space- separated integers, xi, Yi, and ri.

Output Format
Print ten lines of output. Each line j (where 0 ≤ j ≤9) must contain a single integer denoting the answer for d = j. For example, the first line must contain the answer for d = 0, the second line must contain the answer for d = 1, and so on.

Sample Input 0

3 3
1 3 602
1 2 256
2 3 411

Sample Output 0

0
2
1
1
2
0
2
1
1
2

Explanation 0

The table below depicts the distinct pairs of junctions for each d:

Note the following:

  • There may be multiple paths between each pair of junctions.
  • Junctions and roads may be traversed multiple times. For example, the path 2 → 31→2→3 is also valid, and it has total cost of
    411 + 398 +256 + 411 = 1476.
  • An ordered pair can be counted for more than one d. For example, the pair (2, 3) is counted for d = 1 and d = 6.
  • Each ordered pair must only be counted once for each d. For example, the paths 2 → 13 and 23 → 1→2→ 3 both have total costs that end in d = 6, but the pair (2, 3) is only counted once.
HackerRank Toll Cost Digits Problem Solution
HackerRank Toll Cost Digits Problem Solution

Toll Cost Digits C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
void dfs(int x,int len);
void insert_edge(int x,int y,int w);
int trace[100000],dp[100000],odd,even,five,count;
long long ans[10],temp[10],temp2[10],temp3[10],save1[100000][10],save2[100000][10];
lnode *table[100000];

int main(){
  int n,m,x,y,w,i,j;
  long long t1,t2;
  scanf("%d%d",&n,&m);
  for(i=0;i<m;i++){
    scanf("%d%d%d",&x,&y,&w);
    insert_edge(x-1,y-1,w%10);
  }
  for(i=0;i<n;i++)
    if(!trace[i]){
      memset(temp,0,sizeof(temp));
      memset(temp2,0,sizeof(temp2));
      odd=even=five=count=0;
      dfs(i,0);
      if(odd || (even && five))
        for(j=0;j<10;j++)
          ans[j]+=count*(long long)(count-1);
      else if(five){
        temp[0]*=2;
        temp[5]*=2;
        for(j=1;j<5;j++)
          temp[j]=temp[10-j]=temp[j]+temp[10-j];
        for(j=0;j<5;j++)
          temp[j]=temp[j+5]=temp[j]+temp[j+5];
        for(j=0;j<10;j++)
          ans[j]+=temp[j];
      }
      else if(even){
        temp[0]*=2;
        temp[5]*=2;
        for(j=1;j<5;j++)
          temp[j]=temp[10-j]=temp[j]+temp[10-j];
        for(j=t1=t2=0;j<10;j++)
          if(j%2)
            t1+=temp[j];
          else
            t2+=temp[j];
        for(j=0;j<10;j++)
          if(j%2)
            temp[j]=t1;
          else
            temp[j]=t2;
        for(j=0;j<10;j++)
          ans[j]+=temp[j];
      }
      else{
        temp[0]*=2;
        temp[5]*=2;
        for(j=1;j<5;j++)
          temp[j]=temp[10-j]=temp[j]+temp[10-j];
        for(j=0;j<10;j++)
          ans[j]+=temp[j];
      }
    }
  for(i=0;i<10;i++)
    printf("%lld\n",ans[i]);
  return 0;
}
void dfs(int x,int len){
  int t,i;
  lnode *p;
  count++;
  trace[x]=1;
  dp[x]=len;
  for(i=0;i<10;i++)
    temp[i]+=temp2[i];
  temp2[0]++;
  memcpy(&save1[x][0],temp2,sizeof(temp2));
  for(p=table[x];p;p=p->next)
    if(!trace[p->x]){
      for(i=0;i<10;i++)
        temp3[(i+p->w)%10]=temp2[i];
      memcpy(temp2,temp3,sizeof(temp2));
      dfs(p->x,(len+p->w)%10);
      save2[p->x][0]++;
      for(i=0;i<10;i++)
        save2[x][(i+p->w)%10]+=save2[p->x][i];
      save2[p->x][0]--;
      for(i=0;i<10;i++)
        temp2[i]=save2[x][(10-i)%10];
      for(i=0;i<10;i++)
        temp2[i]+=save1[x][i];
    }
    else{
      t=dp[p->x];
      t=(10-t+len+p->w)%10;
      if(!t);
      else if(t==5)
        five=1;
      else if(t%2)
        odd=1;
      else
        even=1;
    }
  return;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=(10-w)%10;
  t->next=table[y];
  table[y]=t;
  return;
}

Toll Cost Digits C++ Solution

//Giorgi Kldiashvili

#include <bits/stdc++.h>

#define M 1000000007ll
#define ll long long

using namespace std;

int n, m;
int P[100020], A[100020][10], a[100020];
ll bb[1024], answer[10];
vector < pair < int, int > > G[100020];
vector < int > C[100020];

int Parent(int x)
{
  if(P[x] == x)
    return x;
  return P[x] = Parent(P[x]);
}

void DSU(int x, int y)
{
  x = Parent(x);
  y = Parent(y);
  if(x == y)
    return;
  P[x] = y;
}

void go(int v, int dig)
{
  A[v][dig] = 1;

  for(int i = 0; i < G[v].size(); ++ i)
  {
    int to = G[v][i].first; int val = G[v][i].second;
    int x = (dig + val) % 10;
    if(A[to][x] == 1) continue;
    go(to, x);
  }
}

int main()
{
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; ++ i)
    P[i] = i;
  for(int i = 0; i < m; ++ i)
  {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    z %= 10;
    G[x].push_back(make_pair(y, z));
    G[y].push_back(make_pair(x, (10 - z) % 10));
    DSU(x, y);
  }
  for(int i = 1; i <= n; ++ i)
  {
    int x = Parent(i);
    C[x].push_back(i);
  }

  for(int i = 1; i <= n; ++ i)
  {
    if(C[i].size() == 0) continue;

    int x = C[i][0];
    go(x, 0);

    for(int j = 0; j < C[i].size(); ++ j)
    {
      int x = C[i][j];
      for(int dig = 0; dig < 10; ++ dig)
        if(A[x][dig])
          a[x] += (1 << dig);
    }
    for(int bit = 0; bit < (1024); ++ bit)
    {
      bb[bit] = 0;
      for(int j = 0; j < C[i].size(); ++ j)
        if((bit & a[C[i][j]]))
          bb[bit] ++;
    }

    for(int dig = 0; dig < 10; ++ dig)
    {
      for(int j = 0; j < C[i].size(); ++ j)
      {
        int x = C[i][j]; int bit = 0;
        for(int d = 0; d < 10; ++ d)
          if(A[x][d])
            bit += (1 << ((d + dig) % 10));
        answer[dig] += bb[bit];
        if((bit & a[x]))
          answer[dig] --;
      }
    }

  }

  for(int i = 0; i < 10; ++ i)
    printf("%lld\n", answer[i]);
}

Toll Cost Digits C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    static Tuple<long, long, long>[] edges;
    static long[] parent;
    static long[] rootCost;
    static List<long>[] childs;
    static long[] totalCountsAllComp = new long[10];

    static bool[] visited;

    static void BFS(long root, long n, long m)
    {
        Queue<long> queue = new Queue<long>();
        queue.Enqueue(root);
        long[] totalCounts = new long[10];
        long[] counts = new long[10];
        bool period1 = false, period2 = false, period5 = false;

        while (queue.Count > 0)
        {
            long node = queue.Dequeue();
            foreach (long edge in childs[node])
            {
                if (!visited[edge])
                {
                    visited[edge] = true;
                    long child = edges[edge].Item1 == node ? edges[edge].Item2 : edges[edge].Item1;
                    long edgeCost = edges[edge].Item1 == node ? edges[edge].Item3 : (10 - edges[edge].Item3) % 10;

                    if (parent[child] == 0)
                    {
                        queue.Enqueue(child);
                        parent[child] = node;
                        rootCost[child] = (rootCost[node] + edgeCost) % 10;
                        long oppositeCost = (10 - rootCost[child]) % 10;
                        for (long d = 0; d < 10; d++)
                        {
                            totalCounts[(d + oppositeCost) % 10] += counts[d];
                            totalCounts[(rootCost[child] + 10 - d) % 10] += counts[d];
                        }
                        counts[rootCost[child]]++;
                        totalCounts[rootCost[child]]++;
                        totalCounts[oppositeCost]++;
                    }
                    else // loop
                    {
                        long loopPeriod = (rootCost[node] + edgeCost + (10 - rootCost[child])) % 10;
                        if (loopPeriod == 1 || loopPeriod == 3 || loopPeriod == 7 || loopPeriod == 9)
                            period1 = true;
                        else if (loopPeriod == 2 || loopPeriod == 4 || loopPeriod == 6 || loopPeriod == 8)
                            period2 = true;
                        else if (loopPeriod == 5)
                            period5 = true;
                    }
                }
            }
        }

        long[] loopAdd = new long[10];
        if (period1 || period2 && period5)
        {
            long all = totalCounts.Sum();
            for (long d = 0; d < 10; d++)
                loopAdd[d] = all - totalCounts[d];
        }
        else if (period2)
        {
            for (long d = 0; d < 10; d++)
                loopAdd[d] = totalCounts[(d + 2) % 10] + totalCounts[(d + 4) % 10] + totalCounts[(d + 6) % 10] + totalCounts[(d + 8) % 10];
        }
        else if (period5)
        {
            for (long d = 0; d < 10; d++)
                loopAdd[d] = totalCounts[(d + 5) % 10];
        }
    
        for (long d = 0; d < 10; d++)
            totalCountsAllComp[d] += totalCounts[d] + loopAdd[d];
    }

    static void Main(String[] args)
    {
        string[] tokens_n = Console.ReadLine().Split(' ');
        long n = Convert.ToInt64(tokens_n[0]);
        long m = Convert.ToInt64(tokens_n[1]);
        edges = new Tuple<long, long, long>[m];
        parent = new long[n + 1];
        rootCost = new long[n + 1];
        childs = new List<long>[n + 1];
        visited = new bool[m];

        for (long i = 0; i < m; i++)
        {
            tokens_n = Console.ReadLine().Split(' ');
            long u = Convert.ToInt64(tokens_n[0]);
            long v = Convert.ToInt64(tokens_n[1]);
            long d = Convert.ToInt64(tokens_n[2]) % 10;
            edges[i] = new Tuple<long, long, long>(u, v, d);
            if (childs[u] == null)
                childs[u] = new List<long>();
            if (childs[v] == null)
                childs[v] = new List<long>();
            childs[u].Add(i);
            childs[v].Add(i);
        }

        while (true)
        {
            bool cont = false;
            for (long i = 0; i < m; i++)
            {
                if (!visited[i])
                {
                    BFS(edges[i].Item1, n, m);
                    cont = true;
                    break;
                }
            }
            if (!cont)
                break;
        }


        for (long d = 0; d < 10; d++)
            Console.WriteLine(totalCountsAllComp[d]);
    }
}

Toll Cost Digits Java Solution

import java.io.*;
import java.util.*;
import java.util.function.Consumer;

public class Solution {

  static class IntMySet {
    private static final int MAX_LOAD = 90;

    private int mask;
    private int len;
    private int size;
    private int level;
    private boolean zeroKey;

    private int maxSize;

    public IntMySet() {
      reset(2);
    }

    public IntMySet(int n) {
      reset(n);
    }
    
    public int size() {
      return size + (zeroKey ? 1 : 0);
    }

    void checkSizePut() {
      if (size >= maxSize) {
        rehash(level + 1);
      }
    }

    private void reset(int newLevel) {
      size = 0;
      level = newLevel;
      len = 2 << level;
      mask = len - 1;
      maxSize = (int) (len * MAX_LOAD / 100L);
      keys = new int[len];
      values = new boolean[len];
    }

    private int getIndex(int hash) {
      return hash & mask;
    }

    public static final boolean NOT_FOUND = false;
    private int[] keys;
    private boolean[] values;
    private boolean zeroValue;

    public void clear() {
      Arrays.fill(keys, 0);
      Arrays.fill(values, false);
      size = 0;
      zeroKey = false;
    }

    public void add(int key) {
      if (key == 0) {
        zeroKey = true;
        zeroValue = true;
        return;
      }
      try {
        checkSizePut();
      } catch (Exception e) {

      }
      int index = getIndex(key);
      int plus = 1;
      do {
        int k = keys[index];
        if (k == 0) {
          size++;
          keys[index] = key;
          values[index] = true;
          return;
        } else if (k == key) {
          // update existing
          values[index] = true;
          return;
        }
        index = (index + plus++) & mask;
      } while (plus <= len);
    }

    protected void rehash(int newLevel) {
      int[] oldKeys = keys;
      boolean[] oldValues = values;
      reset(newLevel);
      for (int i = 0; i < oldKeys.length; i++) {
        int k = oldKeys[i];
        if (k != 0 && oldValues[i]) {
          add(k);
        }
      }
    }

    public void forEach(Consumer<Integer> action) {
      if (zeroKey) {
        action.accept(0);
      }
      for (int x : keys) {
        if (x > 0) {
          action.accept(x);
        }
      }
    }
    
    public boolean contains(int key) {
      if (key == 0) {
        return zeroKey ? zeroValue : NOT_FOUND;
      }
      int index = getIndex(key);
      int plus = 1;
      do {
        int k = keys[index];
        if (k == 0 && !values[index]) {
          // found an empty record
          return NOT_FOUND;
        } else if (k == key) {
          // found it
          return values[index];
        }
        index = (index + plus++) & mask;
      } while (plus <= len);
      return NOT_FOUND;
    }

    public boolean isEmpty() {
      return size() == 0;
    }
  }
  
  static int[] nxt;
  static int[] succ;
  static int[] ptr;
  static int index = 1;

  static void addEdge(int u, int v) {
    nxt[index] = ptr[u];
    ptr[u] = index;
    succ[index++] = v;
  }

  static boolean[] vis;
  static IntMySet group = new IntMySet(10);
  static Deque<Integer> queue = new ArrayDeque<>();

  static void bfs(int src) {
    vis[src] = true;
    group.clear();
    queue.clear();

    group.add(src * 10);
    queue.add(src * 10);
    
    while (!queue.isEmpty()) {
      int u = queue.removeFirst();
      int wb = u % 10;
      u /= 10;
      for (int i = ptr[u]; i > 0; i = nxt[i]) {
        int vw = succ[i];
        int v = vw / 10;
        int w = (wb + (vw % 10)) % 10;
        int vwn = v * 10 + w;
        if (!group.contains(vwn)) {
          group.add(vwn);
          queue.add(vwn);
          vis[v] = true;
        }
      }
    }
  }

  static long[] ans = new long[10];

  private static void solve() {
    Map<Integer, Integer> hm = new HashMap<>();
    Map<Integer, Integer> counts = new HashMap<>();
    group.forEach(j -> hm.put(j / 10, 0));
    group.forEach(j -> hm.put(j / 10, hm.get(j / 10) | (1 << j % 10)));
    
    for (int j : hm.keySet()) {
      counts.put(hm.get(j), 0);
    }
    for (int j : hm.keySet()) {
      counts.put(hm.get(j), counts.get(hm.get(j)) + 1);
    }
    Map<Integer, Set<Integer>> atlas = new HashMap<>();
    for (int j : counts.keySet()) {
      atlas.put(j, new HashSet<>());
      for (int k = 0; k < 10; k++) {
        if (((1 << k) & j) > 0)
          atlas.get(j).add(k);
      }
    }

    for (int j : counts.keySet()) {
      for (int k : counts.keySet()) {
        for (int c = 0; c < 10; c++) {
          for (int b : atlas.get(k)) {
            if (atlas.get(j).contains((c + b) % 10)) {
              if (j == k)
                ans[c] += (long) counts.get(j) * (counts.get(k) - 1);
              else
                ans[c] += (long) counts.get(j) * counts.get(k);
              break;
            }
          }
        }
      }
    }    
  }
  
  public static void main(String[] args) throws IOException {   
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int roadNodes = Integer.parseInt(st.nextToken());
    int roadEdges = Integer.parseInt(st.nextToken());

    nxt = new int[2 * roadEdges + 1];
    succ = new int[2 * roadEdges + 1];
    ptr = new int[roadEdges];

    for (int i = 0; i < roadEdges; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken()) - 1;
      int v = Integer.parseInt(st.nextToken()) - 1;
      int w = Integer.parseInt(st.nextToken()) % 10;

      addEdge(u, v * 10 + w);
      addEdge(v, u * 10 + (10 - w) % 10);
    }

    vis = new boolean[roadNodes];
    for (int i = 0; i < roadNodes; i++) {
      if (!vis[i]) {
        bfs(i);
        solve();
      }
    }

    for (long x : ans) {
      bw.write(x + "\n");
    }

    bw.close();
    br.close();
  }
}

Toll Cost Digits Python Solution

#!/bin/python3

import sys
import itertools as it

n,e = input().strip().split(' ')
n,e = [int(n),int(e)]
connections =[]
for a0 in range(e):
    x,y,r = input().strip().split(' ')
    x,y,r = [int(x),int(y),int(r)]
    connections.append([x-1,y-1,r%10])
nNodes = n
nCon = e

Paths = {m:[] for m in range(nNodes)}
for i1 in connections:
    Paths[i1[0]].append((i1[1],i1[2]))
    Paths[i1[1]].append((i1[0],(10-i1[2])%10))   
    
StartNodeSet = set([m for m in range(nNodes)])    
TollSumFromZero = {m:set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
    Out = [0 for m in range(10)]
    for i1 in Comb[0]:
        for i2 in Comb[1]:
            Out[(i1-i2)%10] = 1
    return Out

while len(StartNodeSet) > 0:
    SubGraphNodes = set()
    StartNode = StartNodeSet.pop()
    SubGraphNodes.add(StartNode)
    StartIterList = []    
    for i1 in Paths[StartNode]:
        if i1[1] not in TollSumFromZero[i1[0]]:
            TollSumFromZero[i1[0]].add(i1[1])
            StartIterList.append(i1)
            
    
    
    SIListNew = []
    #DenseGraph = False
#    Count = 0
    while len(StartIterList) > 0:# and not DenseGraph:
        for i1 in StartIterList:
            if i1[0] in StartNodeSet:
                StartNodeSet.remove(i1[0])
                SubGraphNodes.add(i1[0])
            for i2 in Paths[i1[0]]:
#                Count += 1
                NewTollDig = (i1[1]+i2[1])%10
                if NewTollDig not in TollSumFromZero[i2[0]]:
                    TollSumFromZero[i2[0]].add(NewTollDig)
    #                if len(TollSumFromZero[i2[0]]) == 10:
    #                    DenseGraph = True
                    SIListNew.append((i2[0],NewTollDig))
        StartIterList = SIListNew
        SIListNew = []
    

    SubgraphDict1 = {}
    for key in SubGraphNodes:
        FD = frozenset(TollSumFromZero[key])
        if SubgraphDict1.get(FD) == None:
            SubgraphDict1[FD] = 1
        else:
            SubgraphDict1[FD] += 1

    for Comb in it.product(SubgraphDict1.keys(),repeat=2):
        if CombDict.get(Comb) == None:
            CombDict[Comb] = CombineSetPair(Comb)
        MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
        if Comb[0] == Comb[1]:
            MultFactor -= SubgraphDict1[Comb[0]]
#        print(Comb,'___',MultFactor,[m for m in range(10) if CombDict[Comb][m] > 0])
        if MultFactor > 0:
            CD = CombDict[Comb]
            for i1 in range(10):
                MasterOut[i1] += MultFactor * CD[i1]

    
    
for I1,i1 in enumerate(MasterOut):
    print(i1)
c C# C++ HackerRank Solutions java javascript python

Leave a Reply