You are not logged in. Please login at www.codechef.com to post your questions!

×

GUESS - Editorial

2
2

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

This question is marked "community wiki".

asked 16 Jun '14, 15:01

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53136170
accept rate: 20%

edited 16 Jun '14, 15:22

darkshadows's gravatar image

5★darkshadows ♦
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) imrajeshpal2★

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);
link

answered 20 Jun '14, 08:23

bug2312's gravatar image

3★bug2312
31626
accept rate: 12%

edited 20 Jun '14, 08:24

and this is O(1)

(07 Jul '14, 15:17) nktjhawar2★

willnt case 1 and case 4 interchange ..??

(02 Oct '14, 11:20) aniket_09562★

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

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

link

answered 16 Jun '14, 16:35

shubhi1910's gravatar image

1★shubhi1910
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) harindersingh3★

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

(17 Jun '14, 10:23) shubhi19101★

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

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

link

answered 16 Jun '14, 21:03

jaigurudev's gravatar image

3★jaigurudev
82
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) harindersingh3★

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) romitheguru2★

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

link

answered 17 Jun '14, 01:22

anisdube's gravatar image

2★anisdube
161
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) raja44ever3★

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

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

answered 17 Jun '14, 05:26

qzthrone's gravatar image

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★

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 ^_^

link

answered 17 Jun '14, 14:37

abcdexter24's gravatar image

2★abcdexter24
309212
accept rate: 3%

edited 17 Jun '14, 14:44

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.

link

answered 17 Jun '14, 18:45

Sabari's gravatar image

2★Sabari
21
accept rate: 0%

edited 17 Jun '14, 19:17

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

link

answered 19 Jun '14, 00:10

jugalthakkar's gravatar image

3★jugalthakkar
1
accept rate: 0%

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

link

answered 21 Jun '14, 11:06

mappy's gravatar image

2★mappy
1
accept rate: 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<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);
//}

}

link

answered 10 Jul '14, 03:20

ttqwerty's gravatar image

2★ttqwerty
1
accept rate: 0%

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

link

answered 13 Jul '14, 02:42

TerryMcginnis's gravatar image

2★TerryMcginnis
1
accept rate: 0%

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

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

link

answered 08 Aug '14, 12:36

amar555's gravatar image

2★amar555
1
accept rate: 0%

-1

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;

}

link

answered 16 Jun '14, 15:31

liladharpaliw's gravatar image

2★liladharpaliw
0
accept rate: 0%

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

Happy Coding

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

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) sanzzzay2★
-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;}

link

answered 16 Jun '14, 15:53

jaigurudev's gravatar image

3★jaigurudev
82
accept rate: 0%

Please provide the code so that it is readable.

(16 Jun '14, 16:55) bipin23★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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