×

# GUESS - Editorial

Author: Lalit Kundu
Editorialist: Praveen Dhinwa

Simple

# 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:

This question is marked "community wiki".

2.5k53136170
accept rate: 20%

3.0k93164187

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.

(21 Jun '14, 09:48)

 7 If we further process the answer then there can be 4 cases for m & n m & n are odd m is even, n is odd m is odd, n is even 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);  answered 20 Jun '14, 08:23 3★bug2312 316●2●6 accept rate: 12% and this is O(1) (07 Jul '14, 15:17) willnt case 1 and case 4 interchange ..?? (02 Oct '14, 11:20)
 0 Can anyone tell me why do i get a wrong answer with this code. http://www.codechef.com/viewsolution/4054521 answered 16 Jun '14, 16:35 1 accept rate: 0% Check my code If you dont understand anything feel free to ask http://www.codechef.com/viewsolution/3976338 Happy Coding (16 Jun '14, 16:58) bipin23★ 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 (16 Jun '14, 23:49) Yeah..it was just because of not using long long int. Thanks :) (17 Jun '14, 10:23)
 0 Why did I get a WA with this code.. Plz reply http://www.codechef.com/viewsolution/4104227 answered 16 Jun '14, 21:03 8●2 accept rate: 0% 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 (16 Jun '14, 23:52) 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. (17 Jun '14, 16:29)
 0 hi all can you please tell me for which test cases it failed . thanks in advance . http://www.codechef.com/viewsolution/4087673 answered 17 Jun '14, 01:22 2★anisdube 16●1 accept rate: 0% you haven't use return 0 cause your return type is int. put return 0 and try. (21 Jun '14, 10:42)
 0 I still can't figure where I was wrong, and I do appreciate your kind help :) #include // 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; }  answered 17 Jun '14, 05:26 2★qzthrone 1 accept rate: 0% same solution when i am executing it is showing AC check this link http://www.codechef.com/viewsolution/4109240 (17 Jun '14, 15:50) sanzzzay2★
 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 ^_^ answered 17 Jun '14, 14:37 309●2●12 accept rate: 3%
 0 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. answered 17 Jun '14, 18:45 2★Sabari 2●1 accept rate: 0%
 0 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 answered 19 Jun '14, 00:10 1 accept rate: 0%
 0 Can anybody explain this: O(log(N * M)), complexity for the computation of gcd . answered 21 Jun '14, 11:06 2★mappy 1 accept rate: 0%
 0 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
 0 http://www.codechef.com/viewsolution/4313343 I keep getting WA with this :( Any idea what mistake i am making?? answered 13 Jul '14, 02:42 1 accept rate: 0%
 0 I am getting WA...whats wrong with my code...pls reply me.... http://www.codechef.com/viewsolution/4513060 answered 08 Aug '14, 12:36 2★amar555 1 accept rate: 0%

# 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;


}

0
accept rate: 0%

Happy Coding

(16 Jun '14, 17:00) 3★

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 Jun '14, 15:56) 2★
 -1 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;} answered 16 Jun '14, 15:53 8●2 accept rate: 0% Please provide the code so that it is readable. (16 Jun '14, 16:55) bipin23★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,677
×1,173
×946
×888
×47
×8

question asked: 16 Jun '14, 15:01

question was seen: 4,307 times

last updated: 02 Oct '14, 11:20