frequent values SPOJ

Was trying to solve SPOJ.com - Problem FREQUENT and since was unable to figure out so finally looked at the solutions spoj-cpp/1684_FREQUENT.cpp at master · hbdhj/spoj-cpp · GitHub
There I was unable to figure out what was being done in line 127 :-
““int temp = min(Tree[Node<<1].rfreq, m-u+1) + min(Tree[(Node<<1)+1].lfreq, v-m);””
kindly explain… Though I know that here the mf was being calculated by using the leftnode.rf and rightnode.lf but what was the “m-u+1” & “v-m” was doing???

Suppose you have an array A of N elements, indexed as 0, 1, …, N - 1 then consider a query (I, J), that is finding most frequent element between index I and J, both inclusive. Now there are 3 cases with respect to mid index M = (I + J) / 2

  1. Index J is on left side of Index M.
  2. Index I is on right side of Index M.
  3. Index M is in between of I and J.

Now for first two cases you can go with querying one side of Index M, but if Index M is in between the index I and J then we need to compute most frequent element of left part [lfreq] and right part [rfreq] and then we have to check whether values at Index M and (M + 1) are equal or not.

If values are different then answer to query is maximum of lfreq and rfreq, but if values are same then we need to check whether the second last element of left part of array A[M - I + 1] and the second element of right part of array A[J - M] are different from the values at Index M and (M + 1) respectively.

To do so, just check whether the second last element of left part of array is smaller than rfreq and similarly verify the same for second element of right part of array and lfreq, and once we have the minimum frequent elements of left and right side of array, check whether the previously computed frequent element is greater or the temp frequent element, then just return the maximum of the two values.

3 Likes