Confused101's blog

By Confused101, history, 8 years ago, In English
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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Here are some hints to get you started:

  1. Consider an array of all zeros. What must the array have looked like one step before it became all zeros?
  2. Consider an even length array that isn't all zeros (it has at least some ones in it). Use (1) to deduce an important fact about such even length arrays.
  3. Using the given recurrence for one step A[i] = A[i-1] xor A[i+1], derive a recurrence for the value of A[i] after two steps. What do you notice?
  4. Combining the above three observations, find an O(n log(n)) divide-and-conquer algorithm that solves the problem.
  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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]

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Some explanations and solutions for the hints if you get stuck. Try to figure them out yourself before reading!

    Solutions below spoilers:

    Question 1
    Question 2
    Question 3
    Question 4 (The solution)
    Implementation
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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...

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      woah! was there anything wrong in what I said? or did I understand the question wrong?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you misunderstnd the question, when we transform the sequence 1000100 we get 0101010 in one step...

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          nah.. I meant 100, 0 , 100 people thought 1000100 ? my choice of 100 was lame :P

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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...

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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]