Problem Description

The "Campus Bikes II" problem involves assigning bikes to workers on a campus such that the total distance all workers have to walk to their assigned bikes is minimized. You are given two lists: workers and bikes, each containing coordinates on a 2D grid. Each worker must be assigned exactly one bike, and each bike can be assigned to at most one worker. The goal is to find an assignment such that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

• Key constraints:
  • Each worker must get exactly one bike.
  • No bike can be assigned to more than one worker.
  • There is only one valid solution with the minimum total distance.
  • Input sizes: workers.length ≤ 10, bikes.length ≤ 10
• Input:
  • workers: List of [x, y] coordinates for each worker
  • bikes: List of [x, y] coordinates for each bike
• Output:
  • The minimum possible sum of Manhattan distances for a valid assignment

Thought Process

At first glance, this problem resembles the "assignment problem," where we want to pair workers and bikes in the most optimal way. A brute-force approach would be to try every possible assignment of bikes to workers, calculate the total distance for each, and pick the minimum. However, since the number of possible assignments is factorial in the number of workers (and bikes), this becomes infeasible for larger inputs.

Given the constraints (both lists ≤ 10), the brute-force approach is technically possible, but there are smarter ways to reduce redundant calculations. The key insight is that we can use bitmask dynamic programming (DP) to efficiently track which bikes have already been assigned and avoid recalculating the same scenarios. This approach leverages memoization to store results for subproblems, significantly reducing the number of computations.

In summary, the thought process moves from:

• Trying all permutations (brute-force)
• Realizing the inefficiency due to repeated subproblems
• Shifting to a DP approach with state compression using bitmasks

Solution Approach

To solve this problem efficiently, we'll use a recursive DP approach with memoization, representing the state of assigned bikes using a bitmask. Here's a step-by-step breakdown:

1. Define the State:
   • Let i be the index of the current worker we're assigning a bike to.
   • Let mask be an integer where the k-th bit is 1 if the k-th bike has been assigned, and 0 otherwise.
2. Recursive Function:
   • For each worker, try all bikes that have not been assigned yet.
   • For each valid assignment, calculate the Manhattan distance and recursively solve for the next worker with the updated mask.
   • Memoize the result for each state (i, mask) to avoid recomputation.
3. Base Case:
   • If all workers have been assigned bikes (i == number of workers), return 0 (no more distance to add).
4. Manhattan Distance:
   • For two points (x1, y1) and (x2, y2), the Manhattan distance is |x1 - x2| + |y1 - y2|.
5. Optimization:
   • Use a hash map (or array) to memoize results for each (i, mask) state. This ensures we only compute each subproblem once.

This method ensures that every possible assignment is considered, but redundant calculations are eliminated, making the solution both correct and efficient.

Example Walkthrough

Let's consider an example:

Input:
workers = [[0,0], [2,1]]
bikes = [[1,2], [3,3]]

1. Assign worker 0 to bike 0:
   • Distance: |0-1| + |0-2| = 1 + 2 = 3
   • Now assign worker 1 to remaining bike 1:
   • Distance: |2-3| + |1-3| = 1 + 2 = 3
   • Total: 3 + 3 = 6
2. Assign worker 0 to bike 1:
   • Distance: |0-3| + |0-3| = 3 + 3 = 6
   • Now assign worker 1 to remaining bike 0:
   • Distance: |2-1| + |1-2| = 1 + 1 = 2
   • Total: 6 + 2 = 8
3. The minimal total distance is 6 (from the first assignment).

The DP approach will efficiently compute both options and return 6.

Time and Space Complexity

• Brute-force Approach:
  • There are n! possible assignments (where n is the number of workers/bikes).
  • For each assignment, we compute the sum of distances, so total time is O(n! * n).
• Optimized DP Approach:
  • There are n workers and 2^m possible bike assignment masks (m = number of bikes).
  • Each state is defined by (i, mask), so total states are n * 2^m.
  • For each state, we try up to m options, so total time is O(n * 2^m * m).
  • Space complexity is O(n * 2^m) due to memoization.
• Given the constraints (n, m ≤ 10), this is efficient and feasible.

Summary

In the "Campus Bikes II" problem, we seek the optimal way to assign bikes to workers to minimize total walking distance, with the constraint that each bike and worker is used exactly once. While a brute-force solution is possible due to small input sizes, a more elegant and efficient approach uses dynamic programming with bitmasking to avoid redundant calculations. This approach leverages memoization to ensure each state is only computed once, leading to a solution that is both fast and easy to understand. The problem is a classic example of state compression DP and is highly instructive for learning about assignment problems and optimization strategies.

Code Implementation

from functools import lru_cache

class Solution:
    def assignBikes(self, workers, bikes):
        n, m = len(workers), len(bikes)
        
        @lru_cache(None)
        def dp(i, mask):
            if i == n:
                return 0
            res = float('inf')
            for j in range(m):
                if not (mask & (1 << j)):
                    dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
                    res = min(res, dist + dp(i + 1, mask | (1 << j)))
            return res
        
        return dp(0, 0)
      

class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int n = workers.size(), m = bikes.size();
        vector<vector<int>> memo(n, vector<int>(1 << m, -1));
        
        function<int(int, int)> dp = [&](int i, int mask) {
            if (i == n) return 0;
            if (memo[i][mask] != -1) return memo[i][mask];
            int res = INT_MAX;
            for (int j = 0; j < m; ++j) {
                if (!(mask & (1 << j))) {
                    int dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                    res = min(res, dist + dp(i + 1, mask | (1 << j)));
                }
            }
            return memo[i][mask] = res;
        };
        return dp(0, 0);
    }
};
      

class Solution {
    public int assignBikes(int[][] workers, int[][] bikes) {
        int n = workers.length, m = bikes.length;
        Integer[][] memo = new Integer[n][1 << m];
        return dp(0, 0, workers, bikes, memo);
    }
    private int dp(int i, int mask, int[][] workers, int[][] bikes, Integer[][] memo) {
        if (i == workers.length) return 0;
        if (memo[i][mask] != null) return memo[i][mask];
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < bikes.length; ++j) {
            if ((mask & (1 << j)) == 0) {
                int dist = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                res = Math.min(res, dist + dp(i + 1, mask | (1 << j), workers, bikes, memo));
            }
        }
        memo[i][mask] = res;
        return res;
    }
}
      

var assignBikes = function(workers, bikes) {
    const n = workers.length, m = bikes.length;
    const memo = Array.from({length: n}, () => Array(1 << m).fill(undefined));
    function dp(i, mask) {
        if (i === n) return 0;
        if (memo[i][mask] !== undefined) return memo[i][mask];
        let res = Infinity;
        for (let j = 0; j < m; ++j) {
            if ((mask & (1 << j)) === 0) {
                const dist = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                res = Math.min(res, dist + dp(i + 1, mask | (1 << j)));
            }
        }
        memo[i][mask] = res;
        return res;
    }
    return dp(0, 0);
};