GUESS - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Simple

PREREQUISITES:

ad hoc, simple combinatorics.

PROBLEM:

You are selecting two numbers x and y such that 1 <= x <= N and 1 <= y <= M. How many (x, y) pairs satisfy the condition that x + y is odd.

QUICK EXPLANATION

  • Use the fact that Number of even numbers from 1 to N are floor(N / 2) and number of odd numbers from 1 to N are ceiling(N / 2).

  • Answer will be (floor(N / 2) * ceiling(N / 2)) / (N * M).

  • For representing the fraction in lowest terms, divide both the numerator and denominator by gcd of both.

EXPLANATION

Notice the following simple facts.

  • Sum of an even and an odd number is odd.
    ie
    Even + Odd = Odd.
    Odd + Even = Odd.

  • Number of even numbers from 1 to N are floor(N / 2).
    Number of odd numbers from 1 to N are ceiling(N / 2).

Fact number 1 is very easy to prove.

Let us prove fact 2, first part.
Claim Number of even numbers from 1 to N are floor(N / 2).
Proof:
We will prove this fact by using induction over N.

Base Case:
For N = 1, floor(1 / 2) = 0. Hence LHS = 0
As number of even numbers are 0 too from 1 to 1. Hence RHS = 0
So LHS = RHS

Induction Hypothesis:
Let us assume that formula is true up to N such that N is even, then we need to prove the formula for N + 1.
Notice that N + 1 will be odd. Hence number of even numbers won’t increase and will remain equal to floor(N / 2).
As we know if N is even, then floor(N / 2) = floor((N + 1)/ 2). Hence we are done for this case.

Now Let us assume that formula is true up to N such that N is odd, then we need to prove the formula for N + 1.
Notice that N + 1 will be even. Hence number of even numbers increase by 1, hence they will be equal to floor(N / 2) + 1.
As we know if N is odd, then floor(N / 2) + 1 = floor((N + 1)/ 2). Hence we are done for this case too.

Note that instead of proving it formally, you can just see the above observation by observing the pattern for small numbers.

Proof of second part of fact 2 (Number of odd numbers from 1 to N are ceiling(N / 2).) will also go exactly along the same lines.

So finally our answer will be (floor(N / 2) * ceiling(N / 2)) / (N * M). We need to print this fraction in its irreducible form, so we have to divide both
the numerator and denominator by their gcd.

  • Computing floor(N / 2) can be done by using simply integer division N / 2.
  • Computing ceiling(N / 2) can be done by using simply integer divide (N + 1) / 2.

Complexity
O(log(N * M)), in the computation of gcd.

Things to Take Care

  • Beware of the overflow of the product N * M, So use long long for storing product N * M.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

2 Likes
2

#include<stdio.h>

int gcd(int,int);

int main()
{
int t,m,n,i,j,k,temp,num,flag=2,x;
scanf("%d",&t);
for(k=0;k<t;k++)
{ temp=0;
scanf("%d%d",&n,&m);
num=n*m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if((i+j)%2!=0)
{
temp++;
}
}
}
x=gcd(num,temp);
temp=temp/x;num=num/x;
printf("%d/%d\n",temp,num);
}
system(“pause”);
return 0;
}

int gcd(int x,int y)
{
int r;

while(y%x!=0)
{
	r=y%x;
	y=x;
	x=r;
	if(y%x==0)
		break;
	else
		continue;
}
return x;

}

3

Why did I get a WA with this code… Plz reply (ignore the #incl… ) using namespace std;typedef unsigned long long ull;ull den;ull num;inline ull hcf(ull x,ull y){if(y==0)return x; else return hcf(y,x%y);}int main(){unsigned int tCases;long long int n,m;scanf("%d",&tCases); while(tCases–){scanf("%lld lld",&n,&m);if(n%2==0)printf(“1/2\n”);else{if(m%2==0)printf(“1/2\n”);else{den=nm;n/=2;m/=2;num=(2n*m) + m -n;if(num==0) printf(“0/1\n”);else{ull h=hcf(den,num);num/=h;den/=h;printf("%lld/%lld\n",num,den);}}}}return 0;}

4

Can anyone tell me why do i get a wrong answer with this code.

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

5

Please provide the code so that it is readable.

6

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

Happy Coding

7

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

Happy Coding

8

Why did I get a WA with this code… Plz reply

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

9

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

10

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

11

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

12

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;
}
13

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

14

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:

15

same solution when i am executing it is showing AC check this link http://www.codechef.com/viewsolution/4109240

16

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…

17

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.

18

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.

19

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

20

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);
6 Likes