Arsh_a_d's blog

By Arsh_a_d, history, 2 weeks ago, In English

Given an Array 'A' of size N, we have to choose a 'cyclic subarray R of length N' such that the value of R[0] + R[0]^R[1] + R[0]^R[1]^R[2] + ......... + R[0]^R[1]^R[2]^.....R[N-1]^R[N]Edit: Upto R[N-1] not R[N] is maximum.

Task: You have to return/print the maximum value.

[Note: ^ represents bitwise XOR.]

Examples of Cyclic Subarray: Let's take an Array A = [2, 5, 1, 7, 9], then,

for index 0; [2, 5, 1, 7, 9] and [2, 9, 7, 1, 5] are two cyclic Subarray of size(A) = N.

Similarly, for index 1; [5, 1, 7, 9, 2] and [5, 2, 9, 7, 1] are another two cyclic Subarray of size(A) = N.

Similarly, for index 2; [1, 7, 9, 2, 5] and [1, 5, 2, 9, 7] are another two cyclic Subarray of size(A) = N.

and so on.

What should be the approach to solve this problem? I tried Applying Trie and Gaussian Elimination but I am not able to come up with a solution.

Test Case Example: Input: A = [7, 8, 5, 5, 9, 2, 2, 0, 1, 6] Output: 99

Explanation: The cyclic subarray starting at index 2(leftwards), [5, 8, 7, 6, 1, 0, 2, 2, 9, 5] will have the maximum value of 5 + 5^8 + 5^8^7 + 5^8^7^6 + 5^8^7^6^1 + 5^8^7^6^1^0 + 5^8^7^6^1^0^2 + 5^8^7^6^1^0^2^2 + 5^8^7^6^1^0^2^2^9 + 5^8^7^6^1^0^2^2^9^5 = 99

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I didn't think much, but it seems to me that you can get this function from an array pretty fast. If you have two segments and for each segment you know its XOR, length and number of enabled bits in every position, you can merge them in $$$O(logA)$$$. So, what is the solution, you have to firstly write the array two times ($$$a_{i} = a_{i-n}, i > n$$$), then build segment tree and save XOR of segment, lenght of Segment and number of enabled bits in every position. Then you just have to ask $$$f(i..i+N-1)$$$ for each $$$i \in [1;n]$$$, so the answer is $$$\max_{i=1}^n{f(i..i+N-1)}$$$. Each call of function $$$get$$$ will work in $$$O(logA \cdot logN)$$$, so total complexity is $$$O(N \cdot logA \cdot logN)$$$.

PS: Maybe there exists an $$$O(NlogN)$$$ solution, if so, please reply me

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

    You can keep the information of your seg tree for ranges [N, N+i) (or simply [0, i)) and [i, N). Building and using that to merge [i, N) + [N, N+i) ranges takes $$$O(NlogA)$$$ total.

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

    Since I was not very much aware of Segment Tree, I am replying late because I had to learn them first. So here are couple of follow up Questions:

    1. How storing number of bits is helping to get the desired result in your solution?
    2. I don't see your solution taking in account the 'reverse Cycles (going right to left for any index)'. Can you elaborate how your solution will find the 'given function' if A = [1, 5, 8, 6] and you have to calculate the function for [5, 1, 6, 8], since it is a reverse cycle starting at index 1 (0 based indexing).
    3. What essentially the merge function will do with the results obtained from the child nodes?

    P.S. Please don't mind if my questions are kinda novice type.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      First and thirds question seem to be quite similar.

      So, lets look how we can merge two nodes. Lets look at every bit separately. If we know number of bits enabled in right side and xor of left segment, we can get number of bits in merged segment: $$$cnt = l.cnt + (l.xor ? (r.len - r.cnt) : (r.cnt)) $$$.

      code

      And about your second question, I didn't think about it right now, maybe I'll think about it later.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

R[0]^R[1]^R[2]^.....R[N-1]^R[N]

Is it correct? R[N] is R[0] so you count R[0] twice.

