Digital Matrix

For the 3rd day in a row, I'm solving a problem from recent Dhaka regionals. This time it is problem F - Digital Matrix. It is a very tricky ad hoc problem. No team could solve it during the real time contest. Fudan University came closest to solving it with their solution giving wrong output on only one type of cases. It took them 13 submissions though to come that close.

The problem states that

You are given two N x N square matrices, A and B. Each of the elements of these matrices is an integer between 1 and K (inclusive). You have to convert matrix A into matrix B in minimum number of operations. In each operation you can choose one element of matrix A and change it to any integer between 1 and K (inclusive). You have to ensure that after any operation the matrix is not converted to a symmetric matrix.

Now, when converting matrix A to B, if there were no 'symmetric matrix' constraint, we would have required exactly X operations, where X is the number of differences between the two matrices.

With the constraint applied, we might require X, X+1 or X+2 operations depending on the elements of the matrices. Lets consider two 2 x 2 matrices where non-diagonal symmetric elements are transposed -
A = 12          B = 11
      11                 21

In this case, it will require 3 operations to get B from A (if K is greater than 2) -
12    ->    13     ->     13     ->      11
11           11             21              21

If K is 2, we cannot convert the first matrix to the second.

Now consider another case with N=3 and K=2
A = 112          B = 111
      111                 111
      111                 211

In this case, we'll require 4 operations -
112    ->    122    ->    121    ->    121    ->    111
111           111           111           111           111
111           111           111           211           211

If K was more than 2, we could have done the conversion in 3 steps.

So, the sequence of logical decisions needed to solve this problem are -

1. If the matrices are equal, the result is 0.
2. If the second matrix is symmetrical, the result is -1 (impossible case as we have to convert the matrix to symmetrical after applying an operation)
3. If we get two symmetrical elements that are equal on both matrices, but not equal to each other, we can keep it there until all other conversions are done and then apply this one; so we will require exactly X operations.
4. If we get a mismatch in a position on the 2 matrices, if their symmetrical element and it doesn't make a 'symmetrical transpose' like in first example, we can finish in X steps by keeping this pair unsolved until the end.
5. If their are more than one pairs of 'symmetrical transpose', we can finish in X steps as well, because when solving one pair, the other pair will prevent the matrix from being symmetric.
6. If none of the above conditions are met, we will require X+2 or X+1 operations depending on whether K is 2 or more. One special case is that for N=2, we cannot achieve any solutions.

Source code -

/*
Problem Name : Digital Matrix
Problem Number : Archive 4858
Link   : http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010
Problemsetter : Arifuzzaman Arif
Problem Type : Ad hoc
Difficulty  : 6 / 10
Interest  : 7 / 10
Complexity  : O(N^2)
Date   : November 12, 2010
*/

#include <stdio.h>
#include <math.h>

#define rep(i,n) for(i=0;i<(n);i++)
#define max(a,b) (((a)>(b))?(a):(b))
#define MAXN 100

int N,K;
int A[MAXN+2][MAXN+2], B[MAXN+2][MAXN+2];

bool is_equal() {
 int i,j;
 rep(i,N) rep(j,N) if(A[i][j] != B[i][j]) return false;
 return true;
}

bool is_B_symmetric() {
 int i,j;
 rep(i,N) for(j=i+1;j<N;j++) if(B[i][j] != B[j][i]) return false;
 return true;
}

int main() {
 int T, kase = 1;
 int i,j;
 int diff,res,ct;
 bool flag;

 scanf(" %d",&T);
 while(T--) {
  scanf(" %d %d",&N,&K);
  rep(i,N) rep(j,N) scanf(" %d",&A[i][j]);
  rep(i,N) rep(j,N) scanf(" %d",&B[i][j]);

  printf("Case %d: ",kase++);
  if(is_equal()) { printf("0\n"); continue; }
  if(is_B_symmetric()){ printf("-1\n"); continue; }

  diff = 0;
  flag = false;
  ct = 0;
  rep(i,N) rep(j,N) {
   if(i == j) {
    if(A[i][j] != B[i][j]) diff++;
   }
   else if(A[i][j] == B[i][j]) {
    if(A[j][i] == B[j][i]) {
     if(A[i][j] != A[j][i]) {flag = true;}
    }
   }
   else {
    if(A[i][j] == B[j][i] && A[j][i] == B[i][j]) ct++;
    else { flag = true; }
    diff++;
   }
  }
  if(ct > 2) flag = true;

  if(flag) { printf("%d\n",diff); continue; }
  if(K == 2) {
   if(N == 2) res = -1;
   else res = diff + 2;
  }
  else res = diff + 1;
  printf("%d\n",res);
 }
 return 0;
}