RRMATRIX - Editorial

Problem Link:

Practice

Contest

Author: Roman Rubanenko
Tester/Editorialist: Utkarsh Lath

Difficulty:

Simple

Pre-requisites:

High school maths

Problem:

Given two matrices A and B, both of them having N rows and M columns. The cells of A are numbered in row major order, and cells of B are numbered in column major order. How many cells appears at the same location in both the orderings ?

Explanation:

For 0 ≤ i < N, 0 ≤ j < M, the (i,j)th entries are:

Ai, j = i * M + j + 1
Bi, j = j * N + i + 1

equating the two, we get

i * M + j + 1 = j * N + i + 1
⇒ i * (M-1) = j * (N-1)
⇒ i / j = (N-1) / (M-1) = p / q
⇒ i = l * p, j = l * q for 0 ≤ l ≤ min((N-1) / p, (M-1)/q)

where p/q is reduced form of (N-1)/(M-1).

However, if g = gcd(N-1, M-1),

(p, q) = ((N-1)/g, (M-1)/g)

Therefore, (N-1) / p = (M-1) / q = g
and the cells which get same numbering are (l * p, l * q) for 0 ≤ l ≤ g, which are g+1 in number.

Boundary cases

N = 1 or M = 1, in which case the answer is max(N, M).

Solutions:

Setter’s solution
Tester’s Solution

9 Likes

if n=1 and m=1 then answer will be 1,
but this totorial say(boundary case) that ans =2 how ?

3 Likes

actually there is no need of boundary conditions.
in case when (n==1||m==1) then gcd(0,n(or)m) will be 0 and the answer will itself become 1 and correct.

Why does this C# code produce a wrong answer?

enter code here
    static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());
        int cnt2;

        for (int t = 0; t < T; t++) 
        {
            string[] s = Console.ReadLine().Split();
            int n = int.Parse(s[0]);
            int m = int.Parse(s[1]);
                            
            if (n == 1 || m == 1)
                cnt2 = Math.Max(n, m);
            else
                cnt2 = GCD(n-1, m-1) + 1;
            Console.WriteLine(cnt2);
        }
    }

    static int GCD(int a, int b)
    {
        if (b == 0) return a;
        return GCD(b, a % b);
    }
1 Like

long long gcd(long long a,long long b)
{while(a>0&&b>0)
if a>b a%=b;
else b%=a;
return a+b;
}
so if either m=1 or n=1 then g=gcd(m-1,n-1) becomes zero and g+1 will give 1 which is correct answer!! :slight_smile:

Strangely (to me), the GCD needed to have variables a and b defined as long (instead of int) to work:

    static long GCD(long a, long b)
    {
        if (b == 0) return a;
        return GCD(b, a % b);
    }

Thus, I defined cnt2 as a long also.
It does not seem to me that a, b, a%b, or GCD(a,b) would ever be greater than an int value.

2 Likes

Just a note: in editorial are used 0-based indexes, while in problem statement there wer 1-based indexes used…

1 Like

What if I start calculating from 1- based index. e.g. A(i,j) = (i-1) * M + j and B(i, j) = (j-1) * N + i then by equating these two, I get i(M-1)-M= j(N-1)-N ; How to proceed further?

Please somebody solve it using 1- based indices.

I am not able to understand the last part, that how come answer for no of matches become g + 1. I got the same equation given in editorial, but at the end how come this happens --> i = lp and j = lq and from this how do we draw conclusion that g + 1 is no of matches in both the matrices.
Please Help!

Just a note: in editorial are used 0-based indexes, while in problem statement there wer 1-based indexes used…

bradavice

for n=1 or m=1 shouldnt the answer be just max(n,m) ?

1 Like

for n=1,m=1 obviously answer is 1 only.
You can do it like: if(n==1 && m==1) ans=1 else ans=gcd(n-1,m-1)+1

I hope you’ll not mind that I’ve edited the post, but there was an obvious mistake in the boundary case.

1 Like

you do not need to check if(n==1 && m==1) because you have gcd(0,0) will return 0

Strangely (to me), the GCD needed to have variables a and b defined as long (instead of int) to work:

static long GCD(long a, long b)
{
    if (b == 0) return a;
    return GCD(b, a % b);
}

Thus, I defined cnt2 as a long also. It does not seem to me that a, b, a%b, or GCD(a,b) would ever be greater than an int value.

when “if (n == 1 || m == 1)” comes out true then output should be 1.

Manal, I think you mean “if (n==1 && m==1)” then output should be 1. Otherwise, if n==1 or m==1 then the answer would be the other number (e.g. n=1, m=5, then output 5).

thanks @alex_2oo8 :slight_smile:

may be the problem was elsewhere, because everyones solution used 32 bit numbers only

1 Like