MFREQ - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY:

Easy

PREREQUISITES:

Implementation

PROBLEM:

You are given an array a consisting of of n integers. You have to answer m queries on it each of form l, r, k meaning that you have to check whether there exists an element in the range of elements a_l, a_{l + 1}, \dots, a_r that appears k times consecutively. It is guaranteed in the problem that all the queries will have the value of k more than half the number of elements in that query range, i.e. it k will be greater than \frac{r - l + 1}{2}.

EXPLANATION:

As stated in the problem, value of k will always be more than the half of the length of the number of elements in the range. One can easily see that if there exists some element which appears more than half the number of elements in the range consecutively, then this element should also appear at exactly at the middle element of the range. This is simply due to the fact that number of elements before the middle element are less than or equal to half the number of elements in the range. Same is the case with number of elements after the middle element.

Hence, our problem just turns to check whether the middle element of the range appears consecutively more than k times or not.

If the range is specified by [l, r], then the middle element of the range will be \frac{l + r}{2}.

For solving subtask 1 and 2, one can find the number of times the middle element appear consecutively in the range in \mathcal{O}(|r - l + 1|) for each query, by simply iterating over the entire range. Below is the pseudo code for details.

mid = (l + r) / 2;
cnt = 1; // corresponds to a[mid]
for i = mid + 1 to r:
  if a[i] == a[mid]:
    cnt += 1;
  else:
    break;
for i = mid - 1; i >= l; i--
  if a[i] == a[mid]:
    cnt += 1;
  else:
    break;
// Now check whether cnt >= k or not?

This takes \mathcal{O}(n) time for each query. Hence, overall time complexity is \mathcal{O}(n \cdot m).

Subtask 3:

Iterating over the entire range [l, r] for answering each query is not going to work here. We have to somehow answer a query faster. Let us see another way of seeing the largest length continuous sub-array containing a_{mid}. You can see that a_{mid} will bifurcate the the continuous sub-array into two parts, the part left to a_{mid}, and the part right to a_{mid}. If you can somehow find the first element in the left side which is not equal to a_{mid}, and similarly in the right side, then you can tell the maximum length of consecutive subarray consisting of a_{mid}.

Let L_i denote the smallest index j, such that a_{p} = a_{i} for each j \leq p \leq i.
Similarly, let R_i denote the largest index j, such that a_{p} = a_{i} for each i \leq p \leq j.

For example, consider the array

a = [1, 1, 2, 2, 3, 3, 3]

The L array will be

[1, 1, 3, 3, 5, 5, 5]

The R array will be

[2, 2, 4, 4, 7, 7, 7]

The L array can be easily found by iterating over the from left to right. See the below pseudo code:

L[1] = 1;
for i = 2 to n:
  if a[i] == a[i - 1]:
    L[i] = L[i - 1]
  else
    L[i] = i;

Similarly, R array can be found by iterating over the from right to left. See the below pseudo code:

R[n] = n;
for i = n - 1 to 1:
  if a[i] == a[i + 1]:
    R[i] = R[i + 1]
  else
    R[i] = i;

Recall that we are interested in finding out the consecutive block of equal elements in which a_{mid} lies. Observe that smallest index to the left of mid which will be in this block (all of whose elements will be equal to a_{mid}), will be max(L[mid], l). Similarly, the largest index to the right of mid which will be in this block (all of whose elements will be equal to a_{mid}), will be max(L[mid], l). So, the total number of elements in this consecutive block of numbers equal to a_{mid} will be min(R[mid], r) - max(L[mid], l) + 1.

So, all you have to do to answer the query is to check whether min(R[mid], r) - max(L[mid], l) + 1 is greater than or equal to k or not.

You can pre-compute L and R arrays in \mathcal{O}(n) time. After that, each query can be answered in \mathcal{O}(1) time. Overall complexity of the algorithm will be \mathcal{O}(n + m).

Time Complexity:

\mathcal{O}(n + m)