In this HackerRank Synchronous Shopping problem solution, Bitville is a seaside city that has a number of shopping centers connected by bidirectional roads, each of which has a travel time associated with it. Each of the shopping centers may have a fishmonger who sells one or more kinds of fish. Two cats, Big Cat and Little Cat are at shopping center 1 (each of the centers is numbered consecutively from 1 to n). They have a list of fish they want to purchase, and to save time, they will divide the list between them. Determine the total travel time for the cats to purchase all of the types of fish, finally meeting at shopping center n. Their paths may intersect, they may backtrack through shopping centers n, and one may arrive at a different time than the other. The minimum time to determine is when both have arrived at the destination.
Problem solution in Python.
#!/bin/python3 import math import os import random import re import sys # # Complete the 'shop' function below. # # The function is expected to return an INTEGER. # The function accepts following parameters: # 1. INTEGER n # 2. INTEGER k # 3. STRING_ARRAY centers # 4. 2D_INTEGER_ARRAY roads # from collections import deque import heapq def shop(n, k, centers, roads): # Write your code here fish_masks = [0] all_fishes_mask = 2 ** k - 1 f = 1 for _ in range(k): fish_masks.append(f) f <<= 1 cities = [0] * (n + 1) for idx, c_str in enumerate(centers): c_data = list(map(int, c_str.split())) if c_data[0] > 0: cities[idx + 1] = sum([fish_masks[i] for i in c_data[1:]]) neighbours = [[] for _ in range(n+1)] times = [[0] * (n+1) for _ in range(n+1)] for c1, c2, t in roads: neighbours[c1].append(c2) neighbours[c2].append(c1) times[c1][c2] = t times[c2][c1] = t q = [(1 << 10) + cities[1]] seen = [[False] * (all_fishes_mask + 1) for _ in range(n + 1)] trip_time = [[None] * (all_fishes_mask + 1) for _ in range(n + 1)] fish_mask = 2 ** 10 - 1 node_mask = fish_mask << 10 while q: data = heapq.heappop(q) time = data >> 20 node = (data & node_mask) >> 10 f_mask = data & fish_mask if seen[node][f_mask]: continue seen[node][f_mask] = True if (node == n) and (f_mask == all_fishes_mask): continue for nxt in neighbours[node]: nxt_mew_mask = cities[nxt] | f_mask if seen[nxt][nxt_mew_mask]: continue nxt_cur_time = trip_time[nxt][nxt_mew_mask] nxt_new_time = time + times[node][nxt] if (nxt_cur_time is not None) and (nxt_new_time >= nxt_cur_time): continue trip_time[nxt][nxt_mew_mask] = nxt_new_time heapq.heappush(q, (nxt_new_time << 20) + (nxt << 10) + nxt_mew_mask) rv = 0 trip_times = trip_time[n] for mask_i, time_i in enumerate(trip_times): if not time_i: continue for data_j, time_j in enumerate(trip_times[mask_i:]): if not time_j: continue mask_j = mask_i + data_j mask = mask_i | mask_j t_time = max(time_i, time_j) if mask != all_fishes_mask: continue if rv and t_time >= rv: continue rv = t_time return rv if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') first_multiple_input = input().rstrip().split() n = int(first_multiple_input[0]) m = int(first_multiple_input[1]) k = int(first_multiple_input[2]) centers = [] for _ in range(n): centers_item = input() centers.append(centers_item) roads = [] for _ in range(m): roads.append(list(map(int, input().rstrip().split()))) res = shop(n, k, centers, roads) fptr.write(str(res) + 'n') fptr.close()
Problem solution in Java.
import java.io.*; import java.util.*; public class Solution { static class Node { int label, time, status; public Node(int label, int time, int status) { this.label = label; this.time = time; this.status = status; } } private static int minTime(int n, int k, int[] sale, List<List<Node>> graph) { int[][] time = new int[1 << k][n]; for (int[] t : time) Arrays.fill(t, Integer.MAX_VALUE); PriorityQueue<Node> minHeap = new PriorityQueue<>(new Comparator<Node>(){ @Override public int compare(Node n1, Node n2) { return n1.time - n2.time; } }); minHeap.offer(new Node(0, 0, sale[0])); time[sale[0]][0] = 0; List<Node> candidates = new ArrayList<>(); while (!minHeap.isEmpty()) { Node cur = minHeap.poll(); if (cur.label == n - 1) candidates.add(cur); for (Node node : graph.get(cur.label)) { int newStatus = (cur.status | sale[node.label]); if (cur.time + node.time < time[newStatus][node.label]) { time[newStatus][node.label] = cur.time + node.time; minHeap.offer(new Node(node.label, cur.time + node.time, newStatus)); } } } int min = Integer.MAX_VALUE; for (int i = 0; i < candidates.size(); i++) { Node cur = candidates.get(i); for (int j = i; j < candidates.size(); j++) { Node another = candidates.get(j); if ((cur.status | another.status) == (1 << k) - 1) { min = Math.min(min, Math.max(cur.time, another.time)); } } } return min; } private static final Scanner SCANNER = new Scanner(System.in); public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ String nmk = SCANNER.nextLine(); String[] nmkVals = nmk.split(" "); int n = Integer.valueOf(nmkVals[0]), m = Integer.valueOf(nmkVals[1]), k = Integer.valueOf(nmkVals[2]); int[] sale = new int[n]; for (int i = 0; i < n; i++) { String items = SCANNER.nextLine(); String[] types = items.split(" "); for (int j = 1; j < types.length; j++) { sale[i] |= (1 << (Integer.valueOf(types[j]) - 1)); } } List<List<Node>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) graph.add(new ArrayList<>()); for (int i = 0; i < m; i++) { String edge = SCANNER.nextLine(); String[] detail = edge.split(" "); int n1 = Integer.valueOf(detail[0]) - 1, n2 = Integer.valueOf(detail[1]) - 1, t = Integer.valueOf(detail[2]); graph.get(n1).add(new Node(n2, t, 0)); graph.get(n2).add(new Node(n1, t, 0)); } System.out.print(minTime(n, k, sale, graph)); } }
Problem solution in C++.
using namespace std; #include <bits/stdc++.h> #define MAX 1100 #define MOD 1000000007 #define PI 3.1415926535897932384 #define F first #define S second #define pb push_back #define mp make_pair typedef long long ll; int cost[MAX][MAX]; int n, m, k; vector<int> fish[MAX]; vector<pair<int, int> > adj[MAX]; void db(int val){ vector<int> aux; for(int i = 0;i < k;i++){ if(val & (1<<i)){aux.pb(1);} else aux.pb(0); } for(int i = aux.size()-1;i >= 0;i--) cout << aux[i]; } void prepare_spell(){ set<pair<int, pair<int, int> > > my_s; int mask = 0, cur = 0; for(int i = 0;i < fish[cur].size();i++){ mask |= (1<<fish[cur][i]); } my_s.insert(mp(0, mp(cur, mask))); while(!my_s.empty()){ pair<int, pair<int, int> > aux = *my_s.begin(); //cout << aux.F << " " << aux.S.F << " "; db(aux.S.S); cout << endl; my_s.erase(my_s.begin()); if(cost[aux.S.F][aux.S.S] != -1 && cost[aux.S.F][aux.S.S] <= aux.F) continue; cost[aux.S.F][aux.S.S] = aux.F; for(int i = 0;i < adj[aux.S.F].size();i++){ int mask = aux.S.S; for(int j = 0;j < fish[adj[aux.S.F][i].F].size();j++){ mask |= (1<<fish[adj[aux.S.F][i].F][j]); } //cout << aux.S.F << " " << adj[aux.S.F][i].F << " "; db(mask); if(cost[adj[aux.S.F][i].F][mask] == -1 || cost[adj[aux.S.F][i].F][mask] > aux.F+adj[aux.S.F][i].S){ //cout << " aceito" << endl; my_s.insert(mp(aux.F+adj[aux.S.F][i].S, mp(adj[aux.S.F][i].F, mask))); } //else cout << " nao aceito" << endl; } } } int cast_spell(){ int aux = 0; for(int i = 0;i < k;i++) aux |= (1<<i); int res = -1; for(int i = 0;i < MAX;i++){ for(int j = 0;j < MAX;j++){ if((i|j) == aux && cost[n-1][i] != -1 && cost[n-1][j] != -1 && (res == -1 || max(cost[n-1][i], cost[n-1][j]) < res)){ res = max(cost[n-1][i], cost[n-1][j]); } } } return res; } int main(){ //freopen("in", "r", stdin); // freopen("out", "w", stdout); cin >> n >> m >> k; memset(cost, -1, sizeof(cost)); for(int aux, i = 0;i < n;i++){ cin >> aux; for(int f, j = 0;j < aux;j++){ cin >> f; fish[i].pb(f-1); } } for(int a, b, c, i = 0;i < m;i++){ cin >> a >> b >> c; adj[a-1].pb(mp(b-1, c)); adj[b-1].pb(mp(a-1, c)); } prepare_spell(); cout << cast_spell() << endl; return 0; }
Problem solution in C.
#include <assert.h> #include <ctype.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> const int MAX_INT = 1<<30; typedef struct Item { int key; int value; int node; } Item; typedef struct PriorityQueue { Item* arr; int size; int cap; } Queue; Queue* initQueue() { Queue* q = malloc(sizeof(Queue)); q->size = 0; q->cap = 0; q->arr = NULL; return q; } void insert(Queue* q, int key, int value, int node) { if (q->size == q->cap) { q->cap = q->cap * 2 + 1; q->arr = realloc(q->arr, q->cap * sizeof(Item)); } q->arr[q->size].key = key; q->arr[q->size].value = value; q->arr[q->size].node = node; q->size++; // Up-heap int idx = q->size - 1; int parent_idx = (idx - 1) / 2; while (parent_idx >= 0 && q->arr[idx].key < q->arr[parent_idx].key) { Item t = q->arr[idx]; q->arr[idx] = q->arr[parent_idx]; q->arr[parent_idx] = t; idx = parent_idx; parent_idx = (idx - 1) / 2; } } Item extractMin(Queue* q) { Item item = q->arr[0]; q->arr[0] = q->arr[--q->size]; // Down-heap int idx = 0; int left = idx * 2 + 1; int right = idx * 2 + 2; while ( (left < q->size && q->arr[left].key < q->arr[idx].key) || (right < q->size && q->arr[left].key < q->arr[idx].key) ) { if ( left < q->size && q->arr[left].key < q->arr[idx].key && (right >= q->size || q->arr[left].key < q->arr[right].key) ) { Item t = q->arr[idx]; q->arr[idx] = q->arr[left]; q->arr[left] = t; idx = left; } else { Item t = q->arr[idx]; q->arr[idx] = q->arr[right]; q->arr[right] = t; idx = right; } left = idx * 2 + 1; right = idx * 2 + 2; } return item; } int shop(int n, int k, int* t, int* B_size, int** B, int** W) { int** shortest = malloc(n*sizeof(int*)); for (int i=0; i<n; i++) { shortest[i] = malloc((1<<k)*sizeof(int)); for (int j=0; j<(1<<k); j++) { shortest[i][j] = MAX_INT; } } Queue* q = initQueue(); insert(q, 0, t[0], 0); while (q->size > 0) { Item item = extractMin(q); int key = item.key, value=item.value, u = item.node; // if (u == n-1) { // int opp = value ^ ((1<<k) - 1); // for (int i=0; i<=(1<<k)-1; i++) { // if (shortest[u][opp | i] < MAX_INT) return key; // } // } if (item.key >= shortest[u][value]) continue; shortest[u][value] = item.key; for (int i=0; i<B_size[u]; i++) { int v = B[u][i], w = W[u][i]; insert(q, key + w, value | t[v], v); } } int min = MAX_INT; for (int i=0; i<(1<<k); i++) { int cur = shortest[n-1][i]; for (int j=0; j<(1<<k); j++) { if ((i | j) != (1<<k) - 1) continue; int opp = shortest[n-1][j]; if (cur >= opp && min > cur) min = cur; else if (opp >= cur && min > opp) min = opp; } } return min; } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); int n, m, k; scanf("%d%d%d", &n, &m, &k); int* t = malloc(n * sizeof(int)); for (int i=0; i<n; i++) { int n_fishes; scanf("%d", &n_fishes); t[i] = 0; for (int _=0; _<n_fishes; _++) { int fish; scanf("%d", &fish); t[i] |= 1<<(fish-1); } } int* B_size = malloc(n * sizeof(int)); // Vertex order int* B_cap = malloc(n * sizeof(int)); // Capacity of B int** B = malloc(n * sizeof(int*)); // Adjacent list int** W = malloc(n * sizeof(int*)); // Adjacent weight for (int i=0; i<n; i++) { B_size[i] = 0; B_cap[i] = 0; B[i] = NULL; W[i] = NULL; } for (int j=0; j<m; j++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); u--; v--; if (B_size[u] == B_cap[u]) { B_cap[u] = B_cap[u] * 2 + 1; B[u] = realloc(B[u], B_cap[u] * sizeof(int)); W[u] = realloc(W[u], B_cap[u] * sizeof(int)); } B[u][B_size[u]] = v; W[u][B_size[u]] = w; B_size[u]++; if (B_size[v] == B_cap[v]) { B_cap[v] = B_cap[v] * 2 + 1; B[v] = realloc(B[v], B_cap[v] * sizeof(int)); W[v] = realloc(W[v], B_cap[v] * sizeof(int)); } B[v][B_size[v]] = u; W[v][B_size[v]] = w; B_size[v]++; } int res = shop(n, k, t, B_size, B, W); fprintf(fptr, "%dn", res); fclose(fptr); return 0; }