GridSort
SRM 702 · 2016-11-02 · by lg5293
Problem Statement
Charlie has a grid of n rows by m columns. The rows are numbered 0 through n-1 from top to bottom. The columns are numbered 0 through m-1 from left to right.
Each cell of the grid contains a positive integer. The integers in Charlie's grid are a permutation of the numbers 1 through n*m. (I.e., each of these numbers occurs in the grid exactly once.)
Given a grid, its value list is a sequence constructed by listing all values in the grid in row major order. That is, we first list the values in row 0 from left to right, then the values in row 1 from left to right, and so on.
You are given the
Charlie can modify his grid in two ways: He may swap any two rows, and he may swap any two columns. Charlie now wonders whether there is a sequence of swaps that would sort his grid - that is, rearrange its elements in such a way that the value list of the new grid will be the ordered sequence (1,2,3,...,n*m).
If it is possible to sort Charlie's grid, return "Possible". Otherwise, return "Impossible".
Constraints
- n,m will be between 1 and 50, inclusive.
- grid will be a permutation of [1,...,n*m].
2
2
{
1,2,
3,4
}
Returns: "Possible"
This grid is already sorted, so Charlie doesn't need to do anything.
2
2
{
3,4,
1,2
}
Returns: "Possible"
Charlie can sort this grid by swapping rows 0 and 1.
2
2
{
4,3,
1,2
}
Returns: "Impossible"
1
10
{4,5,1,2,9,8,3,10,7,6}
Returns: "Possible"
3
5
{
10,6,8,9,7,
5,1,3,4,2,
15,11,13,14,12
}
Returns: "Possible"
Submissions are judged against all 98 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GridSort with a public method string sort(int n, int m, vector<int> grid) · 98 test cases · 2 s / 256 MB per case