AM51's blog

round 172 problem D
By AM51, 11 years ago, In English

http://mirror.codeforces.com/contest/281/problem/D

can somebody suggest an approach to this problem

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i looked at that can u please explain what is happening

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

    for each number in the sequence A[i],

    We define: MaxRight[i] = r ... where r is the smallest index where A[r]>A[i] and r>i

    Also MaxLeft[i] = l ... where l is the largest index where A[l]>A[i] and l<i

    If we checked the intervals [i,r] (A[r] XOR A[i]) , [l,i] (A[l] XOR A[i]) and [l,r] (A[l] XOR A[i]) for each index i ... We will cover all possible answers for any interval.

    Now we need to find an efficient way to compute MaxRight[i] and MaxLeft[i]

    For Computing MaxLeft[i] ... I'll check A[i-1] ...

    if A[i-1] > A[i] ... Then, MaxLeft[i]=i-1

    else ... we will need to check A[MaxLeft[i-1]] (Previously computed value)

    Till we find the first maximum to the left.

    The Same strategy can be done for MaxRight[i] ... but we will need to check A[i+1] instead and we will compute the values in reversed order.

    → Reply