2
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jorge Fernández Feb 26 '19 at 18:59
  • $\begingroup$ I do not know how to reference it since it's ran in a buggy server that needs a username $\endgroup$ – Jorge Fernández Feb 26 '19 at 19:01
  • $\begingroup$ You are given the entire array $C_0$ and along with it you are given $n$. $\endgroup$ – Jorge Fernández Feb 26 '19 at 19:22
  • 1
    $\begingroup$ @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. $\endgroup$ – Jorge Fernández Feb 26 '19 at 19:35
  • 1
    $\begingroup$ Good point, thanks for fixing it. I think it is ok now. $\endgroup$ – Jorge Fernández Feb 27 '19 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.