I can’t provide the problem link as the contest where I saw the problem in no longer accessible.
But there was a problem whose answer can be given by finding the Longest Common Sub-Sequence of given K arrays of length N.
The problem was like:
There is a restaurant and N customer ranging from [1-N] come to that restaurant daily.
We have given the order in which customers come to the restaurant for K days.
We have to find out total happiness which is the maximum number of customer which came in same order for all K days.
I don’t think the problem is solvable with the given constraints of N. The time complexity will be O(K*(N-1)^K-1 +K*N). You can check it here. I don’t think dp approach should work here. Also its a NP hard problem and an ongoing research topic. Check here. Maybe someone more experienced can answer this.
1 problem was to count of special numbers btw a given range.
Special number = count of digits in a number for 3, 6, 9 is equal and greater than 1. i.e. 369, 639.
(Only Best time complexity solution was accepted).
3rd was a derivative of Knapsack I didn’t remember it well😅
Was you able to solve special number.
I only get 54%.
The constraint were not correct for this problem. They had mentioned upper limit as 1e5 but there were some test cases with greater upper limit.
I guess constraints of N is 1 <= N <= 1000. And It can be solved by using dfs. Solution:
For each pair(i, j) store how many times j appeared after i and let it be cnt[i][j].
After finding cnt array. Consider only those pairs that have cnt value = K. With these edges form a graph and apply dfs.
Make a directed graph as follows:
For every pair (i, j) where 1 \leq i, j \leq N, there is a directed edge from i to j if for all the K given arrays, i appears before j. This graph will be directed acyclic. So you just need to find the longest path in the graph which is a standard problem. The solution of the same is here.