Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### banyanTree123456789's blog

By banyanTree123456789, history, 2 months ago,

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)

• -26

 » 2 months ago, # |   0 Dp with bitmasking
•  » » 7 weeks ago, # ^ |   0 How bro?? what is the mask?? Can you elaborate your approach??
 » 2 months ago, # |   +3 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)$.
•  » » 2 months ago, # ^ |   0 Thank you for the link to the problem. Let's see if I can arrive to the solution from this point onwards.
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 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.
•  » » 7 weeks ago, # ^ |   0 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?
•  » » » 7 weeks ago, # ^ |   0 How many TCs did you pass with the above approach?
•  » » » » 7 weeks ago, # ^ |   0 Bro can you keep the code here??
 » 7 weeks ago, # |   0 You can submit here: DevSkill #107.