CHFGCD - Editorial

editorial
, , , ,
35

Hi , can you please tell if i perform if( b > a) swap ( b, a) in your code its giving WA , why thats so , why can’t we perform swap operation in this problem if we consider a always greater then b

36

What code are you referring to?

I have made 3 submissions out of which 2 are similar. Paste a link to my submission so that I can investigate that part.

37

This one

38

you are checking for both a+1 and b+1 , but in gernality if we consider a always > b and perform swap when necessary then we only have to check for gcd ( a+1 , b ) >1
If i am wrong please correct me .

39

There is no rule that states you can increment only one among the two.

Some counterexample(s):

1
10 9

In the above example, the answer should be 1 since you can increment 9 to make it 10 and gcd would be greater than 1.

But according to your logic,

This turns out to be true for given example and.,

This turns out to be false. I don’t know what you are doing post this, but incrementing only one among them will not work always (even if you swap to maintain order a \ge b ).

40

for this condition when one is odd and other is even the ans will always be 1 , i was asking bewteen two numbers a and b , where both are odd and where gcd ( a, b ) ==1 , i thing incrementing only bigger out of the two and then checking the gcd will always work , can you provide any test case where both are odd , gcd ==1 and incrementing smaller one by one gives gcd >1

41

Here you go,

1
5 21

Both are odd, the gcd is 1 and incrementing the smaller one gives gcd > 1.

1 Like
42

Thanks man , appreciated

43

hey guys,
I have used the approach given below…

#include
using namespace std;

int main()
{
int t; cin >> t;
while(t–)
{
int x, y;
cin >> x >> y;
int min_op = 0;
if(x % 2 != 0)min_op++;
if(y % 2 != 0)min_op++;
cout << min_op << endl;
}
return 0;
}

As per my analysis, this should work properly. But it shows a wrong answer. Will anyone please help me understanding what’s happening??

44

Can anyone tell me in which test case the code is failing.

Link: CodeChef: Practical coding for everyone

45 
1
1 1
1 Like
46

Some test cases to consider:

Input

3
1 3
1 5
9 6

Expected Output

2
2
0

Your Output

1
1
1
2 Likes
48

It fails for the test input:

1
3 3

(and likely others).

49

Thanks. In this case GDC is already > 1.

50

you need to check gcd(x,y) first for 0 operation case, not just both even only

51

There exist case that both a,b are odd but you only need 1 operation. e.g. 15,19

52

1 ops on 17 and 1 ops on 29 resulting in 18 and 30 which have 2 as gcd

53

I was trying pretty little the same approach but was not able to get AC. Can anyone tell me why this code is wrong?

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve()
{
ll x,y;
cin>>x>>y;
ll ans=0;
if((x%2==0) and (y%2==0))
cout<<0<<"\n";
else if(((x%2==0) and (y%2==1)) or ((x%2==1) and (y%2==0)))
cout<<1<<"\n";
else
cout<<2<<"\n";
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;cin>>t;
while(t–)
{
solve();
}
return 0;
}

54
2 Likes
55

Yeah yeah sorry…my bad thanks btw

1 Like