Help Katekar - HackerEarth

So today I was solving some 2D DP problems on HackerEarth and came across this problem: https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/practice-problems/algorithm/largest-subsequence-c554fb8c/description/ .

I must say that the problem description was very vague and it took time for me to understand the requirements. Adding to it, the editorial provided no explanation.  So, thought to write an unofficial editorial to it.

Ok, so the problem requirements go as follow: From the elements of an array A, you need to construct an array B such that for any two elements a and b in B, if a > b , frequency of a in B > frequency of b in B. 

Solution:

I prefer starting with code first, as code never hides anything, so here you go:

Clearly, while constructing B, we must ensure that if present element is greater than any of the already added elements, it has a frequency larger than all of them. When reading the elements, we store them with their frequencies in a map and also store them in a set. Remember than CPP set is not a multiset, so it will only store the unique values. Also, the values will be stored in a sorted fashion, as sets are implemented as BSTs. (We could have actually completely eliminated using a set as map also stores the keys in a sorted order) . We keep track of the maximum frequency of any element for reasons that shall be clear by the end of post.

Now we construct a 2D DP Table where DP[i][j] represent the maximum length of a sequence with elements till index i (in sorted fashion) such that the maximum frequency of any element is <= j.

Our recurrence relation can be derived easily now. For each state (i, j) , we have two choices:

1. If current j is less than or equal to the frequency of the current([i]) element, we can add j number of current elements to (i - 1, j - 1) as then we are sure that elements till i - 1 are all smaller than i and also j - 1 ensures that maximum frequency of any of them is less than j;
2. Else we have two choices. We choose max amongst either (i - 1, j), which is the length such that we have elements till i with maximum frequency amongst any being j. Or, we choose (i, j - 1), which is choosing till current element, but with maximum frequency being <= j - 1 (Remember that j is greater than frequency of current element, so we can't choose any more of it.) .

Finally we return the max in the last row, which stores the maximum length such that we have checked all elements with max frequency amongst any of them being the index of corresponding column.

I hope I was able to clear it a bit. Thanks :)

This article was updated on April 14, 2019