Akash_Roy's blog

By Akash_Roy, history, 4 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

mp[i] denotes the number of teams which have color i 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.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks Tzak. I got your point :)