NBC003- Editorial

Practice
NOOB_CODING_2k20 Contest

Author: unknown_9876
Tester: sourav472
Editorialist: sourav472

DIFFICULTY:

EASY

PREREQUISITES:

Map & Hashing.

EXPLANATION:

The idea is to make the pair in such a way that the sum of the cooking skills of the cooks
is equal to K.
It can be implemented by any of the two methods either by using hashing or by using Two Pointer
method.
In the Hashing approach , select the ith cook and check whether there exist a cook with cooking skill
K-A[i].Unordered maps reduce the searching complexity to O(1) and hence are used.

Another way is to sort the cooking skill array and use two pointers and set one of them to the begining and
other to the end of the array.
If the sum of both of them is equal to K increment count pointer by one, increment starting pointer by one and decrement the ending pointer by one.
If the sum is less than K we need to increase the sum so increment the starting pointer by one.
If the sum is greater than K we need to decrease the sum so decrement the ending pointer by one.

Both the approaches are demonstrated below.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t,n,m,i,sum;cin>>t;
    while(t--)
    {
        cin>>n>>sum;
        int a[n];
        unordered_map<int,int> hash;
        for(i=0;i<n;i++)
        {
            cin>>a[i];
            hash[a[i]]++;
        }
        int ans = 0;
        for(i=0;i<n;i++)
        {
        	if(hash[a[i]]==0)
        	continue;
            m = sum - a[i];
            hash[a[i]]--;
            if(hash[m]>0)
            {
                ans++;
                hash[m]--;
            }
            else
                hash[a[i]]++;
        }
        cout<<ans<<endl;
    }
    return 0;
}    
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define dfor(i,a,b) for(ll i=(a);i<(b);i++)
#define rfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define pii pair<ll,ll>
#define vi vector<ll>
#define vpii vector<pii>
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define fast ios_base::sync_with_stdio( false );cin.tie(NULL);
const ll mod = (ll)(1e9+7); 
using namespace std; 
int main() {
    fast
    ll t;
    cin>>t;
	while(t--)
	{
	    ll n,k;
	    cin>>n>>k;
	    ll a[n],i,j,count=0;
	    for(i=0;i<n;i++)
	     cin>>a[i];
	    sort(a,a+n);
	    for(i=0,j=n-1;i<n;)
	    {
	        if(i>=j)
	        {
	            break;
	        }
	        if(a[i]+a[j]==k)
	        {
	            count++;
	            i++;
	            j--;
	        }
	        else if(a[i]+a[j]>k)
	        {
	            j--;
	        }
	        else
	        {
	            i++;
	        }
	    }
	    cout<<count<<"\n";
	}
 return 0;
} 
1 Like

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
ll n,k,count=0;
cin>>n>>k;
ll a[n];
map<int,int> m;
for(ll i=0;i<n;i++){
cin>>a[i];m[a[i]]++;
}
for(ll i=0;i<n;i++){
if(k==2a[i] && m[a[i]]>1){
count+=2
(m[a[i]]/2);
m[a[i]]=0;
}
else count+=m[k-a[i]];
}cout<<count/2<<endl;
}
int main(){
ll t;
cin>>t;
while(t–){
solve();
}
return 0;
}//This is my code but it is showing WA. can anyone help here

Hope this explanation and code helps to understand better

We are going with the greedy approach to solve this problem firstly we sort the given elements in ascending order then we apply 2 pointer technique later to find total number of pairs such that the sum is equal to K and at last we print the count of such pairs

My Code : CodeChef: Practical coding for everyone