Editorial for COCI '12 Contest 6 #6 Bakterije

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Take a look at a bacterium: its state can be described using three parameters $X$ ~X~, $Y$ ~Y~ and $C$ ~C~, where $X$ ~X~ and $Y$ ~Y~ present a row/column mark of the cell in which the bacterium currently is, and $C$ ~C~ is the direction bacterium is facing. If we simulate the movement of the bacterium, we can notice the bacterium will eventually encounter a state it had been in before and, since the rules of moving do not change, the bacterium has closed the loop in which it will cycle forever (or by the end of the game). The path of the bacterium will be as shown in the picture:

$\text{[math]}$

Circles present the states of the bacterium, and arrows its movement. Part of the path which is not in the loop is called "tail". Let $L_i$ ~L_i~ be the number of states in the loop of the $i^\text{th}$ ~i^\text{th}~ bacterium, and $T_{i,X,Y,C}$ ~T_{i,X,Y,C}~ the second in which the bacterium first encountered a state $(X, Y, C)$ ~(X, Y, C)~. If the state $(X, Y, C)$ ~(X, Y, C)~ is on the "tail", this second is the only one in which the bacterium is in a state $(X, Y, C)$ ~(X, Y, C)~, and if it is in the loop, it will be there in seconds:

$\displaystyle t = T_{i,X,Y,C} + k \times L_i, k \ge 0$

Assume that in the final second of the game, the bacterium $i$ ~i~ will be in a state $(X_e, Y_e, C_i)$ ~(X_e, Y_e, C_i)~, where $X_e$ ~X_e~, $Y_e$ ~Y_e~ marks a trapped cell. If some bacterium is in that state for the first and the only time (regardless of the game end), then it is trivial to check if other bacteria will be in the final state in that second. If not, we have a system of $K$ ~K~ equations:

$\displaystyle t = T_{i,X,Y,C} + k_i \times L_i, k_i \ge 0$

which can also be presented using congruences:

$\displaystyle t \equiv T_{i,X,Y,C} \pmod{L_i}, \text{with }t \ge T_{i,X,Y,C}$

This problem is solved using the Chinese remainder theorem. Since the theorem offers a solution if the modules ( $L_i$ ~L_i~ in our case) are pairwise coprime, we have to split every $L_i$ ~L_i~ to coprime factors (powers of primes). We thus get a greater number of equations but the modules will now be pairwise coprime. In case there are two powers of the same prime number $p$ ~p~ among the modules, we can eliminate the smaller one because the remainder of division by it is uniquely determined from the remainder of division by the greater one (if they do not match, there is no solution).

Comments

There are no comments at the moment.