FO7's blog

Preparing for square point capital OA , found some problem
By FO7, history, 2 years ago, In English

https://leetcode.com/discuss/interview-question/5846629/SquarePoint-OA-Desk-Quant/

Any ideas how to solve this problem ? some of my observations: (i) all k's are independent to each other (ii) looking for corners ?? Thanks in advance

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
23 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it 
/* 
as k's are independent we can treat them each differently
we say that dp[i][j][l] = min moves to solve till (i, j) for a particular 1 <= l <= k

now the transitions are straight forward
we take min at each step
if(shelf[i][j] != k)
        dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k])
        else dp[i][j][k] = dp[i-1][j-1][k];

*/
for(int i=0;i<=n;i++) for(int j=0;j<=k;j++)dp[i][0][j] = 0; 
    for(int i=0;i<=m;i++) for(int j=0;j<=k;j++)dp[0][i][j] = 0; 
    ll ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int l=1;l<=k;l++){
                if(shelf[i][j] != l){
                    dp[i][j][l] = min(dp[i][j][l], max(dp[i-1][j][l], dp[i][j-1][l]));
                }
                else 
                    dp[i][j][l] = min(dp[i][j][l], dp[i-1][j-1][l] + 1);
            }
        }
    }
    for(int i=1;i<=k;i++) ans += dp[n][m][i];
    cout << ans << '\n';

This solved the given two testcases, You have any different ideas pls share

→ Reply
  • »
    »
    12 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    for grid
    2 1
    1 2
    the answer should be 4 but your code is giving 3

    → Reply