SNAKEEAT - Editorial

@tony_hager thanks a lot for this.

I used merge sort and binary search in my code, still I was getting Time Limit Exceeded error
My code

@victor_arsenal, I have run your program against my test files and it gives exactly the same output as my own program, which got AC.

wow, strange. When I submitedt it in the contest, it returned WA. Anyway, thank you very much.

Thank you for your videos. I think it will be great if you do some hard problems or problems based on some rare topic :slight_smile: Keep up the good work!

Hi @ista2000,
Thanks for the feedback!
There are some hard and rare problems picked up on the channel: Mo’s Algorithm with Updates, Fourier Transform, Persistent Segment Trees etc…
You could have a look at them.

1 Like

can someone please help me with my code ?
getting WA. though I couldn’t find any test case

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
int test;
cin>>test;
while(test--){
	ll i,q,j,k,n,m;
	cin>>n>>q;
	vector<ll> v(n+1,0),dif(n+1,0);
	for(i=1;i<=n;i++)
		cin>>v[i];
	sort(v.begin(), v.end());
	for(i=1;i<=n;i++)
		dif[i]=dif[i-1]+v[i];//prefix sum
	while(q--){	//use tree=snake
		cin>>k;
		ll low=0,high=n;
		while(low<high){//we ask if mid number of trees are possible
			ll mid=(low+high+1)/2;//throws back to high ,i.e. low=4,high=5 gives mid=5
			ll index=n-mid,big_index=lower_bound(v.begin(),v.end(),k)-v.begin();
			big_index-=(v[big_index]>k?1:0);//last index where v[i]<k
			ll val=k*(big_index-index)-(dif[big_index]-dif[index]);
			//val is number of tree required to make mid number of trees possible
			val=max(val,0LL);//not required now
			if((index>=val && big_index>index) || big_index<=index)
				low=mid;//if mid number of trees are possible
			else high=mid-1; 
		}
		cout<<high<<"\n";
	}
}
	return 0;
}

why my solution is wrong
https://www.codechef.com/viewsolution/57678271

Why am i getting wrong answer? And could you please give me a testcase?

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

I sorted both queries and lengths array.
My starting index of the array keeps increasing with the query. So it never resets with the query.

For every query, the end index updates to the (upperBound-1) of the query. And the start keeps increasing and when the length of the snake==query, i update the count as well as end.

And then i print the count.