 # EVENPSUM - Editorial

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

CAKEWALK

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

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

pls check what is the issue here

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

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 Hey guyld 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 