imstark007's blog

By imstark007, history, 4 years ago, In English

can anyone give idea , how to solve question 4 in order of time complexity N , atcoder beginner contest 159. Link: https://atcoder.jp/contests/abc159/tasks/abc159_d

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

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

First take a map, iterate through array once and calculate number of balls for each number i.e. m[a[i]]++;

Now iterate through map and calculate sum of number of ways of choosing 2 balls for each number for(auto i:m) total_count+=((i.second)(i.second-1))/2

Now all you need to do is to go through the array one more time and print total_count-m[a[i]]*(m[a[i]]-1)/2+(m[a[i]]-1)*(m[a[i]]-2)/2 for each element.

Idea is to first subtract number of ways of choosing two balls from m[a[i]] balls and then add number of ways of choosing two balls from m[a[i]]-1 balls.

code link