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

4 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

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

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

6

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

7

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

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:

9

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.

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