Problem Formulation: Let’s think of each conveyor belt as a sequence of numbers Sv, Sc. We have to take p number of numbers from the first sequence and q number of numbers from the second sequence such that p+q = k where p>=1 and q>=1. And from all possible combinations of p and q the sum of taken numbers should be maximized. We have to merge these two prefixes (first p numbers from Sv, and first q numbers from Sc ) of that two sequences such that the resulting sequence is lexicographically smallest.
First, we will iterate through all possible values of p and q and find the maximum sum. Based on this maximum sum, we will store those p and q values for which we found the maximum sum.
Using two pointers for sequence Sv, Sc we will keep merging by taking a smaller element from the sequences. For checking, we may face any of these 3 conditions:
Sv[i] < Sc[j], we take Sv[i]
Sv[i] > Sc[j], we take Sc[j]
Sv[i] == Sc[j], we keep checking forward until we get any inequality, say we found Sv[x] < Sc[y] we chose Sv[i] otherwise we chose Sc[j]. But this operation takes O(n) time which will not fit in the time limit.
So we need to precalculate all (i,j) pairs where the inequality is found. Let's say DP[i][j] keeps L such that S[i,i+1,. . . . .i+l-1] ==S[j,j+1,...j+l-1].
State update will be done like this.
DP[i][j] = if(S_b[i] == S_c[j]) (DP[i + 1][j + 1] + 1) else 0;
We can calculate it in (m*n).
Now for each possible value of (p,q) we will generate the smallest lexicographical sequence taking p from Sv and q from Sc. Among these sequences we will take the smallest one.
