Cell mitosis dp

#1

plz provide the link to the question as i have a diff approach and i want to submit and see if it works or not…

also if we forget about constraints for once then will this recursive code work for all small test cases and give right ans…??plz confirm…

#2

reply at the earliest…

#3

https://hack.codingblocks.com/app/contests/1338/546/problem

#4

plz reply for the recursive code as well…and its question mentioned above…

#5

there are 3 cases

  1. Double the number of cells present in the container.
  2. Increase the number of cells in the container by 1.
  3. Decrease the number of cells in the container by 1.
    you consider only two
#6

i have gone in back manner that is tried to convert n to 1 and in that case wont adding 1 to it gives run time error as it will never give 1…it will just inc

#7

if you want to do it recursively
start from 1 and try to reach till n

your approach will not always give correct output

#8

why 1 to n is not same as n to 1…plz provide a test case…

#9

for input
11
2 1 3

your output is 6 but correct one is 7

you can’t divide it by 2 if it is not multiple of 2

#10

this way it can be managed…
if(n%2==0)
{
return dp[n]=min(x+recur(n/2),y+recur(n-1));
}
else
return dp[n]=y+recur(n-1);

while using recursion how do i ensure that it doesnt run time error…if i include 3 condition of n+1.

#11

make a check that if your n is greater than N then return

#12

return what?? it is int function…


why is this code showing no output and errors…plz correct it…using top down dp …
reply at the earliest…

#13

it is not possible to do it in this manner
you can take one simple example and dry run it you will realize that it will stuck in a cycle

correct way to do this is

recursive code look like:

// CellMitosis.cpp
#include<bits/stdc++.h>
using namespace std;
int CellMitosis(int n,int x,int y,int z) {
    // base case:
    if (n <= 1) return 0;
    // recursion:
    int mincost=INT_MAX;
    if (n % 2 == 0) {
        mincost = min(mincost, x + CellMitosis(n / 2, x, y, z));
        mincost = min(mincost, y + CellMitosis(n - 1, x, y, z));
    }
    else {
        mincost = min(mincost, x + z + CellMitosis((n + 1) / 2 , x, y, z));
        mincost = min(mincost, y + CellMitosis(n - 1, x, y, z));
    }
    return mincost;
}
int main() {
    int n,x,y,z;
    cin >> n;
    cin >> x >> y >> z;
    cout << CellMitosis(n,x,y,z) << endl;
}

i hope this help
if you have more doubts regarding this feel free to ask
if your doubt is resolved mark it as resolved from your doubt section inside your course

#14

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.