Sort by

recency

|

104 Discussions

|

2 months ago+ 0 comments

Organized Shop – Python approach clarification (parity & greedy strategy) Hi all 👋, I’m solving the Organized Shop problem in Python and would appreciate help validating my approach. My test is partially passing need some help! If someone has already passed this

The Organized Shop

The owner of HackerMall loves organized items. A row of items is organized if the parity (even or odd) is different for each adjacent stack of items. To organize the row, half of the items in any stack can be removed. This can happen as many times and on as many stacks as is required. Determine the minimum number of operations needed to organize a row. More formally, given an array items/ of integer of length n, the array is organized if for each x less than n- 1, itemsíx] mod 2!= itemsfx+ 1 mod 2. A mod B is the remainder of A divided by B. In one operation, the owner can choose an element and divide it by 2. That is, if one chooses index x then do itemsixd = floor( itemsix)/2). The goal is to return the minimum number of operations that one needs to perform to organize the array,

4 months ago+ 0 comments

found this problem really interesting because it balances graph traversal with bitmask optimization. It’s great to see how combining shortest path algorithms with state representation can handle multiple conditions Sprinter van efficiently. Definitely a good challenge to strengthen problem-solving skills.

6 months ago+ 0 comments

import math
import os
import heapq  # Import heapq for the priority queue
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
#

def shop(n, k, centers, roads):
    # Step 1: Pre-process the centers input to store fish masks
    fish_masks = [0] * (n + 1)
    for i, center_fish_str in enumerate(centers):
        # The input is a string of space-separated integers
        center_fish = list(map(int, center_fish_str.split()))
        if not center_fish:
            continue
        # The first integer is the count, the rest are fish types
        num_fish = center_fish[0]
        for j in range(1, num_fish + 1):
            fish_type = center_fish[j]
            fish_masks[i + 1] |= (1 << (fish_type - 1))
    
    # Step 2: Build the adjacency list for the graph
    adj = [[] for _ in range(n + 1)]
    for road in roads:
        u, v, w = road
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    # Step 3: Run Dijkstra's with a state-space (node, fish_mask)
    # distances[node][mask] stores the minimum time to reach 'node' having collected fish in 'mask'
    distances = [[float('inf')] * (1 << k) for _ in range(n + 1)]
    
    # Priority queue: (time, node, fish_mask)
    pq = [(0, 1, fish_masks[1])]
    distances[1][fish_masks[1]] = 0

    while pq:
        time, u, mask = heapq.heappop(pq)

        if time > distances[u][mask]:
            continue

        for v, weight in adj[u]:
            new_mask = mask | fish_masks[v]
            new_time = time + weight

            if new_time < distances[v][new_mask]:
                distances[v][new_mask] = new_time
                heapq.heappush(pq, (new_time, v, new_mask))

    # Step 4: Calculate the minimum time for two cats
    min_total_time = float('inf')
    full_mask = (1 << k) - 1

    for mask1 in range(1 << k):
        for mask2 in range(mask1, 1 << k):
            if (mask1 | mask2) == full_mask:
                # Time is the maximum of the two cats' path times
                time_cat1 = distances[n][mask1]
                time_cat2 = distances[n][mask2]
                
                # Check for unreachable states
                if time_cat1 != float('inf') and time_cat2 != float('inf'):
                    min_total_time = min(min_total_time, max(time_cat1, time_cat2))

    return min_total_time


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()

6 months ago+ 0 comments

include

using namespace std;

const int MAXN = 1005; const int MAXK = 11; const int MAX_MASK = (1 << MAXK);

int n, m, k; vector> adj[MAXN]; int fish_types[MAXN]; int dist[MAXN][MAX_MASK];

void dijkstra() { // Priority queue stores {distance, {node, fish_mask}} priority_queue>, vector>>, greater>>> pq;

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < (1 << k); ++j) {
        dist[i][j] = INT_MAX;
    }
}

