GUESS - Editorial

hi all
can you please tell me for which test cases it failed . thanks in advance .
http://www.codechef.com/viewsolution/4087673

I still can’t figure where I was wrong, and I do appreciate your kind help :slight_smile:

#include <cstdio>

// GCD: function to calculate the greatest common divisor
long long GreatestCommonDivisor(long long a, long long b) {
  long long tmp;
  while (b != 0) {
    tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}

int main() {
  int testcases;
  long long n, m, gcd;
  long long odd_sum_cases;
  long long total_cases;
  scanf("%d", &testcases);
  for (int i = 0; i < testcases; ++i) {
    scanf("%lld%lld", &n, &m);
    total_cases = n * m;
    odd_sum_cases =  (n + 1) / 2 * (m / 2) + (m + 1) / 2 * (n / 2);
    gcd = GreatestCommonDivisor(total_cases, odd_sum_cases);
//  printf("%lld %lld %lld %lld %lld\n", n, m, gcd, total_cases, odd_sum_cases);
    printf("%lld/%lld\n", odd_sum_cases / gcd, total_cases / gcd);
  }
  return 0;
}

I used pen and paper, and the answer was clear within 5 minutes. but I got a tle because I was calculating the reduced fraction, but then 1/2 part clicked. The problem was awesome the combinatronics part was cool.
You can find my attempts at : Guess,abcdexter
You can find my ACeD solution at : AC solution,C++
Thanks :slight_smile:

Hi, My solution got accepted for this, formula I used is (oddN * evenM)+(oddM * evenN)/ MN. In this editorial (evenN * oddN)/MN is used and its giving wrong answer.
Eg:

N =2 and M= 3

(evenN * oddN)/M*N will give 1/6 which is wrong. it should be 1/2.

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

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

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

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);
//}

}

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

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

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

Please provide the code so that it is readable.

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

Happy Coding

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

Happy Coding

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

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

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

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

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…

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.

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.