Akash_Roy's blog

By Akash_Roy, history, 4 years ago, In English

This is the problem link

This is the editorial link

We select members for first round dance. Then members of second round dance get automatically selected . Hence the factor nC(n/2). Then we arrange both the round dance. This leads to nC(n/2)*(n-1)!*(n-1)! {Circular permutation}. After this why are we dividing the answer only by 2? I feel we should divide final answer by 4 since there are two round dances. Since clockwise and anticlockwise arrangement does not matter, the final answer should be [nC(n/2)*(n-1)!*(n-1)!]/4. Why is it [nC(n/2)*(n-1)!*(n-1)!]/2 ?

Please help.

Sorry for my poor number formatting.

Full text and comments »

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

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.

Full text and comments »

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