// Start at center 1 with the fish available there.
dist[1][fish_types[1]] = 0;
pq.push({0, {1, fish_types[1]}});

while (!pq.empty()) {
    auto [current_dist, state] = pq.top();
    pq.pop();
    int u = state.first;
    int current_mask = state.second;

    if (current_dist > dist[u][current_mask]) {
        continue;
    }

    // Explore neighbors
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        int new_mask = current_mask | fish_types[v];
        int new_dist = current_dist + weight;

        if (new_dist < dist[v][new_mask]) {
            dist[v][new_mask] = new_dist;
            pq.push({new_dist, {v, new_mask}});
        }
    }
}

}

int main() { cin >> n >> m >> k;

// Read fish types for each center
for (int i = 1; i <= n; ++i) {
    int t;
    cin >> t;
    int mask = 0;
    for (int j = 0; j < t; ++j) {
        int fish_type;
        cin >> fish_type;
        mask |= (1 << (fish_type - 1));
    }
    fish_types[i] = mask;
}

// Read roads and build adjacency list
for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

dijkstra();

int full_mask = (1 << k) - 1;
int min_time = INT_MAX;

// Check pairs of paths for the two cats
for (int mask1 = 0; mask1 < (1 << k); ++mask1) {
    for (int mask2 = 0; mask2 < (1 << k); ++mask2) {
        if ((mask1 | mask2) == full_mask) {
            if (dist[n][mask1] != INT_MAX && dist[n][mask2] != INT_MAX) {
                min_time = min(min_time, max(dist[n][mask1], dist[n][mask2]));
            }
        }
    }
}

cout << min_time << endl;

return 0;

}

6 months ago+ 0 comments

include

using namespace std;

const int MAXN = 1005; const int MAXK = 11; const int MAX_MASK = (1 << MAXK);

int n, m, k; vector> adj[MAXN]; int fish_types[MAXN]; int dist[MAXN][MAX_MASK];

void dijkstra() { // Priority queue stores {distance, {node, fish_mask}} priority_queue>, vector>>, greater>>> pq;

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < (1 << k); ++j) {
        dist[i][j] = INT_MAX;
    }
}

// Start at center 1 with the fish available there.
dist[1][fish_types[1]] = 0;
pq.push({0, {1, fish_types[1]}});

while (!pq.empty()) {
    auto [current_dist, state] = pq.top();
    pq.pop();
    int u = state.first;
    int current_mask = state.second;

    if (current_dist > dist[u][current_mask]) {
        continue;
    }

    // Explore neighbors
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        int new_mask = current_mask | fish_types[v];
        int new_dist = current_dist + weight;

        if (new_dist < dist[v][new_mask]) {
            dist[v][new_mask] = new_dist;
            pq.push({new_dist, {v, new_mask}});
        }
    }
}

}

int main() { cin >> n >> m >> k;

// Read fish types for each center
for (int i = 1; i <= n; ++i) {
    int t;
    cin >> t;
    int mask = 0;
    for (int j = 0; j < t; ++j) {
        int fish_type;
        cin >> fish_type;
        mask |= (1 << (fish_type - 1));
    }
    fish_types[i] = mask;
}

// Read roads and build adjacency list
for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

dijkstra();

int full_mask = (1 << k) - 1;
int min_time = INT_MAX;

// Check pairs of paths for the two cats
for (int mask1 = 0; mask1 < (1 << k); ++mask1) {
    for (int mask2 = 0; mask2 < (1 << k); ++mask2) {
        if ((mask1 | mask2) == full_mask) {
            if (dist[n][mask1] != INT_MAX && dist[n][mask2] != INT_MAX) {
                min_time = min(min_time, max(dist[n][mask1], dist[n][mask2]));
            }
        }
    }
}

cout << min_time << endl;

return 0;

}

Sort by

|

104 Discussions

|

include

include

include

include

include

include

include

include

include

include

include

include

Cookie support is required to access HackerRank