HackerRank Synchronous Shopping problem solution

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;
}