PROBLEM LINK:
Contest: Hey Newbees,Here is Some Honey ! [Round-2]
Author & Editorialist: Samia Rahman
Co- author & Tester: Arefin Labib
Tester: Sanjida Akter , Redowan Ibrahim
DIFFICULTY:
SIMPLE.
PREREQUISITES:
Sorting, Data structures.
PROBLEM:
Some team’s have participated in a contest and within half an hour it is ensured that all the teams have submitted only once and they got at least 1 point.So in the submission list the all the team’s names already exists.
After half an hour, team’s names became random.
Now in the submission list abc, acb, bac, bca, cab, cba refers to the same team.And it is ensured that frequency of each of the character’s in a team’s name will not match with another team.
That means two teams named xoxo and oxox is not possible. Because both of them have the same frequency of each of the characters (two ‘o’ and two ‘x’).
Now print the teams name according to their point in decreasing order.If some of them have equal points.Print the lexicographically smaller team’s name first.
EXPLANATION:
Suppose only 2 teams have registered (R=2) for competing. Team ABC and team XYZ
Within half an hour their submission look like this-
After half an hour teacher Sungjae mistakenly pressed a button.Now in the submission list team’s name become random.
Now in the submission list submissions of
ACB , CAB , CBA , BAC , BCA are basically the submissions of registered team ABC.
And the submissions of YXZ , ZXY , ZYX , XZY , YZX are the submissions of registered team XYZ.
Now total submission is N.
We need to store the register team names (store[i]=t[i] ,iteration from 1 to R) .
Then we’ll sort all the team’s name. ACB,CAB,CBA,BAC,BCA will become ABC.
Add the team’s point which is 1+5+2+1+7+2=18 points. (You can use std::map ) .
Now ABC has 18 points similarly we can get team XYZ ‘s point which is 23.
Now we will make a pair with store[i], mp [ sort ( store [i] ) ] ( mp is a map) .
Then after sorting the pair we will print it.
TIME COMPLEXITY:
T* N*(n log n) [ T=test case , N=N , n=ti ]
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define FastRead \
ios_base::sync_with_stdio(false); \
cin.tie(0);
#define ll long long
#define endl "\n"
#define pi acos(-1)
using namespace std;
bool cmp(const pair<string,ll> &a,
const pair<string,ll> &b)
{
if(a.second!=b.second)
return (a.second > b.second);
else
return (a.first < b.first);
}
int main()
{
FastRead
ll test_case,j;
cin>>test_case;
for(j=0; j<test_case; j++)
{
ll n,r,point,i;
string team,store,b;
cin>>n>>r;
map<string,ll>mp;
set<string>s;
set<string>::iterator it;
vector<pair<string,ll> >v;
for(i=0; i<n; i++)
{
cin>>team>>point;
store=team; //store the unchanged team names
sort(team.begin(),team.end()); //now sort each of the team names
if(mp[team]==0) //if the team name appeared for the first time stored it's unchanged form in a set
s.insert(store); //now in the set all team names are saved unchanged
mp[team]=mp[team]+point; //now sum up each team's points
}
for(it=s.begin(); it!=s.end(); it++)
{
b=*it; //*it=team's name I've previously stored in the set
sort(b.begin(),b.end()); //sorted *it
v.push_back(make_pair(*it,mp[b]));//so now mp[b]=mp[team] from above.Then I've made a pair
}
sort(v.begin(),v.end(),cmp); //sorted the pair.
for(i=0; i<v.size(); i++)
{
cout<<v[i].first<<" "<<v[i].second<<endl;//finally printed it
}
}
return 0;
}
Tester's Solution (Python)
for _ in range(int(input())):
n,r=map(int,input().split())
d={}
mp={}
li=[]
l=[]
for i in range(r ):
p=input()
ti,pii=p.split()
pi=int(pii)
li.append(ti)
d[ti]=pi
v = sorted(ti)
v1="".join(v)
l.append(v1)
mp[v1]=pi
for i in range(n-r):
p=input()
ti,pii=p.split()
pi=int(pii)
v=sorted(ti)
v1="".join(v)
mp[v1]=mp[v1]+pi
for i in range(r):
d[li[i]]=mp[l[i]]
for x in sorted(d.items(),key=lambda x:(-x[1],x[0])):
print (x[0],x[1])
Tester's Solution in C++
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool sortbysec(const pair<string,ll> &a,
const pair<string,ll> &b)
{
if(a.second!=b.second)
return (a.second > b.second);
else
return (a.first < b.first);
}
int main()
{
ll tc,n,r,i,p,x;
scanf("%lld",&tc);
while(tc--)
{
scanf("%lld%lld",&n,&r);
string s[n],s1[n],s2;
map<string,ll>mp,mp1;
for(i=0; i<r; i++)
{
cin>> s[i] >> p;
s1[i]=s[i];
sort(s[i].begin(),s[i].end());
mp[s[i]]+=p;
}
for(i=0; i<n-r; i++)
{
cin>> s2 >> p;
sort(s2.begin(),s2.end());
mp[s2]+=p;
}
for(i=0; i<r; i++)
{
mp1[s1[i]]=mp[s[i]];
}
vector<pair<string,ll> >v(mp1.begin(),mp1.end());
sort(v.begin(),v.end(),sortbysec);
for(i=0; i<v.size(); i++)
{
cout << v[i].first <<" " << v[i].second <<"\n";
}
}
return 0;
}