MFREQ - Can you share your approach for the question MFREQ.

Please share detailed approach of how you solved MFREQ.

1 Like

Observation 1 : floor((R-L+1)/2) < k ≤ R-L+1

After looking at it closely , you will realize that the value of k is either equal to or greater than total elements in the range L,R

It means the middle element will always be inside our consecutive sub array if it appears more than or greater than k time.

Hence , if we go ahead and pick the middle element , and if the middle element occurs more than or equal to k times , we can go ahead print the middle element or else the answer is -1.

Pre computation

So basically , we need to pre compute so we can answer the queries in O(1) time.

For that i used a array preComp[size][3] ,
where

preComp[i][0] = number at i index;

preComp[i][1] = start of the number at i index;

preComp[i][2] = end of the number at i index;

Example to make it more clear.

Let our array be 1,1,1,2,2,1

Then

preComp[0][0] = 1 , preComp[0][1] = 0 , preComp[0][2] = 2;

preComp[1][0] = 1 , preComp[1][1] = 0 , preComp[1][2] = 2;

preComp[2][0] = 1 , preComp[2][1] = 0 , preComp[2][2] = 2;

preComp[3][0] = 2 , preComp[3][1] = 3 , preComp[3][2] = 4;

preComp[4][0] = 2 , preComp[4][1] = 3 , preComp[4][2] = 4;

preComp[5][0] = 1 , preComp[5][1] = 5 , preComp[5][2] = 5;

This should be performed in O(n).

Query Time

Now we are provided Query L , R , k

We compute the middle element in the range by R-L+1/2

Then using our pre computation we directly find the range using ,

left = preComp[R-L+1/2][1];

right = preComp[R-L+1/2][2];

then we compute right - left and check if it greater than k ,

then we print preComp[R-L+1/2][0];

else we print 0.

Time complexity of query is O(1).

For reference code link : CodeChef: Practical coding for everyone

5 Likes

Observation: There may be only one element which occurs greater than floor((R-L+1)/2) times consecutively in the range [L, R], and the consecutive stretch of this element must extend across the centre of the range [L, R]. Hence the question changes to does the element at index (L+R)/2 exist more than k times consecutively in [L, R]?.
To check this, make run length encoding of the array which marks the starting and ending indices of each range of repeated characters. For example the array [1, 2, 2, 2, 3, 3, 1, 1, 1] will be converted to [(1, 1), (2, 4), (5, 6), (7, 9)]. Next, for each query [L, R], locate the range which contains (L+R)/2. The intersection of this range and [L, R] will give you the length of the range within [L, R]. If this value is less than k the answer is -1, else print the value at (L+R)/2.

5 Likes

This is how I solved it.

I converted parts of arrays which continuously contained same elements in 0, 1, 2 …
Like if array was 4 5 5 6 6 6 6 6 8 8 4 4
The new array will loke like 0 1 1 2 2 2 2 2 3 3 4 4

And then I have two vectors “b” and “e” in which ith element stores beginning an ending of occurance of i, respectively.
Now given a range, I check for trivial non presence by comparing the difference between l and r (number of elements that can come in between l and r) with the element on lth position and rth position ( whether it is allowed or not), then if it is not allowed I calculate maximum occurance of all the elements between l to r using vectors “a” and “b”.

My solution CodeChef: Practical coding for everyone

1 Like

@olofmeister
The second line will be , “After looking at it closely , you will realize that the value of k is either equal to or greater than half of the total elements in the range L,R” and in the end it will be to check whether right-left+1>=k. If yes then print else -1.

Can we do like this ?
We store all the ranges of continuous elements and Binary search for each L and R pre-computed and stored
for each element as ({arr[i],{start,end}) but not store the single elements (to save our worst case ).For all the single elements we can simple check if( L==R ) print -1 ??

Can we solve this question using Mo’s Algorithm??

Or, what else you can do is, simply iterate your for loop from L to R-K+1 (this is the last position where your sequence can start) and check for the condition that is the sum of next k elements is equal to the array[mid]*k.
you can see more in my solutions CodeChef: Practical coding for everyone

It is given that K is always greater than (R-L+1)/2, Hence the value if present will always lie on the center of our subarray. Now what we have to do is just to check whether middle element of subarray is present >=K times or not, but traverse would take f((R-L+1)/2) time that will not work. SO what I did was that as soon as I was given the array I maintained start and end position of consecutive series in two separate arrays, start array at index i will mark the start of the series and stop will mark then end. Note that if the array is 2,2,2,3,4,4,2,2,2 then start at index 0,1,2 all will store 0 and stop will store 3, If the array is 1,2,2,2,3,3,3 then start will be 0,1,1,1,4,4,4 and stop will be 0,3,3,3,6,6,6. Now if the when you need to find the no. of times any indexed element is present in the array then you have to just print(stop[index]-start[index]+1). But there is a catch what if L is present after the series began or what if R is present before series stopped. There is a simple way to find such cases just make a variable tmpstart whose value will be minimum(L,start[i]) and tmpstop whose value is max(R,stop) and check if(tmpstop-tmpstart+1>=K) then print middle ele else print -1.

Code: CodeChef: Practical coding for everyone

Hey @eight_bitguy, I think your solution has some corner cases which needs to be corrected. Forgive me if I am wrong…

I tried running the case

12 1

1 1 3 1 3 2 1 1 1 1 2 1

2 10 5

** Your output is 2. But I think it should be -1.**

Pre computation of the input array and answering the query in O(1) time.
Eg:

input:.3 4 5 2 2 2 2 6 7
f:…1 1 1 1 2 3 4 1 1
…l…r

just checking whether the mid point (r+l)/2th element satisfies the condition or not.
if mid element has some f[mid]>1 then there is already some element before a[mid] which are same.so, only need to check the next k-f[mid] element.

https://www.codechef.com/viewsolution/12830835

First precompute an array b[n] using
where b[i] = number of continuous occurrences of b[i] before the index i.

temp=1;
b[0]=1;
for(int i=1;;++i)
{
    if(a[i-1]==a[i])
    {
        ++temp;
        b[i]=temp;
    }
    else
    {
       temp=1;
       b[i]=temp;
    }
 }

if array a[n] is := \{ 8, 8, 1, 4, 6, 6, 6, 3, 3, 3, 3, 5, 5 \}

then array b[n] is \{ 1, 2, 1, 1, 1, 2, 3, 1, 2, 3, 4, 1, 2 \}

Now you need to modify the segment tree such that it returns the position of maximum element in the range,

along with the value of maximum element (use a global variable here).

Now construct that segment tree on array b[n].

For each query [l,r] just do a range max query on [l+k-1,r]

from segmentree you get position of max element in then range [l+k-1,r]
and also the valmax value of maximum element in then range [l+k-1,r]

Answer is a[position] and the answer is -1 if valmax < k

1 Like

@mondalsoura,
Say thanks to the test cases :smiley:

segment tree solution CodeChef: Practical coding for everyone

true that but i wrote it in a different manner.