#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+5,mod=1e9+7;

int mat[20][20],dp[20][20];
int main()
{
	int t,cnt=1;cin>>t;
	while(t--)
	{
		int n;cin>>n;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				cin>>mat[i][j];
			}
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				if(n&1)
				{
					if(j==(n+1)/2)
					{
						int temp=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]);
						dp[i][j]=max(dp[i][j],temp)+mat[i][j];
					}
					else if(j<(n+1)/2)
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];
					}
					else
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];
					}
				}
				else
				{
					if(j<=n/2)
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];
					}
					else
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];
					}
				}
			}
		}
		//cout<<endl;
		int ma=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				//cout<<dp[i][j]<<" ";
				ma=max(ma,dp[i][j]);
			}
			//cout<<endl;
		}
		cout<<"Case "<<cnt++<<": "<<ma<<endl;
	}
	return 0;
}

Just use set to store the elements and answer is the size of set.

    int n,x;cin>>n;
    set<int>s;
    for(int i=0;i<n;++i)
    {
    	cin>>x;
    	s.insert(x);
    }
    cout<<s.size()<<endl;

Two pointer technique-If apartment size is greater than x+k then upper pointer will increase or less than x-k then lower pointer will increase otherwise both the pointer increase along with counter. NB.Don't forget to sort both the arrays.

        cin>>n>>m>>k;
	V v(n),u(m);
	lp(i,n)cin>>v[i];
	lp(i,m)cin>>u[i];
	srt(v);srt(u);
	cnt=0;
	i=0,j=0;
	while(i<n and j<m)
	{
		if(v[i]-k>u[j])j++;
		else if(v[i]+k<u[j])i++;
		else
		{
			i++,j++,cnt++;
		}
	}
	cout<<cnt<<endl;
 

Two pointer technique-First sort the array. Then we have to minimize the number .So if the pointers value over flow the limit then we decrease the upper pointer. otherwise decrease the number.

        cin>>n>>m;
	V v(n);
	lp(i,n)cin>>v[i];
	cnt=n,sum=0,c=0;
	srt(v);
	i=0,j=n-1;
	while(i<j)
	{
		if(v[i]+v[j]<=m)cnt--,i++,j--;
		else j--;
	}
	cout<<cnt<<endl;

Here we need the lower bound of the multiset(as the values can be duplicate) each time and erase it from the set. If the iterator points to the end of set that means there is no value to satisfy the condition.

        cin>>n>>m;
	V v(n),u(m);
	lp(i,n)cin>>v[i];
	lp(i,m)cin>>u[i];
	multiset<int,greater<int>>s;
	lp(i,n)s.insert(v[i]);
	//joker(s)
	lp(i,m)
	{
		auto it=s.lower_bound(u[i]);
		if(it==s.end())cout<<-1<<endl;
		else
		{
			cout<<*it<<endl;
			s.erase(it);
		}
		//joker(s)
	} 

lets consider arrival time +1 and leaving time -1.So we use pair sorting to find the maximum amount of arrival times of the customers.

        cin>>n;
	VP vp;
	lp(i,n)
	{
		cin>>x>>y;
		vp.pb({x,1});
		vp.pb({y,-1});
	}
	ans=0,sum=0;
	srt(vp)
	for(auto i:vp)
	{
		sum+=i.second;
               ans=max(ans,sum);
        }
       cout<<ans<<endl;

Here,we sort the pair according to the ending time.Now if there is no overlaps then we increase the count.Always temp value updated to pair second element.

        cin>>n;
	VP vp;
	lp(i,n)
	{
		cin>>x>>y;
		vp.pb({x,y});
	}
	sort(vp.begin(),vp.end(),as_second);
	i=0,ans=0,temp=0;
	while(i<n)
	{
		if(temp<=vp[i].first)
		{
			temp=vp[i].second;
			i++;
			ans++;
		}
		else i++;
	}
	cout<<ans<<endl;
 

