GCRD

Problem code: CF04

All submissions for this problem are available.

Greatest Common Right Divisor for two square matrices A and B is a matrix 'D' which satisfies following 3 conditions:

  1. A = P * D
  2. B = Q * D
  3. D = X * A + Y * B

where P, Q, X and Y are some matrices.
The task is to output the matrices D, X and Y for the given square matrices A and B.

Input

Input file will contain multiple input cases each denoting a combination of matrices A and B. First line of the input file consists of an integer t (around 20) denoting the no. of test cases.

Each input case will consist of:

  1. First line of the test will contain a single integer N(<=100) denoting the size of matrices A and B.
  2. Next N lines will contain the corresponding row elements of Matrix A each separated by a blankspace.
  3. Further N lines will contain the corresponding row elements of Matrix B each separated by a blankspace.

Output

For each input case, output the following:

  1. First N lines contain corresponding row elements of Matrix D each separated by a blankspace.
  2. Further N lines contain corresponding row elements of Matrix X each separated by a blankspace.
  3. Last N lines contain corresponding row elements of Matrix Y each separated by a blankspace.

Print a new line after each output.

Example

Input:
2
1 2
3 4
4 3
2 1
3
1 2 3
4 5 6
7 8 9
3 4 5
6 7 8
2 5 7

Output:
1 2 
0 -1 
1 0 
3 2 
4 5 
2 3 
1 0 
2 -2 
0 0 
1 0
 
1 2 3 
0 1 1 
0 0 -1 
1 0 0 
4 -3 3 
7 -6 6 
3 -2 2 
6 -5 5 
2 1 0 
1 0 0 
-2 0 0 
-2 0 0 
0 0 0 
0 0 1 
-2 1 1

Date: 2010-03-26
Time limit: 3s
Source limit: 50000
Languages: C C++ 4.0.0-8 C++ 4.3.2


Comments

There is an update in this

manthan @ 28 Mar 2010 06:03 PM
There is an update in this problem. Number of test cases, t <=100. N<=15. Each of the elements in the matrices A and B can only be 1 or 2. Sample Input 2 2 1 2 1 1 1 2 2 1 3 1 2 1 1 1 1 1 2 1 2 1 1 2 2 2 2 1 2 Sample Output 1 2 0 -1 1 0 -1 1 0 0 0 0 1 2 1 0 -1 0 0 0 -1 1 0 0 -1 1 0 1 -3 0 0 0 0 0 0 0 1 0 0

Sample Input 2 2 1 2 1 1 1

manthan @ 28 Mar 2010 06:11 PM
Sample Input
2
2
1 2
1 1
1 2
2 1
3
1 2 1
1 1 1
1 2 1
2 1 1
2 2 2
2 1 2

Sample Output
1 2
0 -1
1 0
-1 1
0 0
0 0

1 2 1
0 -1 0
0 0 -1
1 0 0
-1 1 0
1 -3 0
0 0 0
0 0 0
1 0 0

Current ranking is available

manthan @ 28 Mar 2010 08:08 PM

Current ranking is available at http://www.codechef.com/teams/list/MANTH10/

How answer should be

dzhulgakov_team @ 28 Mar 2010 08:52 PM

How answer should be selected? Obviously, there are infinitely many answers: if (D,X,Y) satisfy the equation than (kD,kX,kY) for real x would also satisfy. Or does it mean that we should found any answer?

Are all elements of all these

ForEver @ 28 Mar 2010 09:05 PM

Are all elements of all these matrices integers?(include P,Q,X,Y,D)

@ForEver: Yes. All the

manthan @ 28 Mar 2010 09:36 PM

@ForEver: Yes. All the elements of all the matrices P, Q, X, Y and D are integers.

@dzhulgakov: There is only one solution possible for each problem.

Note that D is the greatest

manthan @ 28 Mar 2010 09:47 PM

Note that D is the greatest common right divisor. :)

But answer seems not to be

dzhulgakov_team @ 28 Mar 2010 09:49 PM

But answer seems not to be unique! For example I generated thousand of different answers for the first test case. Here is one of them:

D =

2 1

1 1

X =

3 0

3 1

Y =

-3 1

-3 0

P =

-1 3

0 1

Q =

-1 3

1 0

There are thousand of different solutions (probably, infinitely many) where all five matrices are integer-valued.

Is it enough to print any solution?

@CodeFest: what does it mean

dzhulgakov_team @ 28 Mar 2010 09:51 PM

@CodeFest: what does it mean "Greatest" for matrices? :)

Obviously if (P,Q,D,X,Y) is a

Anton_Lunyov_MANTH10 @ 28 Mar 2010 10:18 PM

Obviously if (P,Q,D,X,Y) is a solution then (PU-1,QU-1,UD,UX,UY) is also solution for any unimodular matrix U (with det(U)=1). But there infinitle many unimodular matrix of any order n>1.

GCRD(V1, V2) is a common

manthan @ 28 Mar 2010 10:48 PM 
GCRD(V1, V2) is a common right divisor of V1 and V2 (that is, V1 = W1*GCRD(V1, V2) and V2 = W2*GCRD(V1, V2) for some W1
and W2), and any common right divisor of V1 and V2 is a right divisor of GCRD(V1, V2).

May be we need to find

Anton_Lunyov_MANTH10 @ 28 Mar 2010 11:23 PM

May be we need to find upper-triangular GCRD with elements on diagonal d[1],d[2],...,d[n] such that d[i] divides d[i+1], as I see from yout answers. But even in that case it is not always unique.

@CodeFest: Even if the

contest_crasher @ 28 Mar 2010 11:24 PM

@CodeFest: Even if the greatest common right divisor is unique, X and Y are definitely not. Note in the last input case we could have had

X =

0 0 1
-1 1 0
1 -3 0

 

instead.

I also think the answer are

ForEver @ 28 Mar 2010 11:35 PM

I also think the answer are not unique..

Yes, after reviewing the

manthan @ 28 Mar 2010 11:44 PM

Yes, after reviewing the question statement again, we conclude that there may be mutiple solutions possible. So this question is cancelled. Please do not try solving this question. Sorry for the inconvenience.

Rankign will be done on the basis of the other three questions only.

What a pity , and what a

ForEver @ 28 Mar 2010 11:49 PM

What a pity , and what a great thing!

I study Matrix during the past 3 hours and try to solve this. :)

It's 2:20 AM in my time zone , so I have to sleep ..

good...go to sleep..

ankit_agrawal @ 28 Mar 2010 11:55 PM
good...go to sleep..

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions