CF 1137A - Skyscrapers

Rating: 1600
Tags: implementation, sortings
Solve time: 1m 41s
Verified: no

Solution

Problem Understanding

We are given a city laid out as a grid of size $n \times m$, where each cell represents an intersection containing a skyscraper of a certain height. For each intersection at row $i$ and column $j$, we focus on two lines of skyscrapers: the full $i$-th row (Eastern street) and the full $j$-th column (Southern street). Dora wants to reassign integer heights to these skyscrapers, keeping the relative order of heights intact in both the row and column, and using numbers from 1 up to some integer $x$. The goal is to minimize the maximum number $x$ used.

The input consists of $n$ and $m$, followed by the $n \times m$ grid of integers representing initial heights. The output should be a grid of the same size, where each cell contains the minimal possible maximum height $x$ achievable for that intersection.

The constraints allow $n, m \le 1000$, so the grid can be up to $10^6$ cells. A naive solution that solves each intersection independently by sorting its row and column separately would require $O(n m (n + m) \log(n + m))$ operations, which is too slow. This implies we need a solution that preprocesses row and column information once and uses it efficiently for each intersection.

A subtle edge case occurs when rows or columns have duplicate heights. For instance, if a row is [1, 1, 2] and a column is [1, 2, 2], the intersection height can influence both row and column rankings. A careless approach that assigns ranks independently in row and column could violate the relative order in one of the lines.

Another edge case occurs with minimal input, $n = m = 1$. Here, the only intersection's answer is trivially 1, but the algorithm must correctly handle single-element rows and columns without indexing errors.

Approaches

The brute-force approach would be to consider each intersection separately. For the row and column containing that intersection, we would sort and assign ranks starting from 1 for the smallest height, keeping track of the maximum assigned number. Then we compute the maximum number across both sequences, accounting for the overlap at the intersection. This works correctly but is inefficient because sorting each row and column $nm$ times leads to roughly $O(n m (n + m) \log(n + m))$ operations.

The key observation is that the relative ranks of heights within each row and each column can be precomputed. For each row, we can assign a "row rank" to each cell that represents its position in the sorted row. Similarly, for each column, we can assign a "column rank". For the intersection at $(i, j)$, the answer is the maximum of the row rank and column rank plus adjustments if one rank dominates the other, because we need to extend numbers to align the intersection's position in both sequences. This allows computing the answer in constant time per cell after preprocessing, reducing the complexity to $O(n m)$ after $O(n m \log m + n m \log n)$ preprocessing for row and column sorting.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n m (n + m) log(n + m))	O(n + m)	Too slow
Optimal	O(n m log m + n m log n)	O(n m)	Accepted

Algorithm Walkthrough

For each row, extract all heights and compute the rank of each cell within that row. The rank is 1 for the smallest height, 2 for the next smallest, and so on. This ensures the relative order in the row is maintained when remapped to minimal integers.
Repeat the same process for each column, assigning a column rank to each cell. At this stage, we have two matrices of ranks: row_rank[i][j] and col_rank[i][j].
For each cell $(i, j)$, compute the maximum number needed to preserve both row and column orders. Let r = row_rank[i][j] and c = col_rank[i][j]. Let row_len be the number of unique values in row i and col_len be the number of unique values in column j. The minimal maximum value for the intersection is max(r, c) + max(row_len - r, col_len - c). This formula ensures that both sequences can be mapped into [1, x] without breaking order.
Print the resulting matrix of minimal maximum values.

Why it works: row_rank and col_rank encode the minimal relative ordering for each line. At an intersection, the maximal rank among the two determines the starting number for that cell. Any remaining positions to the right in the row or below in the column extend the maximum by the number of remaining unique ranks, guaranteeing no violation of relative ordering.

Python Solution

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

row_rank = [[0]*m for _ in range(n)]
col_rank = [[0]*m for _ in range(n)]

# Compute ranks for rows
for i in range(n):
    vals = sorted(set(a[i]))
    val_to_rank = {v: idx+1 for idx, v in enumerate(vals)}
    for j in range(m):
        row_rank[i][j] = val_to_rank[a[i][j]]

# Compute ranks for columns
for j in range(m):
    col_vals = sorted({a[i][j] for i in range(n)})
    val_to_rank = {v: idx+1 for idx, v in enumerate(col_vals)}
    for i in range(n):
        col_rank[i][j] = val_to_rank[a[i][j]]

# Compute final answers
res = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        r = row_rank[i][j]
        c = col_rank[i][j]
        row_len = len(set(a[i]))
        col_len = len({a[k][j] for k in range(n)})
        res[i][j] = max(r, c) + max(row_len - r, col_len - c)

for row in res:
    print(*row)

The first two sections compute row and column ranks efficiently using sorted sets. Using sets avoids duplicate heights interfering with ranks. The final nested loop computes each intersection's minimal maximum value using the formula described above. One must carefully use len(set(...)) to count unique heights, otherwise duplicates could lead to incorrect results.

Worked Examples

Sample 1:

Input:

2 3
1 2 1
2 1 2

i	j	row_rank	col_rank	row_len	col_len	res
0	0	1	1	2	2	2
0	1	2	2	2	2	2
0	2	1	1	2	2	2
1	0	2	2	2	2	2
1	1	1	1	2	2	2
1	2	2	2	2	2	2

The table confirms that for every intersection, the maximum height needed is 2, as expected.

Sample 2:

Input:

1 4
3 1 2 2

After row ranking: [4, 1, 2, 2] → ranks [4, 1, 2, 2]

Column ranks for each: 1-length columns → [1, 1, 1, 1]

Max formula: max(r,c) + max(row_len - r, col_len - c) → [4, 1, 2, 2]

This shows the algorithm correctly handles single-row cases.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n m log m + n m log n)	Sorting rows and columns to compute ranks dominates the complexity
Space	O(n m)	Storing row ranks, column ranks, and the result grid

The solution is well within the 2-second time limit, as $n, m \le 1000$ implies at most $10^6$ cells, and the sorting step is affordable.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    
    row_rank = [[0]*m for _ in range(n)]
    col_rank = [[0]*m for _ in range(n)]
    
    for i in range(n):
        vals = sorted(set(a[i]))
        val_to_rank = {v: idx+1 for idx, v in enumerate(vals)}
        for j in range(m):
            row_rank