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

1 Like

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.

3 Likes

It helped a lot. Thank you.

Alternate Solution - Here

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.

1 Like

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!!!