Problem Description

You have a 2D grid representing a campus with n workers and m bikes positioned at various coordinates. The number of bikes is always greater than or equal to the number of workers (n ≤ m).

Your task is to assign exactly one bike to each worker such that:

• Every worker gets exactly one unique bike
• No two workers share the same bike
• The total sum of Manhattan distances between all worker-bike pairs is minimized

The Manhattan distance between two points p1 and p2 is calculated as: |p1.x - p2.x| + |p1.y - p2.y|

For example, if a worker is at position (1, 2) and a bike is at position (3, 5), the Manhattan distance would be |1-3| + |2-5| = 2 + 3 = 5.

The solution uses dynamic programming with bitmask to track which bikes have been assigned. The state f[i][j] represents the minimum total distance when assigning bikes to the first i workers, where j is a bitmask indicating which bikes have been used (if the k-th bit of j is 1, the k-th bike has been assigned).

The algorithm iterates through each worker and considers all possible bike assignments, updating the minimum distance for each valid configuration. The final answer is the minimum value among all possible complete assignments for all n workers.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: While we have workers and bikes on a 2D grid, this is not a graph traversal problem with nodes and edges. We're dealing with an assignment optimization problem.

Need to solve for kth smallest/largest?

• No: We're looking for the minimum total distance, not the kth smallest/largest element.

Involves Linked Lists?

• No: The problem involves 2D coordinates and assignments, not linked list operations.

Does the problem have small constraints?

• Yes: The constraint n ≤ m and the fact that we need to try different combinations of worker-bike assignments suggests relatively small constraints. With n workers and m bikes, we need to explore different assignment combinations, which becomes computationally expensive for large values.

Brute force / Backtracking?

• Yes: We need to explore different ways to assign bikes to workers. Each worker can potentially be paired with any available bike, and we need to try different combinations to find the optimal assignment that minimizes the total Manhattan distance.

Conclusion: The flowchart suggests using a backtracking approach for this problem. We systematically try assigning each worker to different available bikes, keep track of used bikes, and backtrack when needed to explore other possibilities. The solution actually implements this using dynamic programming with bitmask (which is an optimized version of the backtracking idea), where the bitmask represents which bikes have been assigned, effectively encoding the backtracking state space.

Intuition

When we first look at this problem, the natural instinct is to try all possible ways to assign bikes to workers. With n workers and m bikes, we need to choose n bikes from m options and assign them to workers in a way that minimizes total distance.

The key insight is that this is fundamentally an assignment problem where:

1. Each worker must get exactly one bike
2. Each bike can only be assigned to one worker
3. We want the optimal (minimum cost) assignment

If we think about solving this recursively, for each worker, we could try assigning them to any available bike, then solve the remaining subproblem. This naturally leads to a backtracking approach where we:

• Assign worker 0 to an available bike
• Recursively assign the remaining workers to remaining bikes
• Track the minimum total distance across all valid assignments

However, pure backtracking would involve a lot of repeated calculations. For instance, if workers 0 and 1 are assigned bikes 3 and 5, the optimal assignment for the remaining workers would be the same regardless of whether worker 0 got bike 3 or bike 5 (as long as the set of used bikes is the same).

This observation leads us to dynamic programming with states. The state we need to track is:

• Which worker we're currently assigning (worker index i)
• Which bikes have already been used (a set of used bikes)

Since we need to track a subset of bikes, we can use a bitmask where each bit represents whether a bike is used (1) or available (0). For example, if bikes 0 and 2 are used, the bitmask would be 101 in binary or 5 in decimal.

The DP state f[i][j] represents: "What's the minimum distance to assign bikes to the first i workers, where j (as a bitmask) indicates which bikes have been used?"

For each state, we try assigning the current worker to each available bike (where bit is 1 in the mask), calculate the distance, and add it to the optimal solution for the previous workers with that bike removed from the available set. This effectively explores all possible assignments while avoiding redundant calculations through memoization.

Learn more about Dynamic Programming, Backtracking and Bitmask patterns.

Solution Approach

