# 2021 Ateneo De Manila Senior High School Digitab Programming Contest (Biodiverse Subsequence)

I have recently been trying to solve “2021 Ateneo De Manila Senior High School Digitab Programming Contest” problems. One can find the list of problems here. One of the problems that I have found very interesting is “Biodiverse Subsequence”. Thus, I felt that it would be fun to discuss it.

## Problem : Given N, K and an array of integers of length N, we need to count all the subsequences such that, in those subsequences all the integers between 1 to K appear at least once.

The problem is not misleading and gives the hints towards applying the concepts of combinatorics.

Since the key idea of this problem is to consider all the subsequences which have at least one appearance of all the integers from 1 to K, we can try to reach the solution using two ways. One way can be to directly count the relevant subsequences and the other way can be to count the total number of subsequences that can be formed and then removing the ones that we don’t require.

One important thing to consider here, is that since we are dealing with subsequences, there is a specific left to right ordering that we need to consider. By left to right ordering we mean that, for the elements of the subsequence A_i, A_i+1,…., A_m, we have i < i + 1 <….< m.

**Approach #1: **Let us try to use our concepts of Power Set to solve this problem. Instead of using the elements of the given array themselves, what we actually focus on is the frequencies of all the unique elements. We create the power set for each of the unique integers present in this array. For example,

For the above array, if we had to create the power sets for each element, they would look something like the following,

We know that the size of each power set is given by 2^m where m is the number of elements contributing to the power set. Among these 2^m elements comprising the power set, we have exactly one element which represents a null value (∅).

Once we have created all the power sets, it becomes easier to see that what are we interested in is picking exactly one value from each of these sets, given that the value that we pick is not equal to null (!= ∅). The problem now reduces to finding the intersection of all these sets such that any null does not contribute to this intersection.

Implementing this idea is not very difficult. We keep the frequencies of each unique element. Let us say, these frequencies are given by F1, F2, …., Fm. Then,

((2 ^ F1) — 1) * ((2 ^ F2) — 1) * …. * ((2 ^ Fm) — 1).

is our answer.

Applying the formula, we obtain, (2 * 2 * 3) = 12, as our solution to the given example.

**Approach #2: **We can solve this problem using the concept of Dynamic Programming as well. The core concept stays the same, but what we do different is that, we keep finding solutions till index ‘i’ for all 1 ≤ i ≤ N. Basically, we are concerned about finding answers for sequences for all such i, where 1 ≤ i ≤ N. Once we have found this for each element, we add all these values up and the total obtained is the final answer we are concerned about.

Both the above solutions have their time complexities ~O(N).

For more such problems and ways to approach the solutions for them, do check out the INOI past year practice problems discussions :-

For hugs and bugs, please comment down below. Till then.. Happy Coding!