PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Binary search, basic graph algorithms (one of DSU/DFS/BFS)
PROBLEM:
You’re given an N\times M grid that contains every integer from 1 to N\cdot M.
Find the largest integer X such that it’s possible to sort the grid in row-major order by performing the following operation:
- Choose cells (i, j) and (k, l) such that (|i-k|+1) \cdot (|j-l|+1) \ge X, and swap their values.
EXPLANATION:
Since the condition for being able to swap is that the given product is at least X (rather than exactly X), reducing X will only give us more options for swaps.
In particular, if it’s possible to sort the grid appropriately with parameter X, then it can certainly be sorted using X-1 as well.
So, if we’re able to quickly check whether the grid can be sorted with a fixed X, we can then apply binary search to find the maximum valid X for an extra \mathcal{O}(\log{(NM)}) cost which is perfectly reasonable.
We thus focus on just this.
Now, X is fixed, and we want to know if we can convert the grid to the necessary order.
The standard method of doing this is as follows:
- Consider a graph, where each cell corresponds to a vertex.
- For each pair of cells (i, j) and (k, l) such that (|i-k|+1) \cdot (|j-l|+1) \ge X, add an edge between these two cells.
So, edges of the graph signify possible swaps. - Then, for each value v \in [1, NM], if the position currently containing v and the position we want v to be in are in the same connected component of this graph, it’s possible to move v into position via some sequence of swaps.
Otherwise, it’s impossible to move v to the necessary position.
Thus, a necessary and sufficient condition is that every value must have its current and final position be in the same connected component.
Now, implementing this directly would result in a runtime of \mathcal{O}((NM)^2) because we end up checking every pair of cells against each other.
To improve this, note that we don’t actually care about all possible edges - instead, we only care about the connected components of the resulting graph.
Thus, it suffices to only add extreme edges.
Specifically, observe that:
- Suppose (i, j) and (k, l) can be swapped.
Also suppose that i \le k and j \le l.
Then,- (i, j) can also certainly swap with (N, M), because N-i \ge k-i and M-j \ge l-j
- Similarly, (k, l) can certainly swap with (1, 1).
- (1, 1) itself can swap with (N, M)
- So, looking at just the edges from corners, (i, j) and (k, l) are already in the same connected component!
- Similarly, if i \le k and j \ge l instead, we see the same thing but with the other pair of corners: (1, M) and (N, 1).
Thus, we don’t really need to care about each pair of cells.
Rather, we only need to care about which cells can be reached from each of the four corners of the grid - this will give us enough information to correctly construct the connected components!
This immediately reduces the complexity of the check to \mathcal{O}(NM), since we have only 4NM edges to check now: NM from each corner.
Finding the connected components can be done by explicitly constructing the edges and using a graph traversal algorithm to find them, or by using a data structure like a DSU for easier implementation (at the slight cost of complexity, depending on the optimizations used in the DSU - but logarithmic at worst.)
With binary search on top, we obtain a solution in \mathcal{O}(NM\log(NM)) which is good enough.
TIME COMPLEXITY:
\mathcal{O}(NM\log(NM)) per testcase.
CODE:
Editorialist's code (PyPy3)
# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/DisjointSetUnion.py
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, a):
acopy = a
while a != self.parent[a]:
a = self.parent[a]
while acopy != a:
self.parent[acopy], acopy = a, self.parent[acopy]
return a
def union(self, a, b):
self.parent[self.find(b)] = self.find(a)
def check(grid, x):
n = len(grid)
m = len(grid[0])
dsu = UnionFind(n*m)
for i in range(n):
for j in range(m):
for corner in [[0, 0], [0, m-1], [n-1, 0], [n-1, m-1]]:
dist = (abs(corner[0] - i) + 1) * (abs(corner[1] - j) + 1)
if dist >= x:
dsu.union(i*m + j, corner[0]*m + corner[1])
for i in range(n):
for j in range(m):
val = grid[i][j] - 1
if dsu.find(val) != dsu.find(i*m + j): return False
return True
for _ in range(int(input())):
n, m = map(int, input().split())
grid = []
for i in range(n):
grid.append(list(map(int, input().split())))
lo, hi = 1, n*m + 1
while lo < hi:
mid = (lo + hi + 1)//2
if check(grid, mid): lo = mid
else: hi = mid-1
print(lo)
.