GRIDTOUR - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Abdullah Aslam

Tester: Michael Nematollahi

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy.

PREREQUISITES:

Observations and Modular Multliplicative Inverse.

PROBLEM:

Given a grid with N rows numbered from 0 to N-1 and M columns numbered from 0 to M-1 and another integer K, you start from cell (0,0). Determine the minimum number of moves in which you can visit all cells if you can move in the following manner, or determine it is impossible to reach each cell at all.

From cell (r, c), you can move to either of the following three cells.

  • (r, (c+K) \% M)
  • ((r+K)\%N, c)
  • ((r+K)\%N, (c+K)\%M)

EXPLANATION

For the first subtask, it is easy to see that if K = 1, we can always visit any cell by above operation, and if K = 2, we need both N and M to be odd, otherwise we cannot visit odd numbered rows/columns. If we can visit, the minimum number of operations is always N*M.

Coming to final subtask now.

Firstly, assume there’s a single row. Now, the problem becomes to reach all cells (0, y) starting from (0,0) where, in a single step, you can move from (0, c) to (0, (c+K)\%M) (or moving K steps to the right).

Lemma: If we can reach from (0, c) to (0, (c+1)\%M) just by operation of moving K steps to the right, we can reach all cells in the same row.

Proof: If By starting in column c, moving K steps to the right, say y times, we reach column (c+1)\%M, we can again apply operation y times to reach (c+2)\%M and so on. We can continue this until we have visited all cells.

Let us determine the number of steps to move from (0, c) to (0, (c+1)\%M).

Starting from column c and moving y*K steps to the right implies final position (c+y*K) \bmod M which should be (c+1) \bmod M for some y for reaching position (0, (c+1)\%M).
This implies (c+y*K)%M = (c+1)\%M which implies y*K = 1 \bmod M. Multiplying both sides by K^{-1}, we have y = K^{-1} \bmod M.

Now, the criteria for a valid y is that K^{-1}\bmod M exists which requires gcd(M, K) = 1. We can see this is also sufficient condition for existance of y.

Coming to the original problem, we can see that we can apply the operations for each dimension independently. For checking whether a valid tour exists, we can treat the original problem as following two sub-problems.

  • Only one column and N rows for given K
  • Only one row and M columns for a given K.

A valid tour exists in original problem if and only if valid tour exists in both sub-problems, which implies condition both gcd(N, K) and gcd(M, K) should be 1.

Now, coming to the minimum number of cells visited, it can always be seen that we never need to visit a cell twice, leading to exactly N*M cells in the tour.

Example
Consider following grid with N = 2, M = 5 and K = 3. Since gcd(2,5) = 1 and gcd(3, 5) = 1, valid tour exists.

0 1 2 3 4
5 6 7 8 9

One valid tour is 0->3->1->4->2->5->8->6->9->7

The idea for a valid path is to keep moving right, till the next cell is already visited, and in next move, move K steps down too, along with K steps to the right.

TIME COMPLEXITY

Time complexity is O(log(X)) per test case due to GCD operation where X = max(N, M, K).

SOLUTIONS:

Setter's Solution
 #include <bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define N 300101
#define SZ 3001
#define LB lower_bound
#define M 1000000007
#define UB upper_bound
#define MP make_pair
#define LD long double
#define F first
#define S second
 
int main()
{
	LL k,i,j,lt,tc,d,r,q,y,z,v,x,m,n;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>lt;
	while(lt--)
	{
	    cin>>n>>m>>k;
	    assert(n>=1&&n<=1e9);
	    assert(m>=1&&m<=1e9);
	    assert(k>=1&&k<=1e9);
	    if(__gcd(m,k)==1&&__gcd(n,k)==1)
	    {
	        x++;
	        cout<<n*m<<endl;
	    }
	    else
	    {
	        y++;
	        cout<<-1<<endl;
	    }
	}
} 
Tester's Solution
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		int n, m, k; cin >> n >> m >> k;
		if (__gcd(n, k) > 1 || __gcd(m, k) > 1)
			cout << "-1\n";
		else
			cout << 1ll*n*m << "\n";
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class GRIDTOUR{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long n = nl(), m = nl(), k = nl();
	    if(gcd(m,k)==1 && gcd(n, k)==1)pn(n*m);
	    else pn(-1);
	}
	long gcd(long a, long b){
	    return b==0?a:gcd(b, a%b);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new GRIDTOUR().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to Share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

4 Likes

Let A and B be 2 numbers which are coprime.
I observed that A%B,2A%B,3A%B,…,B*A%B are numbers 0 to B-1 occurring exactly once. (Not in order btw).
My new learning this contest to solve the problem.

1 Like

@taran_1407

From what i understand is that

(c+y*K) \bmod M should be equal to c \bmod M for some y.

This implies (c+y*K) c mod M .

How you get y * K = 1 mod M ?

i didnt understand this part

Starting from column c and moving y∗K steps to the right implies final position (c+y∗K)modM which should be cmodM for some y.
This implies (c+y∗K) which implies y∗K=1modM. Multiplying both sides by K−1, we have y=K−1modM.

I think the idea is to find y such that (c+y*k)%M = (c+1)%M. Since the modulo operation is distributive in modulo, we can write the previous equation as :
( (c % M) + (y*k % M) )% M = ((c % M) + (1 % M)) % M . From the latter we can see it is enough than(y*k % M) = 1%M
Correct me if I am wrong , please !

1 Like

That was a typo, corrected now. Thanks for pointing out.

1 Like

It should be
“Starting from column c and moving y∗K steps to the right implies final position (c+y∗K)modM which should be (c+1) modM for some y.”

Corrected now.

1 Like

Have a look on congruence modulo . It means A ≡B (mod C) iff A%C = B%C . Now relate .

I have O(1) solution.
Edit:- I don’t have O(1) solution :stuck_out_tongue:

I have an O(N*M) solution. @anon55659401 :stuck_out_tongue:

1 Like

Can we discuss about the legendary O(1/N * M) solution ? I am more interested in it.
Please enlighten me :stuck_out_tongue:

2 Likes

Only @vijju123 can pull out such a solution. :crazy_face:

1 Like

i got a good solution…for pythoners
https://www.codechef.com/viewsolution/24386790

3 Likes

didn’t know it was possible to prove…also nice editorial…
btw the editorials of MAY LONG are still not out :stuck_out_tongue_closed_eyes:

bro did u understand that part of multiplying with k inverse and how that implies gcd(k,m)=1? help please

1 Like

Is there a way to deduce that NxM is the minimum number of operations without trying out all possibilities of tracing a path in exactly NxM operations?

yes there is, a very easy way

How can we be sure that

we never need to visit a cell twice??

Any other problem based on same concept

Because y*K \bmod M for values of y from 1 to M each generates a distinct number from range 0 to M-1. Read about modular arithmetic.

2 Likes