Basic two pointer technique-If the sum is greater than x the upper pointer should be decreased or if less than x then lower pointer should be increased. Here we need to use pair to store the indices of the value.

        cin>>n>>m;
	VP v(n);
	lp(i,n)
	{
		cin>>x;
		v[i]={x,i};
	}
	srt(v)
	i=0,j=n-1;
	while(i<j)
	{
		if(v[i].first+v[j].first>m)
		{
			j--;
		}
		else if(v[i].first+v[j].first<m)
		{
			i++;
		}
		else
		{
			cout<<v[i].second+1<<" "<<v[j].second+1<<endl;
			return;
		}
	}
	cout<<"IMPOSSIBLE"<<endl;
 

If the sum is increased then we add the value to sum otherwise just take the value. Print the maximum sum.

    ll n,sum=0,ma=-9e18;
    cin>>n;
    vector<ll>v(n);
    for(ll &i:v)
    {
    	cin>>i;
    	sum=max(sum+i,i);
    	ma=max(ma,sum);
   }
   cout<<ma<<endl;
 

First we have to sort the array. The total distance between the middle element of the array with the rest of the elements is the answer.

         int n;cin>>n;
         vector<ll>v(n);
         for(ll &i:v)
         {
    	    cin>>i;
	 }
	 sort(v.begin(),v.end());
	 ll mid=v[n/2],ans=0;
	 for(ll &i:v)
	 {
	    ans+=abs(i-mid);
	 }
	 cout<<ans<<endl;
 

Geeksforgeeks has a similar artical explaining the problem ,here.you have to use ordered map to get ac here.

 ll n;cin>>n;
 ll a[mx];
 for(ll i=0;i<n;++i)
 {
   cin>>a[i];
 }
 map<ll,ll>mp;
 ll ans=0;
 for(ll i=0,j=0;i<n;++i)
 {
    j=max(mp[a[i]],j);
    ans=max(ans,i-j+1);
    mp[a[i]]=i+1;
 }
 cout<<ans<<"\n";       
 

Here we use multiset to store the values and then everytime check if the upper bound of x is present or not in the set.If present then we erase from the set and insert to set.Finally size of set is the answer.

    int n,x;cin>>n;
    multiset<int>s;
    for(int i=0;i<n;++i)
    {
    	cin>>x;
    	auto it=s.upper_bound(x);
    	//cout<<*it<<endl;
    	if(it==s.end())s.insert(x);
    	else
    	{
    		s.erase(it);
    		s.insert(x);
	}
    }
    cout<<s.size()<<endl;

Here we first insert 0 and length of the street x in a set.After we put each traffic light we calculate the difference between both from the 0 and from x as well.And we need to print the maximum value of both this term. As last value of set contains the larger value so it's the answer.

    cin >> x >> n;
    set<int> s;
    s.insert(0);
    s.insert(x);
    multiset<int> ms;
    ms.insert(x);
    while(n--)
    {
        cin >> a;
        auto it = s.lower_bound(a);
        auto it2 = it;
        --it2;
 		//debug2(*it,*it2)
        ms.erase(ms.find(*it - *it2));
        ms.insert(a - *it2);
        ms.insert(*it - a);
 		//joker(ms)
        //auto last = ms.end()[1];
        cout << *--ms.end() << " ";
        s.insert(a);
    }

Here we used multimap<pair<int,int>,int>mp to store the arrival and departure time along with their indices.We used min heap to check if the previous customer is left the hotel or not.If the customer hadn't left the hotel then we increase the count otherwise get the previous count.Everytime we pushed count to the vector.

    int n,cnt=0;cin>>n;
    multimap<pair<int,int>,int>mp;
    for(int i=0;i<n;++i)
    {
    	int x,y;cin>>x>>y;
    	mp.insert({{x,y},i});
	}
	vector<int>v(n);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	for(auto i=mp.begin();i!=mp.end();++i)
	{
		int a,b,c;
		tie(a,b)=i->first;
		if(pq.empty() or get<0>(pq.top())>=a)
		{
			c=++cnt;
		}
		else
		{
			c=get<1>(pq.top());
			pq.pop();
		}
		pq.push({b,c});
		v[i->second]=c;
	}
     cout<<cnt<<endl;
     for(auto i:v)cout<<i<<" "; 

