Given an Array A of n elements, (n < 200000), At each step I can transform whole array such that for every i <= 0 < n, A[i] = A[i - 1] xor A[i + 1]. Is it possible to convert whole array to 000....0 (all zeros) after infinite steps. for example if A = [ 0, 1, 0, 0, 0, 1, 0 ],
Initial: A = [ 0, 1, 0, 0, 0, 1, 0 ]
Step 1 : A = [ 1, 0, 1, 0, 1, 0, 1 ]
Step 2 : A = [ 0, 0, 0, 0, 0, 0, 0 ]
So A can be transferred to zeros after 2 steps.
PS. Consider A[-1] = A[n] = 0, always
I would be highly thankful if someone helps me to solve this task. I saw this problem few days back, will post its link if I found it.
Here are some hints to get you started:
A[i] = A[i-1] xor A[i+1],
derive a recurrence for the value ofA[i]
after two steps. What do you notice?O(n log(n))
divide-and-conquer algorithm that solves the problem.I dont fully get DanielAnderson approach, but I conjeture the following (always assuming the input has some nonzero element):
if
n = 2 k
: well, the transformation is invertible, and so the answer is always no.if
n = 4 k + 1
, you can do a backward analysis from 000..000 and get that the answer is yes only if the input is 101010...01.if
n = 4 k + 3
, here comes the conjeture, I think in this case the answer is always yes, but haven't checked it (not even with a simple code, maybe I'm lazy :))EDIT: [wrong conjeture :(, for n = 11, 11011011011011 transforms to itself, you can even prove that the only sequences that transform to itself are of that form: 110 a number of times, and then 11]
Second conjeture, this time machine tested at least (BTW in the previous comment I assumed the numbers in the sequence were only 0 and 1, as the different bits are independent in the operation described):
if
n = 2 ^ k - 1
(k >= 1
): the answer is always yes (checked with random tests up to n = 255).else the answer is no, taking into account the cases already explained in my previous post.
Anyone willing to fact check this?? :)
EDIT: forgot some cases, so in the else case the answer is I don't really know, could DanielAnderson explain his solution a bit more?
Alright, I've posted solutions below. :)
Some explanations and solutions for the hints if you get stuck. Try to figure them out yourself before reading!
Solutions below spoilers:
There are only two sequences that evolve to become the zero sequence: the zero sequence itself (trivially) and the sequence 1010101....101, ie. alternating ones and zeros that begins and ends with a one. Try to prove this formally.
Using the answer for question 1, we see that an even length sequence will only ever evolve to the zero sequence if it is already the zero sequence. ie. an even length sequence with at least one nonzero element will never become the zero sequence.
If we denote by
A[n][i]
the value of the i'th element on step n, we can find the two step recurrence by substituting the original recurrence into itself. The one-step recurrence can be written asand hence the two step recurrence reads
where we have used the fact that
A[n][i] ^ A[n][i]
cancels out.The key observation that we have to make is that the values of the sequence every two steps at the even positions
i
depends only on the elements at the other even positionsi-2
,i+2
, ie. the even and odds can be treated independently!The fact that we noticed that the even and odd positions are independent on every two-step suggests a divide-and-conquer approach in which we split the sequence into even and odds and solve recursively. First, we have several base cases:
From here, we have an odd length sequence of length at least three that is not all zeros. We first consider the subsequence of elements at even positions only. If this subsequence is a NO, then clearly the entire sequence is a NO. If this subsequence is a YES, then we know that at some point, at every even step, the original sequence will contain all zeros in the even positions. This is almost enough to tell us that the sequence becomes all zeros, but not quite, since we still do not know what happens on the odd steps. So, we can simulate just one step of the process, and repeat the exact same logic to determine whether the even elements evolve to zero on the odd steps too.
If we find that the even position elements eventually evolve to zero on both the odd and even steps, then we deduce that at some point, the even position elements remain fixed at zero forever. It is then easy to see that at this point, the entire sequence must become zero. If not, then we know that there must always be a zero somewhere in the sequence.
Hence, the answer can be determined recursively by extracting the subsequence of the even position elements, simulating one step and extracting even position elements again, and solving the subproblems for the smaller subsequences, returning YES if and only if both the even position elements at the current step and next step both returned YES.
Since every level of recursion solves a problem half the size of the original, there will be
O(log(n))
levels of recursion, takingO(n)
time each. Therefore the running time of the algorithm isO(n log(n))
A simple, recursive implementation of the divide-and-conquer solution above in C++ is:
correction for question 1: it can be alternating between any number and 0 not just 1.for example the sequence 100 0 100 also evolves to 0 0 0 in one step.
I tried your approach, but for question 3, the formula doesnt work exactly as you say, in the corners. for example if there are m numbers, then:
A[n+2][m] = A[n+1][m-1] ^ 0 = A[n][m-2] ^ A[n][m]
so, there is no simplification, because the problems changes (a little bit), and I cannot exactly apply any recursive procedure. How do you deal with that?
Now I read the algorithm under Question 4, and indeed it's correct, nice solution :) The corner case doesnt matter as you never recurse with odd positions...
woah! was there anything wrong in what I said? or did I understand the question wrong?
I think you misunderstnd the question, when we transform the sequence 1000100 we get 0101010 in one step...
nah.. I meant 100, 0 , 100 people thought 1000100 ? my choice of 100 was lame :P
Oh, now I see, the matter is that in this problem you can assume the numbers are only 0 and 1, as all the operations can be taken as independent in each of the bits, and you could solve the problem for each binary position separatly...
woah! I wonder why no one ever mentioned that although it was obvious, haha. Btw, we can deal with the situation you have mentioned if we agree to pretend that a[-1] = 0,a[-2] = a[0] , a[-3]=a[1] and so on.. and similarly a[n] = 0,a[n+1] = a[n-1], a[n+2] = a[n-2]