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, "%d\n", res);
fclose(fptr);
return 0;
}
0 Comments