feb. long challenge 2017

Just saw video tutorial and tried to implement MFREQ question…
can anyone tell me what am I missing at?
here is my code:

#include 
using namespace std;

int main() {
    
	int n,m;
	cin>>n>>m;
	long long a[n],left[n],right[n];
	for(int i=0;i>a[i];
	for(int i=0;i>l>>r>>k;
	     
	    left[0]=0;
	    for(int i=1;i=0;i--)
	    {
	        if(a[i]==a[i+1])
	        right[i]=i+1;
	        else
	        right[i]=i;
	    }
	    for(int i=0;i<n;i++)
	    cout<<left[i]<<" ";    //left array
	    cout<<endl;
	     for(int i=0;i<n;i++)
	    cout<<right[i]<=k)    // not getting this condition 
	    cout<<a[mid]<<endl;
	   else 
	   cout<<-1<<endl;
	}
}

Please help me…

Your code is not even passing the sample test. But that’s not the concern, the concern is blindly copying things without understanding. Dear, don’t write anything in your code before getting the concept. Brainstorm, use pen and paper to see how loops working, think, but don’t blindly copy. It will hurt a lot in long run!

For sample case-

5 1
1 2 2 2 2
1 5 3

Your output is-

0 1 1 2 3 
0 2 3 4 4 -1

Regarding where your code is failing, I need some time to debug it. Will update as soon as possible.

EDIT- Check this submission. This one makes another array to count the cumber of consecutive elements, and returns the element when the repetition is more than k. Be careful the array names are similar (at and ar1, don’t get confused!)

EDIT2- Yes, others are right, the left and right arrays are wrong. Please re-check the video from 2:22 onwards where he discusses this concept.

1 Like

@vijju123
My left and right arrays are correct as explained by gkcs …but not getting the answer to be produced when condition satisfies

1) Your calculations for left and right arrays are wrong.

Either you misunderstood about left and right arrays or you messed up the implementation.

E.g Array = 1 2 2 2 2 (Consider indexing 0).

Left Array = 0 1 1 1 1

Right Array = 0 4 4 4 4

This is what we are supposed to construct.

Now lets have a look at your code.

You code for generation of left array does the following.

Suppose the input array is same, then your left array would be

0 1 1 2 3

As you can see, this is wrong.!!!

2) You are generating left and right arrays m number of times.

The whole purpose of generating these arrays was to order the query in O(1).

And hence we should only generate them once for a particular input array and then answer all the queries.

This is generally called as preprocessing.

So you need not generate the left and right arrays m number of times.

2 Likes

There is some problem in calculating left and right array.I am pretty sure those are not correct.check the method of calculating them or you may have made any other mistake.You are calculating them m times but you have to calculate in only once and then answer the queries.

2 Likes

You are constructing the left and right array completely wrong. left array is used to hold if a number repeats consecutively then what is the start index of that repeating number and right array is used to hold what is the end index of that repeating number.
Fixed… I commented the changes . You can go through it
Click Here

1 Like

If you still have any doubt then you can check my solution …
i’ve code it after watching the video tutorial i hope it’ll help

Gerrymander - https://www.codechef.com/viewsolution/13097085

Most frequent element - https://www.codechef.com/viewsolution/13096986

1 Like

please upvote me so that I can get karma points to ask my first question.

1 Like

I am trying to debug. Thanks for info!

True, even I was feeling the same. Cause I felt the purpose of array was kinda defeated when inside the test-case loop.

Hi @adhish_kapoor,
In the code, you need to modify these statements:

left[i]=i-1; —> left[i]=left[i-1];

and

right[i]=i+1; —> right[i]=right[i+1];

I am sorry if I was ambiguous in the editorial. These are the values we set the array positions to, if we find a corresponding equal adjacent element. If there are further doubts, I will be happy to help :slight_smile:

1 Like

You saved me a lot of time. Thanks!
I always feel privileged to be part of this community :smiley:

Thanks I got it