# You have K amoebas and one amoeba can divide into A,B,C amoebas after one instruction then find the minimum no. of instruction to have N amoebas

. You have developed an artificial amoeba, and you can control exactly how it divides. Each individual amoeba can be instructed to divide into A, B, or C amoebas. That is, if you instruct an amoeba to divide into A, this amoeba will disappear, and A different new amoeba will appear. You start out with K amoeba initially, and you want to give them instructions such that at the end, you have exactly N amoeba left. Giving an instruction is a costly affair because it requires you to produce some biochemicals, and so you want to give as few instructions as possible. Find and write the minimum number of instructions that you should give to end up with exactly N amoebas. If it cannot be done, write −1 instead. Note that each instruction is given to a single amoeba, and not all of them together. For example, suppose K = 1, A = 1, B = 2, C = 3, N = 4. Then, you can take the single amoeba, instruct it to divide into B(2) amoebas. Now, there are 2 amoebas. Then take one of these amoebas and instruct it to divide into C(3) amoebas. So now, you have 4 total amoebas, which is what we want, and we used 2 instructions. You can check that you can’t get 4 amoebas with fewer than 2 instructions, and hence 2 is the minimum, and so the answer is 2. Find the minimum number of instructions needed for these instances:

(a) K = 23, A = 7, B = 12, C = 16, N = 114 (b) K = 9, A = 7, B = 15, C = 16, N = 76 (c) K = 10, A = 9, B = 12, C = 26, N = 138

• I thought hard even tried a greedy approach but it doesn't seem to work plz help thanks in advance Nov 9 '19 at 17:12
• Where is this problem from? Nov 9 '19 at 18:37
• This is one of the problems asked in zonal informatics Olympiad which is the first level of selection procedure for the Indian team for international Olympiad in informatics or IOI. Nov 10 '19 at 1:13
• Please edit the question to credit the original source of the problem. See our guidelines.
– D.W.
Nov 11 '19 at 1:16
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving contest-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question.
– D.W.
Nov 11 '19 at 1:17

The problem is equivalent to that of finding $$\begin{array}{l} \min x_1 + x_2 + x_3 \quad \mbox{s.t.} \\ x_1 (A-1) + x_2 (B-1) + x_3 (C-1) = N - K \\ x_1,x_2,x_3 \in \mathbb{N} \end{array}$$
Assuming $$A,B,C \ge 1$$, this can be solved in $$O(N-K)$$ time (for $$N-K>0$$) via dynamic programming and, depending on the values of $$A$$, $$B$$, and $$C$$, the greedy algorithm might work too. See the change making problem. A slight modification of the dynamic programming algorithm also works if any of $$A,B,C$$ is $$0$$.
• That just means that the values of three variables are to be found, namely $x_1$, $x_2$, and $x_3$. Here $x_1$ represents the number of instructions of type A, $x_2$ is the number of instructions of type B, etc. The goal is to minimize the total number of instructions, which is just the sum of $x_1$, $x_2$, and $x_3$. The first constraint tells you that the net number of newly created amoebas should be $N-K$ (so that the total is $N$), and the second constraint just means that the variables are non-negative integers. Nov 10 '19 at 1:27
• As an example, if $K=1$, $N=23$, $A=3$, $B=6$, $C=11$, then $x_1 = 1$, $x_2 = 0$, $x_3=2$. Nov 10 '19 at 1:33
• If $\min\{A,B,C\}=0$ you can essentially kill one amoeba at a time. Then, you can generate more than $N-K$ amoebas as long as the objective function accounts for the cost of killing the excess amoebas. This boils down to using the dynamic programming algorithm for the non-zero values of $A,B,C$ until you compute the minimum number of operations $OPT[x]$ that are needed to generate a net number of $x$ new amoebas for $x$ up to $N-K$. Then return the best solution between $OPT[N-K]$ and $\min_{x<N-K}\{ OPT[x] + 1 + \min_{\substack{y=A,B,C \\ y+x > N-K}}\{ y + x - (N-K) \} \}.$ Nov 10 '19 at 18:45