CHFGCD - Editorial

editorial
, , , ,
24

Maybe stop running sieve()?

1 Like
25

17 29 becomes 18 and 30 after 2 operations then gcd(18,30)>1ā€¦ We can change both values but in different operation.

26

Didntā€™t worked for meā€¦still giving me TLEā€¦pls help

27

For god sake, watch your code - the indentation sucks. Provide a cleaner code. It becomes easy to find out where it went wrong.

29

https://www.codechef.com/viewsolution/49222720
Why my solution giving WA ? Giving correct answers when testing for all combinations of even and odd numbers.

30

You didnā€™t test all combinations.

Try this test case:

Input

1
3 9

Expected Output

0

Your Output

2
31

It should be mentioned in the question that we can change both the numbers.

32

It is clearly written.

2 Likes
33

Noob Coder

#include

#include

using namespace std;

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int t;

cin >> t;

while(tā€“){

   int a,b;

   cin >> a >> b;

   int op=0;

   // in case if any nummber is 1

   if (a==1){

       a++;

       op++;

   }

   if (b == 1){

       b++;

       op++;

   }

   //making a smaller for one way hcf

   if(a>b){

       swap(a,b);

   }

   if (__gcd(a,b) > 1) // if already in gcd move on

       op = op;

   else if(a%2==1&&b%2==1){    // if both odd

       if(__gcd(a,b+1)>1)     // 7,27 case

       op++;

       else{                  // if both odd and not in above case

   op+=2;

   a++;

   b++;

    }

   }

   else if (a % 2 == 1 || b % 2 == 1)     // if any one is odd

   op++;

       cout << op <<endl;

}

return 0;

}

What is wrong in it

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