Блог пользователя algoskipper

Dp+Bfs issue in Microsoft OA question
Автор algoskipper, история, 5 месяцев назад, По-английски

Question from algozenith mocks Microsoft coding test 2 — question 1 This question is asked un Microsoft online assessment which is present in various sites but none of them have provided correct solutions. One can think of bfs but it will give TLE as many steps are repeated a lot of time. So talking about dp optimization. 2D dp where dp[i][j] will give total number of ships when start with value j and total layers are i including current layer. Base case would be for every i dp[i][0]=i and for every j dp[1][j]=1. dp[i][j]= (summation dp[i-1][j] for every j from 0 to (j*j+1)%m-1 ) But its constantly giving wrong answer. And to make it worse nowhere correct answer is given nor failed test case is shown. i think i have something wrong in my idea can anyone clarify. below is my code.

ll l,m;cin>>l>>m;
    vector<vector<ll>>dp(l+2,vector<ll>(m+2,0));
    f(m){dp[1][i]=1;}

    vector<ll>lp(m+1);lp[0]=1;
    for(ll i=1;i<l;i++){lp[i]=lp[i-1]+1;}
for(ll i=0;i<l;i++){dp[i][0]=i;}
    for(ll j=2;j<=l;j++){

for(ll i=0;i<m;i++){
    if(i==0)continue;
    if((i*i+1)%m!=0)dp[j][i]=lp[((i*i+1)%m)-1];
    dp[j][i]++;

}
for(ll i=0;i<lp.size();i++){if(i==0)lp[i]=dp[j][i];else lp[i]=lp[i-1]+dp[j][i];}

    }
    cout<<dp[l][2]%m<<endl;

question link Question link

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

here is my accepted solution with dp[i][j] = number of nodes in subtree of i upto level j , base is for for all i dp[i][1]=1 , also use prefix sum to get dp states sum otherwise it will tle

code
→ Ответить
»
3 недели назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int l,m;
    cin>>l>>m;
    vector<vector<int>>dp(l+1,vector<int>(m+1,0));
    vector<vector<int>>pref(l+1,vector<int>(m+1,0));
    dp[l][0]=1;
    pref[l][0]=1;
    for(int i=1;i<=m;i++)
    {
        dp[l][i]=1;
        pref[l][i]=(dp[l][i]+pref[l][i-1])%m;
    }
    for(int i=l-1;i>=1;i--)
    {
        for(int j=0;j<m;j++)
        {
            int val=(j*j+1)%m-1;
            if(val>=0)
            {
                dp[i][j]=(1+pref[i+1][val])%m;
            }
            else
            {
                dp[i][j]=1;
            }
            if(j==0)
            {
                pref[i][j]=dp[i][j];
            }
            else
            {
                pref[i][j]=(pref[i][j-1]%m+dp[i][j]%m)%m;
            }
        }
    }
    cout<<dp[1][2];
    return  0;
}
→ Ответить