ZIO19002 - Editorial

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