#Problem link:
[Practice] CINVIT02 Problem - CodeChef
[CodeInvicta] CodeChef: Practical coding for everyone
Author: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef
Editorialist: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef
DIFFICULTY: Easy
# PREREQUISITES: Math
#Problem :
You are given N pair of numbers where the first number can be an integer and second number is 0 or 1. So you need to count the occurence of the various pairs finally on the basis of how many times a pair occurred its value is added to the total sum which is our answer.
Quick Application:
We can use the concept of container within container to take the count.Along with another map or set to keep note of numbers and finally iterate over our second map and take the count in our first map.
Explanation:
So here we can use a pair within a map to keep the count of our various pairs the first value of map being the pair (the first value of which being the number and the second value being 0 or 1) the second value of map keeps the count . At the same time we can take a set or a map to keep note of what numbers are there in our code. Having taken the count and the total numbers available.
We iterate over our second map and check the count of each pair 0 and 1 available for that particular number if count of X,1 is <= X,0 we take sum+=count of X,1 * X.
Else we take sum-=count of X,0 *x. Note you should initialize the sum to 0 initially.
Finally the sum is our answer.
#Solutions:
[Setter and Editorialist’s Solution]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mod 1e9+7
#define all(x) x.begin(),x.end()
void solve() {
int n,sum=0;
map <pair<int,int>,int> m;
map <int,int> m1;
cin>>n;
for(int i=0;i<n;i++)
{
int s,x;
cin>>s>>x;
m1[s]=0;
m[{s,x}]++;
}
map <int,int> :: iterator it;
for(it=m1.begin();it!=m1.end();it++)
{ int y;
y=it->first;
if(m[{y,0}]<=m[{y,1}])
sum+=ym[{y,1}];
else
sum-=ym[{y,0}];
}
cout<<sum<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
solve();
}