This is the problem link
An O(n^2) solution gave me TLE on test 10. I came across one of the solutions below.
main() {
int n,i,f,s; cin>>n; map<int,int> mp; pair<int , int> a[n]; for(i=0;i<n;i++) { cin>>f>>s; mp[f]++; a[i]={f,s}; } int m=n-1; for(i=0;i<n;i++) { a[i].first=m+mp[a[i].second]; a[i].second=m-mp[a[i].second]; cout<<a[i].first<<" "<<a[i].second<<endl; }
}
I don't understand how the following two lines work.
a[i].first=m+mp[a[i].second];
a[i].second=m-mp[a[i].second];
Each team plays n-1 home and n-1 away games . But what is purpose of mp[a[i].second]? Please help.
mp[i]
denotes the number of teams which have colori
as their home kit. Then,mp[a[i].second]
is the number of teams which have home kit being the same color as your away kit, or in other words, the number of games where you would normally play your away kit but have to play your home kit instead.Thanks Tzak. I got your point :)