EVENPSUM - Editorial

PROBLEM LINK:

Practice
Div1
Div2

Setter: Ildar Gainullin
Tester: Alexander Morozov
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

We are given two positive integers A and B . We need to find the number of pairs of positive integers (X,Y) that can be formed such that 1 \le X \le A and 1 \le Y \le B and the sum X+Y is even.

QUICK EXPLANATION:

  • When is the sum of two numbers even? The answer is when either both of the numbers are even or both of them are odd.

  • Thus, count the number of even-even pairs and odd-odd pairs and add them to get the answer.

  • Be careful of integer overflow!!! This can happen in some languages such as C++. In that case make sure you use the right datatype to store the variables while finding the answer.

EXPLANATION:

Let’s recall the definitions of even and odd numbers. A number n is even if n=2 \cdot k for some positive integer k . A number n is odd if n=2 \cdot k+1 for some positive integer k . We have 4 cases for X and Y:

Case 1: X is even and Y is odd

  • Let X=2 \cdot k1 and Y=2 \cdot k2+1 .

  • Then X+Y=2 \cdot k1+2 \cdot k2+1= 2 \cdot k+1 where k=k1+k2 .

  • Therefore, X+ Y is an odd number.

Case 2: X is odd and Y is even

  • Let X=2 \cdot k1+1 and Y=2 \cdot k2 .

  • Then X+Y=2 \cdot k1+1+2 \cdot k2=2 \cdot k+1 where k=k1+k2 .

  • Therefore, X+ Y is an odd number.

Case 3: X is even and Y is even

  • Let X=2 \cdot k1 and Y=2 \cdot k2 .

  • Then X+Y=2 \cdot k1+2 \cdot k2=2 \cdot k where k=k1+k2 .

  • Therefore, X+ Y is an even number.

Case 4: X is odd and Y is odd

  • Let X=2 \cdot k1+1 and Y=2 \cdot k2+1 .

  • Then X+Y=2 \cdot k1+1+2 \cdot k2+1=2 \cdot k where k=k1+k2+1 .

  • Therefore, X+ Y is an even number.

Thus, we have X+Y even in case 3 and case 4 . (here all the divisions are integer divisions) .

  • Total even numbers in [1,A] are A/2 .

  • Total odd numbers in [1,A] are (A+1)/2 .

  • Total even numbers in [1,B] are B/2 .

  • Total odd numbers in [1,B] are (B+1)/2 .

Therefore, the number of pairs (X,Y) where X+Y is odd are
(A/2) \cdot (B/2) + ((A+1)/2) \cdot ((B+1)/2) .

TIME COMPLEXITY:

O(1) for each testcase.

SOLUTION:

Editorialist's solution
    #include <bits/stdc++.h>
    using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int a, b;
		cin >> a >> b;
		long even_a = a / 2;
		long even_b = b / 2;
		long odd_a = (a + 1) / 2;
		long odd_b = (b + 1) / 2;
		long ans = even_a * even_b + odd_a * odd_b;
		cout << ans << endl;
	}
	return 0;
}
Setter's solution
#include <cmath>

#include <functional>

#include <fstream>

#include <iostream>

#include <vector>

#include <algorithm>

#include <string>

#include <set>

#include <map>

#include <list>

#include <time.h>

#include <math.h>

#include <random>

#include <deque>

#include <queue>

#include <cassert>

#include <unordered_map>

#include <unordered_set>

#include <iomanip>

#include <bitset>

#include <sstream>

#include <chrono>

#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq

mt19937 rnd(228);

#else

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

#endif

int main()

{

#ifdef iq

freopen("a.in", "r", stdin);

#endif

ios::sync_with_stdio(0);

cin.tie(0);

int t;

cin >> t;

while (t--)

{

int a, b;

cin >> a >> b;

int even_a = a / 2, even_b = b / 2;

int odd_a = (a + 1) / 2, odd_b = (b + 1) / 2;

ll ans = even_a * (ll)even_b + odd_a * (ll)odd_b;

cout << ans << " \n";

}

}

VIDEO EDITORIAL (English):

VIDEO EDITORIAL (Hindi):

Please comment below if you have any questions, alternate solutions, or suggestions.

1 Like

Why is this code showing WA for subtask 3 - https://www.codechef.com/viewsolution/40305092

