EVEN - Editorial

problem link:

EVEN

Author:dhussa_09

Tester:dhussa_09

Translator:dhussa_09

Editorialist:dhussa_09

DIFFICULTY:
SIMPLE

** PREREQUISITES:**
LOGIC, PATTERN

PROBLEM:

chef’s friend is a chemist. He has n atoms.

He tells chef to note down the weight of all n atoms . All the weights are EVEN and DISTINCT.

chef has to find the number of all the subsequences of atoms whose sum of weights is completely divisible by two.

He also, has to find number of pairs of atoms whose sum of weights is completely divisible by two.

NOTE: use (long long int).

Definition of Subsequence:

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

For example, the sequence {A,B,D}. A,B,D is a subsequence of {A,B,C,D,E,F}.obtained after removal of elements C, E, F.

QUICK EXPLANATION:

You are given all even distinct numbers and you store that in the array.

1st part.

  1. find the subsequences of atoms whose sum of weights is completely divisible by two.

Each of the number is completely divisible by 2 and its addition with any other number is also completley divisible by 2.so, we have to find all possible such subsequences.
for eg: consider n=3, and element are x,y,z.
subsequbnces will be-
x
y
z
xy
yz
xz
xyz
so,total they are 7.
The formula for this type of pattern and considering all sequences of element in array is 2^n.
But here we dont consider any empty set except that we consider evey sequence.
so,are formula becomes,
(2^n)-1.
similarly, if n=4 our ans will be,(2^4)-1=15.

2.find number of pairs of atoms whose sum of weights is completely divisible by two.

its same as above part but here we have to find only pair of such sequence.means elements should be only 2.
so, in above example.n=3,elements in array-[x,y,z].
such pairs are,
xy
yz
xz
ans=3.
for n=2. elements=[x,y].
such pairs are,
xy(only).
ans=1.
similarly,for n=4.when you will trace manually you get ans=6.
so, we get there are n*(n-1)/2 pairs always.
so,ans=n*(n-1)/2 (general formula).

The solution in c++14 language:

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int n,base=2;
long long int ans1=1,ans2;
cin>>n;
int A[n];
for(int j=0;j<n;j++)
{
cin>>A[j];
}
ans2=n*(n-1)/2;
while (n != 0) {
ans1 *= base;
–n;
}

    cout<<ans1-1<<endl<<ans2<<endl; 
}
return 0;

}