RRMATRIX - Editorial

editorial
, , , ,
1

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

6 Likes
2

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

3 Likes
3

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

4

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

5

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.

6

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

1 Like
7

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

8

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
9

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:

10

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
11

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.

12

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

13

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

14

thanks @alex_2oo8 :slight_smile:

15

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

1 Like
16

going by strict definition of divisors, gcd(0, i)should be undefined. However, people conveniently extend it to mean that gcd(i, 0) = i.

17

@utkarsh_lath [Not something relating to this problem] I remember a problem from some previous contest, where 0^0 was conveniently taken as 1. That didn’t go by strict definitions.

18

Its all about conventions and widely accepted norms. Whether 0^0 is 0 or 1 is usually clear from the context.
Sometimes people give special mention to such things, sometimes assume that others are aware of it.

1 Like
19

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

1 Like
20

0 based indexes makes reasoning much easier to convey / come up with.

1 Like