Epic Coloring (Editoryal)

Solution 1

Notice there are only two cases of parity of sum of the array , let's consider when $\sum a$ is odd , let's consider all possible choices for pair sum :

• $\text{odd+odd=even}$ and thus complementary is $\text{odd-even=odd}$.

• $\text{even+even=even}$ and thus complementary is $\text{odd-even=odd}$.

• $\text{even+odd=odd}$ and thus complementary is $\text{odd-odd=even}$

Notice in all configurations none of them matches the parity , thus the answer is $0$ when (\sum a \bmod 2=1).

Now let's consider when $suma$ is even , we've all possible configurations :

• $\text{odd+odd=even}$ and thus complementary is $\text{even-even=even}$.

• $\text{even+even=even}$ and thus complementary is $\text{even-even=even}$.

• $\text{even+odd=odd}$ and thus complementary is $\text{even-odd=even}$

Notice that all configurations match, thus we consider all pairings which is

Complexity $O(n)$.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    int n;cin>>n;
    vector<int>a(n);
    ll sum=0;
    for(auto &i:a){
        cin>>i;
        sum+=i;
    }
    if(sum&1){
        cout<<"0\n";
    }else{
        cout<<(ll)(n*(n-1))/2<<"\n";
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        solve(); 
    }
    return 0;
}

Solution 2

We can sequentially pair every parity with it's corresponding one and accumulate the count each time , each time we'll pair even with odds and we accumulate the count simply. Only this works when $\sum a$ is even , otherwise it's 0.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    int n;cin>>n;
    vector<int>a(n);
    int o=0;int e=0;
    ll sum=0;
    ll ans=0;
    for(auto i:a){
        cin>>i;
        sum+=i;
    }
    if(sum&1){
        cout<<"0\n";
        return;
    }else{
        for(auto i:a){
            ans+=e+o;
            if(i&1){
                e++;
            }else{
                o++;
            }
        }
    }
    cout<<ans<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--){
        solve(); 
    }
    return 0;
}

Complexity $O(n)$.