2 Likes

Hi, on line number 39, multiplying two integers will first result in integer which could lead to integer overflow. I have modified that line of your code by typecasting the product to long long. Here is your modified code . Hope it helps.

4 Likes

It helped a lot. Thank you.

Alternate Solution - Here

1 Like

Here is an even simpler approach.

Suppose the number of rows B is even. Then in every pair of rows there are A even numbers, alternating between the first and second row. So the total of evens is (AB / 2).

If A is even, swap A and B in the previous argument to get the same answer.

For both odd, we can easily see there is an extra even number in the last row. For example look at 5 by 3 to see the pattern, where the solution is 8.

So the solution is simply the result of integer division (AB + 1) / 2 in all cases.

2 Likes

Here is my simple implementation hope it helps
#include
using namespace std;

int main() {
long long int t,x,y;
cin>>t;
while(t–){
cin>>x>>y;
if(x%2!=0 && y%2!=0){
cout<<(x-1)/2*(y-1)/2+(x-((x-1)/2))(y-((y-1)/2))<<endl;
}
if(x%2==0 && y%2==0){
cout<<(x/2)
(y/2)+(x-x/2)(y-y/2)<<endl;
}
if(x%2==0 && y%2!=0){
cout<<(x/2)
((y-1)/2)+(x-x/2)(y-((y-1))/2)<<endl;
}
if(x%2!=0 && y%2==0){
cout<<(y/2)
((x-1)/2)+(y-y/2)*(x-((x-1))/2)<<endl;
}
}
return 0;
}

try:
    t=int(input())
    for _ in range(t):
        A,B=map(int,input().split(" "))
        print(int(((A*B)+1)/2))

except:
    pass

Why is this failing in third test case?

Simple? You can replace the whole ‘while’ loop with all the 'if’s by the following, as I describe above

while (t–) {
    cin >> x >> y;
    cout << (x * y + 1) / 2 << endl;
}

A * B may be too long to fit into a 32-bit integer. As the editorial says above Be careful of integer overflow!!!

import java.util.Scanner;

class Main{
public static void main(String []argh)
{
Scanner obj = new Scanner(System.in);
int T = obj.nextInt();
while (T–>0){
int a = obj.nextInt();
int b = obj.nextInt();
long sum = 0;
if(a%2!=0 && b%2!=0){
int div_a = a/2;
int div_b = b/2;
sum = div_adiv_b;
if(b>a)
sum +=((a-div_a)
(div_b+1));
else
sum +=((b-div_b)*(div_a+1));
}else{
sum = (a%2==0)?(a /=2)*b:(b /=2)*b;
}
System.out.println(sum);
}
}
}

can any give me one test case for this code that give me wrong result . Becouse i am trying some test case they give me correct result but code don’t get Submitted.

https://www.codechef.com/viewsolution/44489313
all the thing are running on my offline compiler but not passing while I submit to codechef please help.

its because
a* b may be too long to fit into a 32-bit integer. As the editorial says above Be careful of integer overflow!!!
so to fix this change the data type of a ,b int to long …

try
a = 235323
b = 6754346
and its answer is 794726481879

A sample test case for everyone whose last test case shows the wrong answer, but other test cases are correct.
a = 235323
b = 6754346
and its answer is 794726481879.

pls check what is the issue here

https://www.codechef.com/submit/EVENPSUM

Hey, please provide the link to your submission in order for us to check.
The link you have provided here is of the general submit page.
Thanks!

Hi can anyone explain why this method wouldn’t work?
#include

int main(){

int t;

std::cin >> t;

while(t--){
    unsigned long long a, b, count = 0;

    std::cin >> a >> b;

    for(unsigned long long i = 0; i < a; i++){
        for(unsigned long long j = 0; j < b; j++){
            if((j + i) % 2 == 0){
                count++;
            }
            else{
                continue;
            }
        }
    }
    std::cout << count << std::endl;
}
return 0;

}

I’m assuming its something to do with using a for loop with such large numbers?
thanks :slight_smile:

Hey guyld :smiling_face:
this code is fine only when (a , b <= 1000) but as the constraints are (a,b <= 10^9) this will give time limit exceeded.

If you have any doubts feel free to ask :slight_smile: