LCS of K given sequences!

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.

1 <= K <= 10
1 <= N <= 10000
1 <= Arr[i] <= N

Constraints of N?

I updated the problem.

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.

There should be some other technique to solve otherwise this problem should not be in the contest.

See this problem, very similar to what you mentioned. Just the constraints are less-Problem

1 Like

Thanks :relaxed:

Hackwithinfy, 9th may, I tried to solve this problem only 18% score I got :((

@viveksing9780 What were your other 2 problems?

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.

1 Like

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.

Could you elaborate on how to build the graph exactly, some sample code would be useful. I’m not sure I got the idea just right. Thanks.