Блог пользователя Confused101

Автор Confused101, история, 8 лет назад, По-английски
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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      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 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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]