The solution implements dynamic programming with bitmask to efficiently explore all possible worker-bike assignments.

Data Structure:

• A 2D DP table f[i][j] where:
  • i represents the number of workers we've assigned bikes to (from 0 to n)
  • j is a bitmask representing which bikes have been used
  • f[i][j] stores the minimum total Manhattan distance for this configuration

Initialization:

• Create a DP table with dimensions (n+1) × (2^m) initialized to infinity
• Set f[0][0] = 0 as the base case (0 workers assigned, no bikes used, distance is 0)

Main Algorithm:

1. Iterate through each worker i from 1 to n:
   • For each possible bike configuration j (from 0 to 2^m - 1):
     • Try assigning each bike k to the current worker
     • Check if bike k is available in the current mask: j >> k & 1
       • This checks if the k-th bit is set to 1
     • If bike k is available:
       • Calculate the Manhattan distance between worker i-1 and bike k
       • The previous state would be f[i-1][j ^ (1 << k)]
         • j ^ (1 << k) removes bike k from the used set (flips the k-th bit)
       • Update: f[i][j] = min(f[i][j], f[i-1][previous_state] + distance)

Finding the Answer:

• After processing all workers, the answer is min(f[n])
• This finds the minimum value among all possible ways to assign all n workers to bikes

Time Complexity: O(n × 2^m × m) where we have n workers, 2^m possible bike configurations, and check m bikes for each state.

Space Complexity: O(n × 2^m) for the DP table.

The bitmask technique elegantly handles the constraint that each bike can only be used once, while the DP approach ensures we don't recalculate the same subproblems multiple times.

Example Walkthrough

Let's walk through a small example with 2 workers and 3 bikes:

• Workers: [(0, 0), (1, 1)]
• Bikes: [(0, 1), (2, 1), (2, 0)]

Step 1: Initialize DP Table

• Create f[3][8] table (3 rows for 0-2 workers, 8 columns for 2^3=8 bike configurations)
• Initialize all values to infinity except f[0][0] = 0

Step 2: Assign first worker (i=1)

For each possible mask where exactly 1 bike is used:

• Mask 001 (bike 0 used):

  • Distance from worker 0 (0,0) to bike 0 (0,1) = |0-0| + |0-1| = 1
  • f[1][001] = f[0][000] + 1 = 0 + 1 = 1

• Mask 010 (bike 1 used):

  • Distance from worker 0 (0,0) to bike 1 (2,1) = |0-2| + |0-1| = 3
  • f[1][010] = f[0][000] + 3 = 0 + 3 = 3

• Mask 100 (bike 2 used):

  • Distance from worker 0 (0,0) to bike 2 (2,0) = |0-2| + |0-0| = 2
  • f[1][100] = f[0][000] + 2 = 0 + 2 = 2

Step 3: Assign second worker (i=2)

For each mask where exactly 2 bikes are used:

• Mask 011 (bikes 0,1 used):

  • Try bike 0 for worker 1: Previous state f[1][010] = 3
    • Distance: worker 1 (1,1) to bike 0 (0,1) = 1
    • Total: 3 + 1 = 4
  • Try bike 1 for worker 1: Previous state f[1][001] = 1
    • Distance: worker 1 (1,1) to bike 1 (2,1) = 1
    • Total: 1 + 1 = 2
  • f[2][011] = min(4, 2) = 2

• Mask 101 (bikes 0,2 used):

  • Try bike 0 for worker 1: Previous state f[1][100] = 2
    • Distance: worker 1 (1,1) to bike 0 (0,1) = 1
    • Total: 2 + 1 = 3
  • Try bike 2 for worker 1: Previous state f[1][001] = 1
    • Distance: worker 1 (1,1) to bike 2 (2,0) = 2
    • Total: 1 + 2 = 3
  • f[2][101] = min(3, 3) = 3

