PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Aniket Marlapalle
DIFFICULTY:
medium
PREREQUISITES:
longest-increasing-sub-sequences subsets
PROBLEM:
Given an array of elements and corresponding colors of these numbers. Process Q queries as follows :
In each query given K consider all the non-decreasing sub-sequences of length equal to K and find the minimum colorfulness among such sequences. Colorfulness of a sequence is total distinct colors in that sequence.
EXPLANATION:
First of all lets think how many distinct colorfulness values are there. It will be one of he subsets of the colors. So lets do some preprocessing by iterating over all the subsets of these colors and consider only those numbers that have color from this set.
One more observation is that if we can make a sequence of colorfulness C of length L then we can make any sequence of length <=L with a colorfulness of <=C. So for every subset of colors find the longest increasing sub-sequence (here) and update the answer for all the lengths less than or equal to L.
Time Complexity : O(2^CNlog(N)) where C is the distinct colors and N is the length of the array.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here