CODECHEF COOK38 RRMATRIX

Problem Statement

Let ‘A’ be a R x C  Matrix. Elements in ‘A’ are filled from 1 to R*C in row-major order. ‘B’ is also a R x C Matrix where the elements are filled in column-major order.

Find number of cells which satisfy the property Ai,j ==  Bi,j.

For a brief problem statement click here.

Solution

Consider an element ( i, j ). In Matrix A, the element is located at

Posold = i * C + j.

In Matrix B (Transposed Matrix of A), the same element will be located at

Posnew = j * R + i

To satisfy the property Ai,j ==  Bi,j. Posold and Posnew should be equal.

i * C + j == j * R + i

The equation can be simplified as i * (C-1) – j*(R-1) == 0

i = ( (R-1) / (C-1) ) * j

Clearly ‘i’ should be an integer. The eq. is of the form i = ( a / b ) * j. For ‘i’ to be integer, ‘j’ should be a multiple of ‘b’.

a = ( R – 1 ) / GCD( R-1,C-1)    —————————————————————–> 1

b = ( C-1 ) / GCD( R-1,C-1 ).     —————————————————————–> 2

‘j’ is the column index. Its values ranges from 0 to C-1. So, the maximum value ‘j’ can take is C-1. Therefore , the no. of  unique possible values of ‘j’ are j / b . In other words, number of multiples of ‘b’ in the range 0 to C – 1.

From 2,  j / b = ( ( C – 1 ) * GCD ( R-1, C-1 ) ) / ( C – 1 ) which is simply GCD ( R-1, C-1 ).

Therefore, No. of Elements which satisfy the property is GCD(R-1,C-1) + 1.

Note:    +1 is the first element in the Matrix.

Boundary Conditions

  • M == 1,  No. of Elements which satisfy the property is N
  • N == 1,   No. of Elements which satisfy the property is M.

Code:

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
	if(b == 0)
		return a;
	return gcd(b,a%b);
}
int main()
{
	std::ios_base::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		int m,n,g;
		cin>>m>>n;
		if( m < n )
			std::swap(m,n);
		g = gcd(m-1,n-1);
		if( m == 1 || n == 1 )
			cout<<std::max(m,n)<<endl;
		else
			cout<<g+1<<endl;
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s