PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Soumyadeep Pal
Tester & Editorialist: Aman Dwivedi
DIFFICULTY:
Simple
PREREQUISITES:
Maths, Combinatorics
PROBLEM:
You are given an array A consisting of N integers and Q queries. Each query is described by two integers L and R. For each query, output the number of tuples (i, j, k) such that L\le i\lt j\lt k\le R and A_i+A_j+A_k is an even number.
EXPLANATION:
Since we are looking for even tuples, let us see when will the combination of three numbers result in an even sum. We can easily see that the conditions to get an even sum are:
Let’s say E and O are the count of even and odd numbers respectively within the queried range of positions, [L, R] in the given array.
Calculating E and O in a queried window of A
Running a loop from positions L to R for every query would result in a complexity of O(N \times Q) for calculation of even and odd numbers in the queried window of the array.
Instead, we precompute the number of even numbers from position 1 to x for every x \in [1, N] and store them in an array (say B), i.e. B_x= number of even numbers in A_{[1, x]}. This makes it clear that the number of even numbers, E in A_{[L, R]} will be given by B_R when L=1 and by B_R-B_{L-1} otherwise. Similarly the number of odd numbers, O in A_{[L, R]} will be given by (R-L+1)-E.
As in the first type of tuples, we need to choose 3 even numbers from the total even numbers present in the queried window of the given array, the total number of tuples of the first type are:
Now in the second type of tuples, we need to choose 2 odd numbers from the total odd numbers along with 1 even number among all even numbers present in [L, R]. Hence the total number of tuples of the second type will be:
Thus the total number of tuples with even sum in the array window [L, R] would become:
That is our final answer for every query, we can simply output it.
TIME COMPLEXITY:
O(N+Q) per test case
SOLUTIONS:
Setter
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
vector<vector<int>> a(n + 1, vector<int>(2));
for (int i = 1; i <= n; i++) {
int x; cin >> x;
a[i][0] = a[i - 1][0] + (x % 2 == 0);
a[i][1] = a[i - 1][1] + (x % 2 == 1);
}
while (q--) {
int l, r;
cin >> l >> r;
int even = a[r][0] - a[l - 1][0];
int odd = a[r][1] - a[l - 1][1];
int ans = (even * (even - 1) * (even - 2)) / 6 + (odd * (odd - 1) / 2) * even;
cout << ans << '\n';
}
}
return 0;
}
Tester
#include<bits/stdc++.h>
using namespace std;
#define int long long
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || ( cnt == 19 && fi > 1) ));
} else if (g == endd) {
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
int sum_n,sum_q;
void solve()
{
int n,q;
n=readIntSp(1,100000);
q=readIntLn(1,100000);
sum_n+=n;
sum_q+=q;
int a[n];
for(int i=0;i<n;i++)
{
if(i!=n-1)
a[i]=readIntSp(0,1000000);
else
a[i]=readIntLn(0,1000000);
if(a[i]%2!=0)
{
if(i==0)
a[i]=1;
else
a[i]=1+a[i-1];
}
else
{
if(i==0)
a[i]=0;
else
a[i]=a[i-1];
}
}
while(q--)
{
int l,r;
l=readIntSp(1,n);
r=readIntLn(1,n);
assert(l<=r);
l--;
r--;
int len=r-l+1;
int odd=a[r];
if(l!=0)
odd-=a[l-1];
int even=len-odd;
int ans=0;
if(even>=3)
{
int tup_even = even*(even-1)*(even-2);
tup_even/=6;
ans+=tup_even;
}
if(odd>=2)
{
int pair_odd=odd*(odd-1);
pair_odd/=2;
int tup_odd=pair_odd*even;
ans+=tup_odd;
}
cout<<ans<<"\n";
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("tc1.txt","r",stdin);
// freopen("output.txt","w",stdout);
sum_n=0;
sum_q=0;
int t;
t=readIntLn(1,1000);
while(t--)
solve();
assert(sum_n<=1000000 && sum_q<=100000);
assert(getchar() == EOF);
return 0;
}
