Weird Bacteria-Procon Junior 2017

Can someone please tell me the reason of the following losing condition in problem WEIRD of PROCON Junior 2017

when both a and b are even and their difference is 2

It is clear that when a=b it is always possible for Second Player to reach same condition a=b irrespective of the first player move.

@vijju123 please use this one : CodeChef: Practical coding for everyone

i also want to know the solution but does not have enough karma to ask!

I think I have an answer. Here, we define a winning position to be when the player who will play next has a confirmed strategy to win.

I assume you know why (k, k) is a losing position. So Bran tries to convert the two testtubes into a (k, k) form. So, let him add x bactera from TT B to TT A. Here, for simplicity bacteria in TT B is larger than bacteria in TT A. So,

a + {x/2} = b - x
b - a = x + {x/2}

Now, look at the values of x + {x/2}, you’ll observe they are always 0, 1 \pmod{3}. Hence, if a - b \equiv 0, 1 \pmod{3} we are done.

Now if a-b = 2 \pmod {3} for x > 2, we’ll try to prove that we can turn it into a set of form (k, k+2) which is also a losing position for other. This is always possible as b-a-2 \equiv 0 \pmod{3} and we can find an x for this and simply remove x from TT B (try to think why this works).

Now, here is the heart of the question, why is the exception when b - a = 2?
The answer: because here b - a - 2 = 0, the minimum we can take is 1.

If you have any doubts, feel free to ask.

1 Like

Link is broken :frowning:

Okay, i will work for a solution :slight_smile:

Thanks for dhruv and alax for their views. I seriously felt that answer was not upto the mark after reading that. Your approaches were really awesome :slight_smile:

@vijju123 I’ve added a solution. Could you review it?

I think you might need to expand this line a bit -

Now, look at the values of x+x/2, you'll observe they are always 0,1(mod3). Hence, if a−b≡0,1(mod3)a−b≡0,1(mod3) we are done.

Its a nice answer dear :slight_smile: