GUESS - Editorial

editorial
, , , , ,
10

I got the answer right & accepted, but I wish to optimize this solution

if (N & 1 && M & 1){	
  product = (unsigned long long int)N*M;
  printf("%llu/%llu\n", (product - 1) >> 1, product);
}else{	
  printf("1/2\n");
}

The best time I get is 0.11

11

If we further process the answer then there can be 4 cases for m & n

  1. m & n are odd
  2. m is even, n is odd
  3. m is odd, n is even
  4. m & n are even

For the case 1,2 & 3 the answer is always 1/2.

Whereas for the case 4, the ans is (mn)/2 / mn

The code can be as

 if(((m+n)&1)|| (!(m&1) && !(n&1)))
   printf("1/2\n");
else
   printf("%llu/%llu\n",(m*n)/2,m*n);
7 Likes
12

Can anybody explain this: O(log(N * M)), complexity for the computation of gcd .

13

Could someone please tell me why my solution is wrong. Uncommenting the currently commented out section and deleting the code between the //----------------- result in a accepted solution, but funny thing is that the code between the
//------------- dashes are equivalent to the currently commented out section.

Here is my solution, sincerely thankful if someone would be kind enough to point out my mistake:

#include "stdio.h"

unsigned long long gcd(unsigned long long a, unsigned long long b){
unsigned long long r;
while(b){
	r=a%b;
	a=b;
	b=r;
}
return a;

}

int main(){
unsigned long long t, n, m;
scanf("%llu", &t);

for(unsigned long long e=0;e<t;e++){
	scanf("%llu", &n);
	scanf("%llu", &m);
	//-----------------
	if((n%2)&&(m%2)){
		unsigned long long d=gcd((n*m)-1,2*n*m);
		printf("%llu", ((n*m)-1)/d);
		printf("/%llu\n", (2*n*m)/d);
	} else {
		printf("%llu",1);
		printf("/%llu\n",2);
	}
	//-----------------
//unsigned long long nodd=(n/2)+(n%2);
//unsigned long long neven=(n/2);
//unsigned long long modd=(m/2)+(m%2);
//unsigned long long meven=(m/2);
//unsigned long long num=(nodd*meven)+(modd*neven);
//unsigned long long den=n*m;
//unsigned long long d=gcd(num, den);
//printf("%llu", num/d);
//printf("/%llu\n", den/d);
//}

}

14

http://www.codechef.com/viewsolution/4313343
I keep getting WA with this :frowning: Any idea what mistake i am making??

15

I am getting WA…whats wrong with my code…pls reply me…

http://www.codechef.com/viewsolution/4513060

16

Please provide the code so that it is readable.

17

Check my code
If you dont understand anything feel free to ask
http://www.codechef.com/viewsolution/3976338

Happy Coding

18

Please provide the code so that at-least we can read it.
Or please send the link…

Happy Coding

19

Maybe because you not using long long int for M and N you’re not getting correct answer.
Your Code: http://ideone.com/JWuav5.
My Code: http://ideone.com/x7AEbg.
Test case used
t=1
m = n = 999999999

20

Hint : your code doesn’t pass this test case (t=1 m=n=999999999). Correct answer for this is 499999999000000000/999999998000000001.
Your Code gives 499999998000000002/999999998000000001

21

Yeah…it was just because of not using long long int. Thanks :slight_smile:

22

same solution when i am executing it is showing AC check this link CodeChef: Practical coding for everyone

23

you have used too many loops i think you will get TLE …try to use pen and paper … just a little thinking and boom you will get the answer or try to follow editorial note…

24

i think there is little problem in logic
try to replace “num=(2nm) + m -n;” with “num=(2nm) + m + n;” in your code and then try again.

25

how could You say answer will be (floor(N / 2) * ceiling(N / 2)) / (N * M) ???
for n=10 and m=10 answer is 1/4 while correct answer is 1/2.

26

you haven’t use return 0 cause your return type is int.
put return 0 and try.

27

and this is O(1)

28

willnt case 1 and case 4 interchange …??

29

Very Nice Explanation, Thank you.