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, In English

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)

 
 
 
 
  • Vote: I like it
  • -26
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dp with bitmasking

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How bro?? what is the mask?? Can you elaborate your approach??

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

You can submit here: DevSkill #107.