# Finding the final state of the $1$ dimensional “split the twos” automata

This problem is from a coding competition ( Website Here ) in Mexico that does not provide solutions and has me stuck.

Consider the following automata:

Every state $$B_k$$ is an array of fixed length $$n$$ such that $$B_k[i]$$ an integer for all $$0\leq i \leq n-1$$

The state $$B_k$$ can be obtained from the state $$B_{k-1}$$ as follows:

$$B_k[i] = B_{k-1}[i] + C_{k-1}[i]$$ if $$B_{k-1}[i] < 2$$ and $$B_k[i] = B_{k-1}[i] - 2 + C_{k-1}[i]$$ if $$B_k[i] \geq 2$$.

The quantity $$C_{k}[i]$$ is defined as the number of entries $$B_k[i-1],B_k[i+1]$$ that are at least $$2$$. (If $$i$$ is equal to $$0$$ or $$n-1$$ then $$C_k[i]$$ can be at most $$1$$).

We are given an arbitrary initial state $$B_0$$ of size $$n\leq 10^6$$ where each $$B_0[i]$$ is $$0,1$$ or $$2$$.

So in coloquial terms the only thing this automaton does is send a $$1$$ to the left and right if one of the entries is $$2$$ or more.

It is not hard to see that after a finite number of steps $$B_k$$ becomes invariant ( Because $$B_k[0]$$ cannot be equal to $$2$$ an infinite number of times we can use induction on $$n$$ for example) .

I would like to find the final state, something along the speed of $$\mathcal O(n\log(n))$$ seems to be required for the solution to pass.

Original statement:

• If I could write the iteration as some sort of multiplication in an algebra by an element $\sigma$ and calculate $\sigma^M$ with logarithmic exponentiation that would be great but I have not been able to. – Jorge Fernández Feb 26 '19 at 18:59
• I do not know how to reference it since it's ran in a buggy server that needs a username – Jorge Fernández Feb 26 '19 at 19:01
• You are given the entire array $C_0$ and along with it you are given $n$. – Jorge Fernández Feb 26 '19 at 19:22
• @Apass.Jack No, the reason you can't find it is that the website sucks and the problems are behind a different server that requires a username and password that I do not have. However luckily one of the people from my university solved it. Also, the original statement of the problem is more confusing. – Jorge Fernández Feb 26 '19 at 19:35
• Good point, thanks for fixing it. I think it is ok now. – Jorge Fernández Feb 27 '19 at 17:47