adarsh851997's blog

Plese help me On Dp Question
By adarsh851997, history, 6 years ago, In English

here is one of the dp question in which i got stucked ;please someone help me . i know there are many geneious people here for whom this problem will be a cakewalk.

PROBLEM:: A rat gives birth to 2 rat on day 1 and on day 2 it gives birth to 3 rat and on third day it dies. how many rats will be present at Nth day .intially there are K rats are present; k and n are upto 1e4;

MY SOLUTION here is what i did i tried to calcualte number od rats present on day i,let it be dp[i].

so,dp[i]=number of rats on (i-1) day+number of rats on (i-2) day + (birth on (i-1) day)*2 + (birth on (i-2) day)*3 -death on i-3 th day; is iam right? or something is wrong the problem was asked in interview of airtel and the interviewer was not satisfied.

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

Comments Comments (9)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Your DP has a problem: it doesn't take into consideration the rats' age. I mean, when you calculate dp[i], how do you precisely know how many rats from the previous days give birth to 2 babies and how many to 3? The correct solution is the following: let dp[i][j] be the number of rats who are alive on the i-th day and are j days old (j is either 1 or 2). The final answer will be dp[n][1] + dp[n][2]. The recurrence relation is:

dp[1][1] = K
dp[1][2] = 0
dp[i][1] = dp[i-1][1]*2 + dp[i-1][2]*3
dp[i][2] = dp[i-1][1], for all i from 2 to N.

Note that this DP does take into consideration the rats' 3-day lifespan: from dp[i][2] you can only go to dp[i+1][1]. In other words, the rats that are two days old only contribute to the answer with the babies they make.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +14 Vote: I do not like it

    This DP can be easier: dp[n]=dp[n-1]*2+dp[n-2]*3, where dp[1]=k, dp[2]=3k.

    It is quite similar to Fibonacci numbers. You can also calculate such DP faster using matrix exponentation.

    You can also notice that the answer is 3^(n-1)*k.

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +18 Vote: I do not like it

      Yeah, it can definitely be optimised. I wanted to explain the thought process and focus less on how to make it faster, I think that's better for DP beginners.

      → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      according to you if k=5,dp[2]=15 but answer is 20 and dp[3]=45, but according to you dp[3]=30; please clear what you are storing in dp

      → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I Tried Your Implementation , But it is giving wrong ans , try it for n=3, k=5 After 3rd year there should be 145 rats , i guess it is not considering the rats died after 3rd year , i have implemented the same , but dont know if it is correct or not , but it is passing all Samples TC 

          int n,k;
    cin>>n>>k;

    vvi dp(n + 1, vi(3, 0)); // 2 means 2 days old , 1 means 1 day old

    dp[0][1] = k;

    rep(i,1,n+1)
    {

        dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][2] * 3;
        dp[i][2] = dp[i-1][1];
    }
    rep(i,0,n+1)
    {
        cout<<dp[i][1]<<" "<<dp[i][2] bn
    }

    vi rats(n+1,0);
    rats[0] = k;
    rep(i,1,n+1)
    {
        rats[i] = rats[i - 1] + dp[i - 1][1] * 2 + dp[i - 1][2] * 3;
        if(i>1)
            rats[i] -= dp[i - 2][2];
    }
    cout<<rats[n] bn

      Hope it helps someone

      → Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    thank you sir; love the approach

    → Reply