There's a scientist named Brook who is interested in budding of cells. He has one container which initially contains only a single cell. Now Brook wants n number of cells in his container. So he can change the number of cells in container in 3 different ways -:
Double the number of cells present in the container.
Increase the number of cells in the container by 1.
Decrease the number of cells in the container by 1.
Now, all the above operations have different costs associated with them x,y,z respectively for above operations. Help brook in finding the minimum cost to generate n cells in the container starting from one cell Constraints 1<=n<=10^5 1<=x<=y<=z<=10^5
Output Format Output an integer denoting the minimum cost incurred to create n cells
Sample Input 5 2 1 3 Sample Output 4 i have been trying hard but cant get around what can work for this question
Auto comment: topic has been updated by 2020 (previous revision, new revision, compare).
Think of it as a shortest paths problem on a graph. To guarantee correctness, create a graph with 2e5 vertices.
Does the number of nodes are 2 times the n?
This is a classic example of making a node for each number, where each node has an outdegree of 3.
The more interesting version of this problem has n up to 10^18, so you can’t do that naively.
I am pretty sure you can make some greedy observations, assuming x=y=z for the hard version
if $$$x = y = z$$$
then we just need to calculate the first power of $$$2$$$ smaller or equal to $$$n$$$
and the first power of $$$2$$$ greater or equal to $$$n$$$
$$$a = 2^m \le n$$$ $$$,$$$ $$$m$$$ is maximum possible
$$$b = 2^t \ge n$$$ $$$,$$$ $$$t$$$ is minimum possible
$$$ans = x \times min(m + (n - a) , t + (b - n));$$$
but can it be solved when there are no restrictions on $$$(x , y , z)$$$ ?
$$$UPD$$$ incorrect solution
Your solution is incorrect. It can be proven that the answer is less than $$$2 \cdot log(n)$$$ for $$$x = y = z = 1$$$ (using only additions and doubling), and your solution is of order $$$O(n)$$$.
yeah you're right it's incorrect, I didn't consider some additions and then doubling.
but for time complexity it's $$$O(log (n))$$$ because I'm just considering powers of two and if $$$n = 10^{18}$$$ it will be $$$O(60)$$$, because $$$2^{60}$$$ is greater than $$$10^{18}$$$
code.
correct me if I'm wrong.
I was referring to the solution complexity (how big your solution is), not the time complexity of the algorithm. You are right, the solution runs in $$$O(log(n))$$$, but your answer is of order $$$O(n)$$$.
yeah the answer is in order of $$$O(n)$$$.
thanks for discussing the issue of my solution, I'll try better next time :D.
How to solve the problem with constraints upto 10^18?
I was just thinking if it's possible to do this kind of question using dp somehow like can we create state and state transition for this type of question I found a solution but not able to prove that this works
[user:agtxdy][user:agtxdy] if i is even dp[i]= min(dp[i/2]+x,dp[i-1]+y} ;
if i is odd dp[i]=min(dp[i-1]+y,dp[i+1/2]+x+z} ;meme
It can be proven that the number of doubling operations should be relatively small (less than $$$2 + log_{2}(n * max(y, z))$$$). Let's iterate over this number of operations, and call it $$$a$$$.
Without any additions/subtractions, the final number would be $$$2^a$$$. Now, any addition or subtraction can add/subtract any power of two of form $$$2^b$$$, where $$$b \leq a$$$, depending on where it is placed. Also, at most one addition/subtraction of $$$2^b$$$ with $$$b < a$$$ makes sense. In fact, we can argue that $$$n$$$ will be formed by satisfying the equation $$$n = 2^a * k + b$$$, where $$$|b| < 2^a$$$. It can be seen that only a handful of values for $$$k$$$ make sense in a scenario like this (2 at most).
Let's add cost $$$n\text{ div }2^a * y$$$ to our current case, and set $$$n' = n\text{ mod }2^a$$$. Now we're left with an easier problem, writing $$$n'$$$ as a sum of powers of $$$2$$$, with sign either $$$+1$$$ or $$$-1$$$ (note the fact that the upper bound on the power of $$$2$$$ has disappeared, this is ultra important). It's important that you convince yourself that we're allowed to do thnt.
This problem can be solved using dp in complexity $$$O(a)$$$.
Total complexity is $$$O(log^2(n * (x + y + z)))$$$
Source code: https://pastebin.com/84Fcm9SP
Could you give me the link of this problem for practicing?