Binary search :We check all the possible outcomes between 0 and 1e18 using binary search. Here the possible outcome can't cross 1e9 so we must take the minimum of sum and 1e9.Similar type of problem:get the container

ll n,m;
ll ar[mx];
bool check(ll p)
{
	ll sum=0;
	for(int i=0;i<n;++i)
	{
		sum+=min(p/ar[i],(ll)1e9);
	}
	return sum>=m;
}
 
        cin>>n>>m;
   	for(int i=0;i<n;++i)
   	{
   		cin>>ar[i];
	}
	ll low=0,hi=1e18;
	while(low<hi)
	{
		ll mid=low/2+hi/2;
		if(check(mid))
		{
			hi=mid;
		}
		else low=mid+1;
	}
	cout<<low<<endl;

First sort the pair in non decreasing order. Then each time get the difference between the second value with the summation of first value.

    ll n;
    cin>>n;
    vector<pair<ll,ll>>arr;
    for(ll i=0;i<n;i++)
    {
        ll x,y;
        cin>>x>>y;
        arr.push_back({x,y});
    }
    sort(arr.begin(),arr.end());
    ll sum=0;
    ll start=0;
    for(ll i=0;i<n;i++)
    {
        start+=arr[i].first;
        sum+=arr[i].second-start;
    }
    cout<<sum;

Here if max>(sum-max) then 2*max otherwise sum is the answer.

        ll n;cin>>n;
	ll sum=0,ma=INT_MIN;
	for(int i=0;i<n;++i)
	{
		ll x;cin>>x;
		sum+=x;
		ma=max(ma,x);
	}
	cout<<(ma>(sum-ma)?2*ma:sum)<<endl; 

Like the previous one here we can use similar approach to get the third value. If the sum of three value exceeds we decrease upper pointer value or if it subceeds then we increase lower pointer value.

       int n,x;cin>>n>>x;
    vector<int>a(n);
    vector<pair<int,int>>v(n);
    for(int i=0;i<n;++i)
    {
    	int xx;
    	cin>>xx;
    	a[i]=xx;
    	v[i]={xx,i+1};
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;++i)
	{
		int low=0,hi=n-1;
		while(low<hi)
		{
			if(v[low].second==i+1)low++;
			else if(v[hi].second==i+1)hi--;
			else if(v[low].first+v[hi].first+a[i]>x)hi--;
			else if(v[low].first+v[hi].first+a[i]<x)low++;
			else
			{
				cout<<v[low].second<<" "<<v[hi].second<<" "<<i+1<<endl;return 0;
			}
		}
	}
	cout<<"IMPOSSIBLE"<<endl;

Here we run two loops one starting i=0,another j=i+1.The other two values we check from j+1 to n-1.As the pair is already sorted the numbers must be lied between these numbers.

       int n,x;cin>>n>>x;
    vector<int>a(n);
    vector<pair<int,int>>v(n);
    for(int i=0;i<n;++i)
    {
    	ll xx;
    	cin>>xx;
    	a[i]=xx;
    	v[i]={xx,i};
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;++i)
	{
		for(int j=i+1;j<n;++j)
		{
			int low=j+1,hi=n-1;
			while(low<hi)
			{
				int p=v[i].first,q=v[j].first,r=v[low].first,s=v[hi].first;
				if(p+q+r+s==x)
				{
					cout<<v[i].second+1<<" "<<v[j].second+1<<" "<<v[low].second+1<<" "<<v[hi].second+1<<endl;return 0;
				}
				else if(p+q+r+s<x)low++;
				else hi--;
			}
		}
	}
	cout<<"IMPOSSIBLE\n";

