This problem was asked by Goldman Sachs yesterday for hiring interns at IIT Kharagpur:
Given a N x 3 grid with numbers written in the cells. You have K, 2 x 1 tiles which you can put to cover some cells. The numbers written on those two cells is added to your score which was initially zero. Find the maximum possible score you can achieve.The tiles can be placed horizontally or vertically.
Constraints:
1<=N<=1000
1<=K<=1000
Example:
N = 2
K = 2
0 4 1
1 0 4
Ans = (4 + 1) + (0 + 4)
Dp with bitmasking
You should solve this problem first. Now for your problem, we just add the variables $$$k$$$ in the 3 subproblems given in the link, that is maximum sum we can obtain using atmost $$$k$$$ tiles which can be solved using dynamic programming in $$$O(NK)$$$.
Why would it be O(NK), shouldn’t we keep track of K best dominos for every tiling permutation (and there is a lot of them)? Doesn’t seem obvious that we can group them by by sum or by min of k tilings.
The complexity of this will be O(NM*8) which is essentially O(NM). The '8' comes from the total number of masks (2^3). Then for each mask, we need to check which all masks are compatible with it. Further, there may be some cases in which we place the tile horizontally in the current row. In that case, we need not check for compatibility with the previous mask. So you will have to handle tonnes of different cases. This is exactly what I tried to do in the contest but failed to complete it within the time limit.
Does anyone have any better solution?