NUMFUN - EDITORIAL

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Shivam Wadhwa
Tester: Shivam Manchanda
Editorialist: Shivam Machanda

DIFFICULTY:

EASY

PREREQUISITES:

DP , 2D-DP

QUICK EXPLANATION:

For every pair of N and M there are atmost 3 ways to proceed. Decrease N, or decrease M or N/=GCD(M,N) and M/=GCD(M,N).

EXPLANATION:

Make a 2-D array DP, where DP[i][j] represents minimum ways to make i and j both 1. You can now make a recursive definition:

DP[1][1]=0;
for(i from 1 to N)
{
	for(j from 1 to M)
	{
		if(i==1 && j==1)
			continue;
		if(gcd(i,j) != 1)
			minimum from (DP[i/gcd][j/gcd]+1 , DP[i-1][j]+1 , DP[i][j-1]+1 );
		else
			minimum from ( DP[i-1][j]+1 , DP[i][j-1]+1 );
	}
}

Time complexity

O(N*M)

AUTHOR’S AND TESTER’S SOLUTIONS:

Solution can be found here.