Basic Amortized analysis technique. Better explanation is here in geeksforgeeks.

    int n;cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i)
    {
    	cin>>v[i];
	}
	stack<int>s;
	for(int i=0;i<n;++i)
	{	
		while(!s.empty() and v[s.top()]>=v[i])
		{
			s.pop();
		}
		if(s.empty())
		{
			cout<<0<<" ";
		}
		else
		{
			cout<<s.top()+1<<" ";
		}
		s.push(i);
	}

We can solve it using prefix sum like this.But if we consider negative values then here is another approach-Link(https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/) in geeks for geeks

    ll n,sum;cin>>n>>sum;
    vector<ll>v(n);
    for(int i=0;i<n;++i)
    	cin>>v[i];
    ll m=0,cnt=0;
    map<ll,ll>mp;
    for(int i=0;i<n;++i)
    {
    	m+=v[i];
    	if(m==sum)cnt++;
    	if(mp.count(m-sum))
    	{
    		cnt+=mp[m-sum];
		}
		mp[m]++;
	}
	cout<<cnt<<endl;

Similar to previous one.

    ll n,sum;cin>>n>>sum;
    vector<ll>v(n);
    for(int i=0;i<n;++i)
    	cin>>v[i];
    ll m=0,cnt=0;
    map<ll,ll>mp;
    for(int i=0;i<n;++i)
    {
    	m+=v[i];
    	if(m==sum)cnt++;
    	if(mp.count(m-sum))
    	{
    		cnt+=mp[m-sum];
		}
		mp[m]++;
	}
	cout<<cnt<<endl;

geeks for geeks has similar article explained the problem here

    ll n,sum=0;cin>>n;
    vector<ll>v(n),mod(n,0);
    for(ll i=0;i<n;++i)
    {
    	cin>>v[i];
    	sum+=v[i];
		mod[((sum%n)+n)%n]++;	
	}
	ll res=0;
	for(ll i=0;i<n;++i)
	{
		if(mod[i]>1)
		{
			res+=(mod[i]*(mod[i]-1)/2);
		}
	}
	res+=mod[0];
	cout<<res<<endl;

Simple binary search-Similar type of problem:get the container.

const ll mx = 2e5+5;
ll n,k,hi=0,low=9e18,cnt;
ll v[mx];
bool check(ll tot)
{
	ll temp=0,cnt=1;
	for(ll i=0;i<n;++i)
	{
		if(v[i]>tot)return false;
		if(v[i]+temp<=tot)temp+=v[i];
		else {
			temp=v[i];cnt++;
		}
	}
	
	return cnt<=k;
}

    cin>>n>>k;
    for(ll i=0;i<n;++i)
    {
    	cin>>v[i];
    	hi+=v[i];
    	if(v[i]<low)low=v[i];
	}
	ll ans=-1;
	while(low<=hi)
	{
		ll mid=(low+hi)/2;
		if(check(mid))
		{
			//cout<<ans<<endl;
			ans=mid;
			hi=mid-1;
		}
		else
		{
			low=mid+1;
		}
	}
	cout<<ans<<endl;

Basic sliding window technique-use queue to maintain the window size constant. To search from the window we have to use ordered multiset as it's searching is faster then other data structure to be exact O(log(n)) time.

        int n,m;cin>>n>>m;
   	int a[n];
   	for(int i=0;i<n;++i)
   	{
   		cin>>a[i];
	}
	ordered_multiset st;
	queue<int>q;
	for(int i=0;i<n;++i)
	{
		if(q.size()==m)
		{
			if(m&1)
			{
				cout<<*(st.find_by_order(m/2))<<" ";
			}
			else cout<<*(st.find_by_order(m/2-1))<<" ";
			int p=q.front();
			st.erase(st.find_by_order(st.order_of_key(p)));
			q.pop();
		}
		q.push(a[i]);
		st.insert(a[i]);
	}
	if(m&1)
	{
		cout<<*(st.find_by_order(m/2))<<" ";
	}
	else
	{
		cout<<*(st.find_by_order(m/2-1))<<" ";	
	}