• Mask 110 (bikes 1,2 used):

  • Try bike 1 for worker 1: Previous state f[1][100] = 2
    • Distance: worker 1 (1,1) to bike 1 (2,1) = 1
    • Total: 2 + 1 = 3
  • Try bike 2 for worker 1: Previous state f[1][010] = 3
    • Distance: worker 1 (1,1) to bike 2 (2,0) = 2
    • Total: 3 + 2 = 5
  • f[2][110] = min(3, 5) = 3

Step 4: Find minimum The answer is min(f[2]) = min(2, 3, 3, ...) = 2

This corresponds to assigning worker 0 to bike 0 (distance 1) and worker 1 to bike 1 (distance 1), for a total minimum distance of 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * 2^m * m)

The algorithm uses dynamic programming with bitmask to track which bikes have been assigned. There are three nested loops:

• The outer loop iterates through n workers: O(n)
• The middle loop iterates through all possible bike assignment states (bitmasks): O(2^m)
• The inner loop iterates through m bikes to check each possible assignment: O(m)

For each combination, we perform constant time operations (checking if a bike is used via bit manipulation, calculating Manhattan distance, and updating the minimum). Therefore, the overall time complexity is O(n * 2^m * m).

Space Complexity: O(n * 2^m)

The algorithm uses a 2D DP table f where:

• The first dimension represents workers (from 0 to n): n + 1 rows
• The second dimension represents all possible bike assignment states using bitmask: 2^m columns

Each cell stores a single value (the minimum distance), so the total space required is O((n + 1) * 2^m), which simplifies to O(n * 2^m).

Additional space usage includes the input lists and a few variables for indices and distances, but these don't affect the asymptotic space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Manipulation Logic

A frequent mistake is confusing when a bit represents "used" vs "available". In the provided solution, when (bike_mask >> bike_idx) & 1 returns 1, it means the bike IS used in the current state. However, developers often mistakenly think this means the bike is available to assign.

Wrong interpretation:

# Incorrect: thinking bit=1 means available
if (bike_mask >> bike_idx) & 1:  # This actually means bike is USED
    # Try to assign this bike (WRONG!)

Correct approach:

# Check if bike is used in current mask
if (bike_mask >> bike_idx) & 1:
    # Bike IS used in current state
    # Calculate previous state where this bike wasn't used
    prev_mask = bike_mask ^ (1 << bike_idx)  # Remove this bike

2. Inefficient State Enumeration

Another pitfall is iterating through all possible masks (0 to 2^m - 1) even when many states are invalid. Since we're assigning exactly i bikes to i workers, we should only consider masks with exactly i bits set.

Inefficient version:

for bike_mask in range(1 << num_bikes):  # Checks ALL possible masks
    # Many of these masks have wrong number of bikes selected

Optimized solution:

# Only iterate through masks with exactly i bikes selected
for bike_mask in range(1 << num_bikes):
    if bin(bike_mask).count('1') == worker_idx:  # Only valid states
        for bike_idx in range(num_bikes):
            if (bike_mask >> bike_idx) & 1:
                # Process valid assignment

3. Memory Overflow with Large Input

When the number of bikes is large (e.g., m = 20), the DP table size becomes 21 × 2^20, which can cause memory issues. Consider using rolling array optimization or memoization with dictionary.

Memory-efficient alternative using dictionary:

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(worker_idx, bike_mask):
    if worker_idx == num_workers:
        return 0
  
    min_dist = float('inf')
    for bike_idx in range(num_bikes):
        if not (bike_mask >> bike_idx) & 1:  # Bike not used
            dist = manhattan_distance(workers[worker_idx], bikes[bike_idx])
            min_dist = min(min_dist, dist + dp(worker_idx + 1, bike_mask | (1 << bike_idx)))
  
    return min_dist

4. Index Confusion Between Workers and DP Table

The DP table uses 1-based indexing for workers (dp[1] for first worker) while the workers array uses 0-based indexing. This often leads to off-by-one errors.

Common mistake:

# Wrong: forgetting to subtract 1
worker_x, worker_y = workers[worker_idx]  # Should be worker_idx - 1

Correct indexing:

# Correct: properly adjust index
worker_x, worker_y = workers[worker_idx - 1]  # DP uses 1-based, array uses 0-based