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;
}