PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Video Editorial
Author: Alei Reyes
Tester: Suchan Park
DIFFICULTY:
SIMPLE - EASY
PREREQUISITES:
None
PROBLEM:
You are given a matrix of distinct integers A or size N. In one operation you can transpose any submatrix from (1,1) to (X,X). Find the minimum number of operations to sort the matrix.
QUICK EXPLANATION:
- If A_{i,j} \neq A_{j,i} and i>j, then the number of operations with X \geq i should be odd.
- If A_{i,j} = A_{j,i} and i>j, then the number of operations with X \geq i should be even.
- The transpositions can be constructed by greedily satisfying the previous two conditions in decreasing order of X.
EXPLANATION:
A transposition at index X makes all elements at rows and columns less or equal than X to be swapped with its symmetric. After an arbitrary number of operations, each element (i,j) in the matrix can be either in the same position or at (j,i). To find the final position of element (i,j), we have to count the number of operations performed at indices greater or equal than max(i,j), if it is odd (i,j) will be swapped with its symmetric, otherwise it will remain in the same place. Note that the order in which the operations are performed doesn’t matter.
Let’s construct a binary array B, where B_i=1 iff the number of transpositions with X \geq i must be even. We can get B by iterating over the matrix and finding the elements that need to be swapped with their symmetrical.
We can find the a set of transposition operations that satisfies B from right to left. Let’s say B_i=x, and the parity of the number of operations we performed so far (at positions X \gt i) is y, if x=y then we don’t have to do anything because the constraint is already satisfied, otherwise a transposition at X=i is required.
SOLUTIONS:
Setter's Solution
int m[66][66];
int main(){
int t=rint('\n');
int sn2=0;
while(t--){
int n=rint('\n');
assert(4<=n&&n<=64);
sn2+=n*n;
assert(sn2<=3e5);
set<int>all;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
m[i][j]=rint(j==n-1?'\n':' ');
assert(1<=m[i][j]&&m[i][j]<=n*n);
assert(all.count(m[i][j])==0);
all.insert(m[i][j]);
--m[i][j];
}
}
vector<int>d(n);
int c=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i>j && m[i][j]!=c){
d[i]=1;
}
c++;
}
}
int ans=0;
int b=0;
for(int i=n-1;i>0;i--){
if(d[i]!=b){
ans++;
b^=1;
}
}
printf("%d\n",ans);
}
assert(getchar()==EOF);
return 0;
}
Tester's Solution
package ADAMAT
class ADAMAT_SOLUTION (val br: java.io.BufferedReader, val bw: java.io.BufferedWriter) {
var sumN = 0L
fun check() {
require(sumN <= 300000)
}
fun run() {
val N = br.readLine()!!.toInt()
require(N in 4..64)
sumN += N
val A = List(N) { br.readLine()!!.split(' ').map{ it.toInt() - 1 } }
var flipped = false
fun get(i: Int, j: Int) = if(!flipped) A[i][j] else A[j][i]
fun isValid (i: Int, j: Int) = get(i, j) == i*N+j
val _Aset = A.map{ it.toList() }.flatten().toSet()
require(_Aset.min()!! == 0)
require(_Aset.max()!! == N*N-1)
require(_Aset.size == N*N)
var ans = 0
for(L in N-1 downTo 0) {
if((0 until L).any{ !isValid(it, L) || !isValid(L, it) }) {
flipped = !flipped
ans++
}
}
bw.write("${ans}\n")
}
}
fun main (args: Array<String>) {
val br = java.io.BufferedReader(java.io.InputStreamReader(System.`in`))
val bw = java.io.BufferedWriter(java.io.OutputStreamWriter(System.`out`))
val T = br.readLine()!!.toInt()
val solver = ADAMAT_SOLUTION(br, bw)
repeat(T) {
solver.run()
}
solver.check()
bw.flush()
require(br.readLine() == null)
}
