In this 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. Farmville's road system consists of n junctions connected by e bidirectional toll roads, where the ith toll road connects junctions Xi and Yi. In addition, some junctions may not be reachable from others and there may be multiple roads connecting the same pair of junctions.
Problem solution in Python.
#!/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)
Problem solution in Java.
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();
}
}
Problem solution in C++.
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MAXN = 2e5 + 10;
const int VAL = 1e4;
int n;
vector<pair<int, int> > graph[MAXN];
vector<int> vertices;
bool visit[MAXN][20], check[MAXN];
int d[MAXN], new_d[MAXN];
long long res[20], cnt[VAL];
queue<pair<int, int> > queues;
void DFS(int s, int ds) {
queues.push(make_pair(s, ds));
visit[s][ds] = true;
check[s] = true;
while (!queues.empty()) {
int u = queues.front().first, du = queues.front().second;
queues.pop();
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i].first, w = graph[u][i].second;
w = (w + du) % 10;
if (!visit[v][w]) {
if (!check[v]) {
d[v] = (1 << w);
vertices.push_back(v);
} else {
d[v] += (1 << w);
}
check[v] = true;
visit[v][w] = true;
queues.push(make_pair(v, w));
}
}
}
}
void compute() {
for(int i = 0; i <= 9; i++) {
memset(cnt, 0, sizeof(cnt));
for(int j = 0; j < vertices.size(); j++) {
int u = vertices[j], s = 0;
for(int k = 0; k <= 9; k++) {
if ((d[u] | (1 << k)) == d[u]) {
int t = (k + i) % 10;
s += (1 << t);
}
}
new_d[u] = s;
cnt[s]++;
}
for(int j = 0; j < vertices.size(); j++) {
int u = vertices[j];
for(int k = 0; k < (1 << 10); k++) {
if (cnt[k] > 0) {
if ((k & d[u]) > 0) {
res[i] += cnt[k];
}
}
}
if ((d[u] & new_d[u]) > 0) {
res[i]--;
}
}
}
}
int main(){
int e;
scanf("%d %d", &n, &e);
for(int a0 = 0; a0 < e; a0++){
int x, y, r;
scanf("%d %d %d", &x, &y, &r);
r %= 10;
graph[x].push_back(make_pair(y, r));
graph[y].push_back(make_pair(x, 10 - r));
}
memset(check, false, sizeof(check));
for(int i = 1; i <= n; i++) {
if (!check[i]) {
vertices.clear();
vertices.push_back(i);
d[i] = 1;
DFS(i, 0);
compute();
}
}
for(int i = 0; i <= 9; i++) {
cout << res[i] << endl;
}
return 0;
}
Problem solution in C.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _lnode
{
int x;
int w;
struct _lnode *next;
}lnode;
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];
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 & 1 )
{
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;
}
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 & 1 )
{
t1 += temp[j];
}
else
{
t2 += temp[j];
}
}
for( j = 0 ; j < 10 ; j++ )
{
if( j & 1 )
{
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;
}
0 Comments