We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Manhattan Distances of All Arrangements of Pieces

Difficulty: Hard

Problem Description

You are given three integers m, n, and k. There is a rectangular grid of size m × n containing k identical pieces. Return the sum of Manhattan distances between every pair of pieces over all valid arrangements of pieces. A valid arrangement is a placement of all k pieces on the grid with at most one piece per cell. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.
  • The task involves calculating distances for all arrangements of k pieces on an m × n grid.
  • Instead of generating all arrangements, we can use combinatorial mathematics to derive the total distances.
  • The contributions to the Manhattan distance can be broken down into contributions from the x-coordinates and y-coordinates separately.
  • For each coordinate, the arrangement of pieces can be treated independently.

Space and Time Complexity

Time Complexity: O(n + m)
Space Complexity: O(1)

Solution

To solve the problem, we can break down the total Manhattan distance calculation into contributions from x-coordinates and y-coordinates separately.

  1. Combinatorial Counting: We will calculate the number of ways to choose k positions from m*n cells.
  2. Distance Contribution: For each possible coordinate, we can calculate how much distance a specific coordinate contributes to the overall Manhattan distance by considering how many pieces are placed at each coordinate.
  3. Final Calculation: Combine the contributions from both x and y coordinates, and return the result modulo 10^9 + 7.

Code Solutions

def manhattanDistance(m, n, k):
    MOD = 10**9 + 7

    def total_distance(s, k):
        total = 0
        for i in range(s):
            # Calculate the number of pairs that involve this coordinate
            # The distance contribution from this coordinate
            total += (i * (k * (s - k)) + (s - i - 1) * (k * (k - 1) // 2))
            total %= MOD
        return total

    dist_x = total_distance(m, k)
    dist_y = total_distance(n, k)

    # The total distance is the sum of x and y contributions
    return (dist_x + dist_y) % MOD
← Back to All Questions