In this problem,everytime we check for a window of k elements.

First we check for first k elements and store it's mid value in P(capital). Then with each iteration we erase the first value from window and add the next value from the array.

See,if the initial set is 2 3 4 after iteration it's 3 4 5.

After the iteration mid value is p(small).Now after the new value added to set the cost is abs(p-a[i+m]) and the previous cost is abs(P-a[i]).So the change of total cost d is simply the difference between these two.

Now when it's come to even value ,Like this one-

8 4
2 4 3 5 8 1 2 1

Here the previous window is 2 3 4 5 and after 1st iteration 3 4 8 5. P(capital)=3, p(small)=4; Unlike the odd k ,even k has two mid value. So either 1st mid value gives you the min cost or the 2nd mid value. If you notice then P(capital) is 1st mid value, p(small) is 2nd mid value. That's the reason we simply erase the extra value(it's either add to total cost or decreases).

        ll n,m;cin>>n>>m;
   	ll a[n];
   	for(int i=0;i<n;++i)
   	{
   		cin>>a[i];
	}
	ordered_multiset st;
	for(int i=0;i<m;++i)
	{
		st.insert(a[i]);
	}
	ll P=*st.find_by_order((m+1)/2-1);
	ll d=0;
	for(int i=0;i<m;++i)d+=abs(a[i]-P);
	cout<<d<<" ";
	for(int i=0;i<n-m;++i)
	{
		st.erase(st.find_by_order(st.order_of_key(a[i])));
		st.insert(a[i+m]);
		ll p=*st.find_by_order((m+1)/2-1);
		d+=abs(p-a[i+m])-abs(P-a[i]);
		if(!(m&1))d-=p-P;
		P=p;
		cout<<d<<" ";
	}

We always check the lower bound of the starting time.If the starting time is already in the set or less then the previous one then we increase the count and push the ending value to the set.

        int n,k;cin>>n>>k;
   	vector<pair<int,int>>v(n);
   	for(int i=0;i<n;++i)
   	{
   		int x,y;cin>>x>>y;
   		v[i]={y,x};
	}
	sort(v.begin(),v.end());
	multiset<int,greater<int>>s;
	s.insert(v[0].first);
	for(int i=0;i<k-1;++i)s.insert(0);
	int cnt=1;
	for(int i=1;i<n;++i)
	{
		auto it=s.lower_bound(v[i].second);
		if((*it)==s.size())
		{
			if((*it)<=v[i].second and s.find(v[i].second)!=s.end())
			{
				s.erase(it);
				s.insert(v[i].first);
				cnt++;
			}
		}
		else
		{
			s.erase(it);
			s.insert(v[i].first);
			cnt++;
		}
	}
	cout<<cnt<<endl;

geeks for geeks has similar article given here.

        ll n,a,b;cin>>n>>a>>b;
   	ll ar[n],presum[n];
   	for(int i=0;i<n;++i)
   	{
   		cin>>ar[i];
	}
	presum[0]=ar[0];
	for(int i=1;i<n;++i)
	{
		presum[i]=presum[i-1]+ar[i];
	}
	multiset<ll>s;
	s.insert(0);
	ll ans=-9e18;
	ans=max(ans,presum[a-1]);
	int flag=0;
	for(int i=a;i<n;++i)
	{
		if(i-b>=0)
		{
			if(!flag)
			{
				auto it=s.find(0);
				s.erase(it);
				flag=1;
			}
		}
		if(i-a>=0)
		{
			s.insert(presum[i-a]);
		}
		ans=max(ans,presum[i]-*s.begin());
		if(i-b>=0)
		{
			auto it=s.find(presum[i-b]);
			s.erase(it);
		}
	}
	cout<<ans<<endl;