Omar_Elaraby's blog

By Omar_Elaraby, 5 days ago, In English

I need help to solve this problem from an ICPC Regional Contest

It's easy to find the MEX difference of the subarray [l:r] in O(1), F(l, r). but what makes it hard is to find the maximum MEX difference among all subarrays inside range l:r

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

»
5 days ago, # |
  Vote: I like it +1 Vote: I do not like it

can you provide the link of this problem ?

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

      here is my code

      feel free to ask me anything !

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

        Thank you

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

          What can i do if i am not allowed to see the contest? Really wanna upsolve this now(

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

            you need to join this group in order to see the contest

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

              ty!

»
5 days ago, # |
  Vote: I like it +4 Vote: I do not like it

my approach: first, absolute values are hard to work with so let's remove them by calculating the max value of MEX(P,a,b) - MEX(Q,a,b) over all a,b for a query (and similarly MEX(Q,a,b) - MEX(P,a,b)) and answer is the max of these 2

now to maximize MEX(P,a,b) - MEX(Q,a,b), let's think of a naive solution first: let's loop over all values X which MEX(P,a,b) can be, and try to minimize MEX(Q,a,b). Well observe that as you extend a subarray by 1 ([a,b] -> [a-1,b] or [a,b+1]) the mex can only increase, so we want to find the smallest subarray where MEX(P,a,b) equals X

well this can be done with a simple loop:

first calculate index:

for(int i = 0; i < n; i++)
  a_index[a[i]] = i;

then something like:

int l = n, r = -1;
for(int i = 0; i < n; i++) {
  l = min(l, a_index[i]);
  r = max(r, a_index[i]);
}

finally we can observe that these "minimal-mex" subarrays in a can only increase in length, so for a query, we can binary search the largest mex for which that corresponding "minimal-length" subarray is contained in the query. And also store MEX(P,a,b) - MEX(Q,a,b) in an array, prefix-maxed