Manhattan Distances of All Arrangements of Pieces - Problem

Math Combinatorics Hard

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.

The Manhattan Distance between two cells (x_i, y_i) and (x_j, y_j) is |x_i - x_j| + |y_i - y_j|.

Input & Output

Example 1 — Small Grid

$ Input: m = 1, n = 2, k = 2

› Output: 1

💡 Note: Only one arrangement possible: both pieces at positions (0,0) and (0,1). Distance = |0-0| + |0-1| = 1.

Example 2 — Square Grid

$ Input: m = 2, n = 2, k = 2

› Output: 8

💡 Note: Grid has 4 cells, C(4,2) = 6 arrangements. Sum of all pairwise distances across arrangements equals 8.

Example 3 — Single Piece

$ Input: m = 3, n = 3, k = 1

› Output: 0

💡 Note: With only one piece, there are no pairs to calculate distance between, so sum is 0.

Constraints

1 ≤ m, n ≤ 100
1 ≤ k ≤ m × n
Answer fits in 32-bit integer after modulo

Visualization

Tap to expand

Asked in

G Google 25 f Meta 18 M Microsoft 15 a Amazon 12

The key insight is to avoid generating all arrangements by using combinatorial mathematics. Split Manhattan distance into x and y components, then for each pair of cells, calculate how many arrangements include both cells using C(total-2, k-2). Best approach is mathematical combinatorics. Time: O(m²×n²), Space: O(1)

Common Approaches

✓ Binary Search Answer

⏱️ Time: N/A Space: N/A

Brute Force Enumeration

⏱️ Time: O(C(m*n, k) * k²) Space: O(k)

Generate all C(m*n, k) possible arrangements of k pieces on the grid. For each arrangement, calculate Manhattan distances between all pairs of pieces and sum them up.

Mathematical Combinatorics

⏱️ Time: O(m² × n²) Space: O(1)

Split Manhattan distance into x and y components. For each component, count how many times each distance appears across all arrangements using combinatorial formulas.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_POSITIONS 10000
#define MAX_COMBINATIONS 100000

typedef struct {
    int row, col;
} Position;

Position positions[MAX_POSITIONS];
int posCount = 0;

int combinations[MAX_COMBINATIONS][50];
int comboCount = 0;

int current[50];
int currentSize = 0;

void generateCombinations(int n, int k, int start) {
    if (currentSize == k) {
        for (int i = 0; i < k; i++) {
            combinations[comboCount][i] = current[i];
        }
        comboCount++;
        return;
    }

    for (int i = start; i <= n - (k - currentSize); i++) {
        current[currentSize++] = i;
        generateCombinations(n, k, i + 1);
        currentSize--;
    }
}

long long solution(int m, int n, int k) {
    long long total = 0;

    // Generate all positions on grid
    posCount = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            positions[posCount].row = i;
            positions[posCount].col = j;
            posCount++;
        }
    }

    // Generate all combinations of k positions
    comboCount = 0;
    currentSize = 0;
    generateCombinations(posCount, k, 0);

    // Calculate sum of distances for each combination
    for (int c = 0; c < comboCount; c++) {
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < k; j++) {
                Position pos1 = positions[combinations[c][i]];
                Position pos2 = positions[combinations[c][j]];
                int dr = pos1.row - pos2.row;
                int dc = pos1.col - pos2.col;
                int dist = (dr < 0 ? -dr : dr) + (dc < 0 ? -dc : dc);
                total = (total + dist) % MOD;
            }
        }
    }

    return total;
}

int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);

    long long result = solution(m, n, k);
    printf("%lld\n", result);

    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

12.4K Views

Medium Frequency

~35 min Avg. Time

285 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen