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

Ankesh Krishna Prasad
Jan 23 · 4 min read
Photo by Nicolas HIPPERT

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,

Given an array of integers

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

The Power Sets created on the basis of frequencies and indices of distinct elements.

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).

Gateway To Thoughts

Knowlege Expands, When Shared!

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store