ZIO19002 - Editorial

editorial
, , ,
1

Editorialist: Aryan Agarwala

Problem link: ZIO 2019 Problem 2

Explanation:

The only observation to be made in this problem is that when you divide a bacterium into X bacteria, you’re adding (X-1) bacteria to the count.

Thus, this problem can be simplified into:

You have a number K, three numbers A, B, C, and another number N.

Find the minimum number of times you have to add (A-1), (B-1), or (C-1) to K so that you can get N.

The approach to solving this problem is based on greedy and some hit-and-try. You sort A, B, and C in descending order (where A is the largest).

Let N(a) = number of times we added A-1, N(b) = number times of times we added B-1, N(c) = number of times we added C-1

You have to find the answer for each N(a), where N(a) ranges from 04 to (N-K)/(A-1). To do this for each N(a), you first pick the highest N(b) such that K + (A-1)*N(a) + (B-1)*N(b) <= N.. Then, you decide what the maximum value of n(C) can be n(C). If K + (A-1)*N(a) + (B-1)*N(b) + (C-1)*N(c)=N then N(a) + N(b) + N(c) is the answer for that n(A). Else, decrement N(b) and repeat the process with N(c). If you still haven’t found a solution by the time N(b) is 0, there is no solution for that N(a). Decrement N(a) and repeat this process. Do this for all N(a) and choose the smallest answer.

This is a demonstration of the approach on the first part of this problem:

K = 23,

A = 16,

B = 12,

C = 7,

N = 114
N(a) N(b) N(c) K + (A-1)*N(a) + (B-1)*N(b) + (C-1)*N(c)
6 0 0 113
5 1 0 109
5 0 2 110
4 2 1 111
4 1 3 112
4 0 5 113
3 4 0 112
3 3 2 113
3 2 4 114
2 5 1 114
1 6 1 110
1 5 3 111
1 4 5 112
1 3 7 113
1 2 9 114
0 10 0 110
0 8 0 111
0 7 2 112
0 6 4 113
0 5 6 114

Therefore, the optimal solution for the first subtask is min ( 3+2+4, 2+5+1, 1+2+9, 0+5+6) = 8

1 Like
2
3
4

We first simplify the conditions. We want to find \min(x+y+z) across solutions of (A-1)x+(B-1)y+(C-1)z=N-K where x,y,z\in \NN_0. Now, we consider individual cases.\\textbf{}\
a) We want 91=6x+11y+15z. Considering the equation \pmod{3} we get that 1\equiv 2y\pmod{3}. Thus, y\ge 1. So, we can remove 11 twice from both sides. Now, considering \pmod{5}, we get 4=x+(y-2)\pmod{5}. Thus, x+y-2\in \{4,9,14,\cdots\}. We can easily assume that x+y-2 is then 4 as 9 is too large. Now, we must have the remaining numbers as 15. So, we get that the value of (6x)+11(y-1) can be any integer between 30 and 55. Now, we want to remove minimum number of 15s 15s from 80 so resultant is \le 55, this is thus, just 2 so our minimum is 91=6+11*5+15*2. Thus, x+y+z=8.\ \textbf{}\
b) We want 67=6x+14y+15z. We again consider \pmod{3} to get that 1\equiv 2y\pmod{3}. Thus, y\in\{2,5,\cdots\} but 5\cdot 14>67 so y=2. Now, we want 6x+15z=39 or 2x+5y=13. Now, \pmod{5} we get that x=4 and z=1. In fact, here we found that this is a unique solution and 67=4*6+14*2+15\ \textbf{}\
c) We want 128=8x+11y+25z. Considering \pmod{11}, we get 3z-3x\equiv 7\pmod{11}, we now have z-x\in {\cdots ,-5,6,\cdots} but we can’t have z\ge 6 so, we will have z-x=-5. So, we will get x\ge 5. Now, we get 88=8z+11y+25z\implies 8=3z+2y and we want to minimize 2z-5+y. This clearly happens when (x,y,z)=(7,2,2) and (5,8,0) so the answer is 11.

1 Like
6

I feel that this is wrong, as in this case:

\Rightarrow K+(A-1)\times N(a)+(B−1)\times N(b)+(C−1)\times N(c)

\Rightarrow 23+(16-1)\times 0+(12−1)\times 10+(7−1)\times 0
\mathrm{(\because\ substituting\ the\ values\ of\ N(a), N(b), N(c) )}

\Rightarrow 23+(15)\times 0+(11)\times 10+(6)\times 0

\Rightarrow 23+0+110+0

\Rightarrow 23+110

\Rightarrow 133 \ne 110 (QED)

Do correct me if I am wrong.