ADAMAT - Editorial

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)
}

Video Editorial

5 Likes

Check out Screencast Tutorial for this problem: https://www.youtube.com/watch?v=zvOFqeShgb4&list=PLz-fHCc6WaNJa2QJq7qULBBV0YOJunq75&index=3

2 Likes

Check out this SPEED Video Tutorial for a very quick explanation

2 Likes

This long contest was really great & helpful, learnt a lot of new topics

4 Likes

Solution Link : CodeChef::ADAMATRIX

Its simple form is given here:

2 Likes

Here is my approach. Just consider the first row for elements which are at correct position(even number of operations) and not at correct position(odd number of operations).

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int t,n;
	cin>>t;
	while(t--){
	    cin>>n;
	    vector<vector<int>> a(n, vector<int>(n,0));
	    for(int i=0;i<n;i++)
	        for(int j=0;j<n;j++)
	            cin>>a[i][j];
	    int c=0;
	    for(int j=n-1;j>0;j--){
	        if(a[0][j] != j+1){
	            if(c%2 == 0)
	                c++;
	        }
	        else{
	            if(c%2!=0)
	                c++;
	        }
	    }
	    cout<<c<<endl;
	}
}
5 Likes

Why my code is wrong

#include <bits/stdc++.h>
#include <string>
#include <sstream> 
#include <iostream> 
#define rep(i,a,n) for(int i=int (a);i<int (n);i++)
#define OUT  freopen("output.txt", "w", stdout)
#define IN  freopen("input.txt", "r", stdin)
#define mem(a,b) memset((a),(b),sizeof(a))
#define NumofDigits(n) ((int)log10(n)+1)
#define NumofBits(n) ((int)log2(n)+1)
#define PI 3.14159265358979323846264
#define vii vector<pair<int,int>>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi  vector<int>
#define vc  vector<char>
#define vl  vector<long>
#define nl  cout<<"\n"
#define pb  push_back
#define mp  make_pair
#define ll  long long
#define ss  second 
#define ff  first
#define endl "\n"
#define sp  " "
using namespace std;

int main(){
    ll t;
    cin>>t;
    while(t--){
    	ll n;
    	cin>>n;
    	vector<vector<int>> a(n, vector<int>(n));
    	for(int i = 0; i < n; i++){
    		a[i].resize(n);
    		for(int j = 0; j < n; j++){
    			cin>>a[i][j];
    		}
    	}
    	int h = 0;
    	int j = 0;
    	int k = n;
    	for(int i = 0; i < n; i++){
    		for(int j = 0; j < n; j++){
    			if(a[i][j] == i*k+j+1){
    				continue;
    			}
    			else{
    				h++;
    			}
    		}
    	}
    	if(h%n == 0 && h != 0){
    		h = 1;
    	}
    	else{
    		h = h%n;
    	}
    	cout<<h<<endl;
    }
}

Same.

1 Like

The order of transpositions is immaterial, so I simply worked back from the largest possible. We are told that a series of transpositions will work, so for each sub-matrix I transpose if one arbitrarily chosen element in the last row or right column, other than on the leading diagonal, is not the expected value. I do not consider odds and evens.

I have used the exact same logic, but my implementation is bit different (If the element is at correct position I have given 0 at that value in binrow array. After that I have checked the number of flips). Could you please help me out what is wrong here. Thanks!

       `int n = scanner.nextInt();
        int[] row = new int[n];
        int[] binrow = new int[n];
        for (int i = 0; i < n; i++) {
            row[i] = scanner.nextInt();
            if (row[i] == i + 1)
                binrow[i] = 1;
            else
                binrow[i] = 0;
        }
        int steps = 0, flip = 1;
        for (int i = n-1; i > 0; i--) {
            if (binrow[i] != flip) {
                steps++;
                flip = 1 - flip;
            }
        }
        System.out.println(steps);`

According to your code, even if some element is in correct position the step will increase only once.
e.g: Suppose first row has a1 a2 a3 a4 a5.
a5 is not at correct position but a4 is at correct position. Your code will increase step only once for a4 also.

You have to check the value of step for each element and change it accordingly. Keep in mind that elements at correct position will need even moves and others will need odd moves.

1 Like