# How to solve the 2nd Question in ZIO 2019?

1 Like

You can create a graph of, say, N = 150 nodes. The vertex i represents the state where there are i amoeba. Connect this with directed edges to states that you can reach in one operation, and then reduce what you have into a well-known problem/algorithm.

1 Like

I don’t understand what you just wrote, but it seems you are trying to tell me an algorithm for that question, which is not needed, I just want to know the logic for any one of the sub-questions namely a, b, c of that question.

1 Like

Okay, I just realised that it has to be solved using pen-and-paper. Sorry I had no idea how ZIO works. The logic is that you want to start at 0 and end up at N - K, and in one operation, you can add A-1, B-1 or C-1. So you have a diophantine equation like ax + by + cz = d and you want to minimise x + y + z (here, a = A - 1, etc., and d = N - K). I would probably start with the variable with the largest coefficient and try to give that the maximum value, and then check if there is a solution (to check that, do the same thing again - take the variable with the second-largest coefficient and try to assign it a value as large as possible). This is a greedy approach and it is quite simple to prove that it works. To go faster, you can also eliminate a lot of solutions based on the fact that a linear combination must be some multiple of the gcd.

2 Likes

Even I did like this

Now I do understand the logic that you explained thank you very much, I tried that way before posting it on discussion forum, it doesn’t work for me if it does for you, so can you please solve any one of that sub-question as an example so I could understand it better. Sorry for the trouble, I am not able to solve it.

1 Like

Hello
This is how you do the a part of the question

You will understand this
If you didnt understand ask the doubt

Sudheera Y S

1 Like

Dude, I understood, this is just awesome, and now I don’t have any doubt. Thank You !

Again Thanks for the Explanation!

1 Like

Welcome

Sudheera Y S