GCD and LCM - A mystical error in codechef problem

general
, , , , ,
1

Okay, this one’s interesting …

Here is a problem from school aka beginner section of codechef. Problem is simple. Find gcd and lcm . That’s it. Here is the problem.

I submitted 2 solutions . Solution 1 got accepted while Solution 2 gets rejected. What’s the difference ? Only of int and long long . Int one gets accepted (solution 1) while long long one got rejected . (solution 2)

SOLUTION 1 : LINK

#include<stdio.h>


int gcd(int a , int b)
{
		if(a==0)
			return b;
		
		return gcd(b%a , a);
	
}


int main()
{
		
		int t;
		scanf("%d",&t);
		
		while(t--)
		{
			int a,b,k;
			
			scanf("%d%d",&a,&b);
			
			k=gcd(a,b);
			
			printf("%d %d\n",k,(a*b)/k);
			
		}
		
		return 0;
}

SOLUTION 2 : LINK

#include<stdio.h>


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


int main()
{
		
		long long t;
		scanf("%lld",&t);
		
		while(t--)
		{
			long long a,b,k;
			
			scanf("%lld%lld",&a,&b);
			
			k=gcd(a,b);
			
			printf("%lld %lld\n",k,(a*b)/k);
			
		}
		
		return 0;
}

So, who has a explanation now ? :smiley:

2 Likes
2

the answer should be wrong for soln 1 as it doesnt meet A,B constraints.so i think it is a problem with codechefs solution

1 Like
3

As jpkumar7 said it’s error from author’s side. Author didn’t consider that LCM of A and B cannot go beyond int range however it is possible since A and B are less than 10^6 so LCM can be go at max 10^12 which is beyond int range. For example, A = 999999 and B = 999997 then LCM will be 999996000003 which will not fit in int. But author made the test cases using int so whenever there will be overflow(like in above case) user will get WA. This issue should be resolved as soon as possible because when a beginner will try to solve this problem and he/she gets WA even when his/her code is completely correct then that person would feel a bit demotivated that he/she could not such an easy problem.

2 Likes
4

But why does storing data in long long int data type give WA ?

5

Consider this example, A = 10^6 and B = 999999, LCM of A and B is close to 10^12 which is beyond the int range.

I used long data type and it gave me WA. When I used int, it gave me AC.
The test cases for this problem should be corrected immediately as it gives confusion especially for beginners. It’s been more than a year, anybody going to fix the test cases?

6

Instead of changing the test cases, what admin can do is that write below the problem statement as a note that use long long instead of int for cpp users. In the INOI and ZCO problems, it is done like this.

7

I got almost 25 WAs because of this. Yes, It won’t be just demotivating but also it might take the faith of beginner from codechef i.e. in other questions when he will be getting WA due to mistake from his side like some minor mistakes in code, edge cases mishandled … etc. He will end up believing that the mistake is from codechef not his.