If you have the value sum = R[0] + R[0]^R[1] + R[0]^R[1]^R[2] + ......... + R[0]^R[1]^R[2]^.....R[N-1]^R[N] for some index i you can calculate it for index i+1 by xoring previous value sum with R[0] (and adding the missing last item R[1]^R[2]^.....R[N]^R[N+1], if it is correct) because R[0]^R[0] = 0. Similarly for the right-to-left direction, which hints on $$$O(N)$$$ solution.

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

    No, R[N] is not always R[0]. If you see my sample test case example, there are two 5s so it's only a coincidence in this example otherwise R[0] and R[N] is not gonna be same all the time.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We have:

      • an Array 'A' of size N
      • cyclic subarray R of length N
      • 0-indexed arrays

      So the last term in the sum should be

      $$$R[0] \oplus R[1] \oplus R[2] \oplus \dots \oplus R[N-2] \oplus R[N-1]$$$

      (N terms in the expression, not N+1 terms as in R[0]^R[1]^R[2]^.....R[N-1]^R[N]). And the sample test case confirms it. This expression is constant for all subarrays R, let's denote it as Z. So if we have the value

      $$$sum_0 = A[0] + A[0] \oplus A[1] + \dots + A[0] \oplus A[1] \oplus \dots \oplus A[N-1]$$$

      we can calculate

      $$$sum_1 = A[1] + A[1] \oplus A[2] + \dots + A[1] \oplus A[2] \oplus \dots \oplus A[N-1] \oplus A[0]$$$

      as

      $$$sum_1 = sum_0 \oplus A[0] + Z$$$

      Next we can calculate

      $$$sum_2 = sum_1 \oplus A[1] + Z$$$

      and so on:

      $$$sum_i = sum_{i-1} \oplus A[i-1] + Z$$$

      We just have to choose the largest value among all values sum[i] (here i changes from 0 to N-1). Similarly for the right to left direction.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, You are correct. The last term is R[N-1] not R[N]. But the problem is how efficiently we can calculate Z (Which you didn't specified). On top of that, sum1=sum0⊕A[0]+Z for me, seems to only work if we assume XOR to be distributive over Addition, which I don't think is true. Can you tell me how sum1=sum0⊕A[0]+Z holds true?

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Seems you are right and I am wrong. Sorry for your wasted time.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$Z$$$ is $$$A[0] \oplus A[1] \oplus \dots \oplus A[N-2] \oplus A[N-1]$$$ or XOR of all array elements.

      Ok. Let's try next $$$O(N)$$$ approach. We will consider each bit separately for each sum item. We need only general information about bit count for each bit position. I suppose that $$$a[i] \le 10^9$$$. Instead of single number $$$sum$$$ we will support the array $$$bits$$$ of size 30. $$$bits_i$$$ means the number of bit 1 in all $$$N$$$ items of our sum in position $$$i$$$. Thus we can easily restore the value $$$sum$$$:

          #define MAXN 100000
      
          int n, a[MAXN], bits[32];
      
          long long getsum( void )
          {
            int i;
            long long sum = 0;
            for( i = 0; i < 30; ++i)
              sum += (long long) bits[i] << i;
            return sum;
          }
      

      Then the rule $$$sum_i = sum_{i−1} \oplus A[i−1] + Z$$$ turns into correct transformation of the array $$$bits$$$:

      • if bit number $$$j$$$ is set into $$$A[i-1]$$$ then $$$bits[j]$$$ becomes $$$n - bits[j]$$$ because $$$1 \oplus 1$$$ is zero;
      • if bit number $$$j$$$ is set into $$$Z$$$ then $$$bits[j]$$$ becomes $$$bits[j] + 1$$$.

      I.e.

          for( j = 0; j < 30; ++j)
          {
            if( (a[i-1] >> j) & 1 ) bits[j] = n - bits[j];
            if( (z >> j) & 1 ) bits[j]++;
          }
      
      Code

      PS Hope this approach is correct.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Arsh_a_d (previous revision, new revision, compare).