ETUP - Editorial

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:

Even +Even+Even = Even \\ Odd+Odd+Even = Even

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:

fst = {E \choose 3}

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:

snd = {O \choose 2} \times {E \choose 1}

Thus the total number of tuples with even sum in the array window [L, R] would become:

total = fst +snd

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

7 Likes

Can someone please explain why my this submission is giving wrong answer??

https://www.codechef.com/viewsolution/48975571

You should have taken long long while calculating the number of evens and odds in a range as (even * (even - 1) * (even - 2)) and (odd * (odd - 1) / 2) * even can exceed integer limit.

2 Likes

Can anyone explain why this was wrong Solution: 48970190 | CodeChef !!

@soumyadeep_21
I understood evenC3 and oddC2*even

but how (even * (even - 1) * (even - 2)) and (odd * (odd - 1) / 2) * this come i really didn’t understood that

Even C 3 =even * (even-1)(even-2)/ (12*3)

Weak Testcases

@soumyadeep_21 can we expect an O(N\times Q) solution to execute within the given time limit?

https://www.codechef.com/viewsolution/48970497

The above solution is pretty naive (if I am not wrong). It has executed within the given time limit during the contest.
The exact same solution is giving TLE now.

Can we accept this mistake in a rated contest (of course it is rated only for Division 3 and the solution I picked also belongs to Division 3)?

@admin, this isn’t an issue related to the execution environment, right?

but how it come ?

I hope you know the formula of nCr → which is n! / (n - r)! (r!)
Right??
so this formula can also be written as

n x (n - 1) x … x (n - r + 1) x (n - r)! / ( r! x (n -r)!)
=>n x … x (n - r+ 1) / r!

using this concept 5c3 => (5 x 4 x 3 )/ 3!
Just play around with different examples and you will get the hang of it!! :smiley:

Thus
EvenC3 => (Even * (Even - 1) * (Even - 2) ) / (3 x 2)
I hope you got your answer @ranjeethinge
Please clarify me if I am wrong @soumyadeep_21

1 Like

Can you give a reference link or a math reference for further reading? I’m not able to understand how you were able to re-write the Combination formula as such.

[Solution: 48991007 | CodeChef]
can somebody please tell me why it is giving WA??

Sorry !! I am not able to find any such articles.You should definitely check for some youtube videos maybe you will find something over there.

@strange_boy_0 understood bro thanks a lot

Timely reminder for people getting WA - check this first:

Edit:

You can test it with this simple testcase.

3 Likes

Could someone find error ? I am getting Runtime error on submission
My solution

Due to overflows, you’re getting a division by zero error on the testcase I linked above.

@cherry0697 - people are confused as to how to compute {O \choose 2} \times {E \choose 1} without overflow - can you extend the Editorial a little to address it?

You are correct

1 Like

Thanx for replying!! :smiley:

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

Looks like this again.

Edit2:

Actually, the error occurs even before there, and is due to stack overflow due to the huge local array you’re declaring.

1 Like

In your code, line number 24 to 29 & 38 to 44 are causing errors. Remove those lines, and also at line 60 and 61 you are directly applying the formula, rather you should check if in one query, even numbers are >= 3, then line 60 wil make sense, otherwise it will contribute 0 and in the same way, if odd numbers are >= 2 then line 61 will make sense, otherwise it will contribute 0 and update ans variable to 0 in each query, then your code may get AC.
Thanks. :slight_smile: