Axelius's blog

Help with UVA problem 11235 — RMQ
By Axelius, history, 8 years ago, In English

Hello ,

I need help with problem 11235 — RMQ of UVA
Link : — https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2176
Approach applied : I know that this question is of segment tree, and the values being in sorted order can further be used to calculate frequencies . The new frequency array should be pushed into segment tree , but after that I am lost . How would I then use the segment tree to calculate the answer , because I can't calculate answer for like (5,10) etc. Any help is appreciated !

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

Comments Comments (15)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Read the problem... "You are given a sequence of n integers a1, a2, . . . , an in non-decreasing order" that's all...

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

    Yes with that it will be easy to calculate frequency of a number Due to large n we cant do it linear But then how to use that in a segment tree

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

      Sorry for my poor english.

      For each range (or node) you must store five values:

      the leftmost value, the frequency of the the leftmost value, the rightmost value, the frequency of the the rightmost value, the maximum frequency(the answer).

      Now you can merge any two nodes. be careful when the rightmost value from the left node is equal to the leftmost value from the right node.

      I hope this helps you to solve the problem.

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

        Since I am new to segment tree , I am not quite sure how to merge the nodes.
        Can you help?

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

          Sorry for my poor English. Lets be:

          a : leftmost node

          b: rightmost node

          you must find: c = f(a,b)

          where f is a function for merge two nodes. Basically this means to gather information from the nodes a and b, in the resulting node c. Now you must think. How join information from the children nodes? for example if you solve the classic Range Minimum Query problem, you have only a minimum value. And you must update c.min = min(a.min,b.min) and that's all!. But now you must think how update the five values (for my approach). ask yourself: 'How update the leftmost value, the frequency of the the leftmost value, the rightmost value, the frequency of the the rightmost value, the maximum frequency(the answer) for the parent node?' I hope this helps you. Good luck.

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

            I understand the building tree part . But , how to make query ? How to merge two nodes answer ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Suppose every node in your tree is of 'node' type.

              So your update may look like this — 

              node query(...) {
    if in range return this node
    node leftq = query(left)
    node rightq = query(right)
    return merge(leftq, rightq)
}
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Can you look at my code . Whats wrong in merging two node in query function ? code

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

                  I recommend you to code a merge function.

                  c = f(a,b)

                  or

                  node = merge(node a,node b){ ... }

                  So if you know how join(or merge) two nodes then you can use it in the build process of the the segment tree, in the update process and also in the query process...

                  Because in every step you need to merge two nodes... right?

                  → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

just build a segment tree for the given array don't edit it. each node in the segment tree should has the following information about its range 1- what is the most frequent value in this range and its count 2-count of integers with the same value at the beginning of the range from left and the value it self 3-count of integers with the same value at the end of the range from right and the value it self i.e the node correspond for the range [1,1,5,5,5,6] should be like max=5 maxCount=3 maxl=1 countL=2 maxR=6 countR=1 now suppose you have two node how to merge them?? its easy just think how to mege them to get the information of the resulting node to conclude its the the same idea as normal segment tree the only change is the merge function of two node .

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Another way to solve this problem is create a new array of frequency F, where F[i] = frequency(A[i]), and to answer queries you can use simple RMQ over F, but handling these cases:

Let's say you have a Query [i,j]:

L[x], left-most appearance of value x

R[x], right-most appearance of value x,

1.- If A[i]==A[j] : j-i+1

2.- If A[i]!=A[i-1] and A[j]!=A[j+1] : RMQ (i,j)

3.- If A[i]==A[i-1] and A[j]!=A[j+1] : max(R[A[i]]-i+1, RMQ (R[A[i]+1], j))

Now an example for the third case, suppose you have an array: 1 1 1 2 2 3 3, the respective F array will be 3 3 3 2 2 2 2, and you have to answer the query [1, 4] (0 index).

Clearly, RMQ(1,4) = 3, and it's incorrect. But, given that the array is already sorted, you should know the rightmost position where the number 1 appears, so the answer should be:

MAX(amount of 1's in F[1..4], RMQ(R[1] + 1, 4)) = MAX(2,RMQ(3,4)) = MAX(2,2) = 2

There are still two more cases to handle,

4.- A[i]!=A[i-1] and A[j]==A[j+1]

5.- A[i]==A[i-1] and A[j]==A[j+1]

It's up to you to deduce the answer, good luck :)

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

    I will try your approach. but in this case I think the segment tree is more appropriate and easy to code.

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

    Why would you use Array instead of segment tree?

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

      You will use a segment tree over the array F to get the RMQ's

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hello friend, just wanted you to know that your answer helped me a lot.

    → Reply