KRYP4 - Editorial

[Contest][1]
[Practice][2]

Author: [Shivam Garg][3]
Tester: [Shiv Dhingra][4]

DIFFICULTY

CAKEWALK

PREREQUISITES

Basic Maths

PROBLEM

Given a list of integers, the aim is to find out the number of ways to select two integers having the same value.

EXPLANATION

For a given value, let the number of integers be X.
The number of ways to select two of them is Y= {X\choose 2}.
The answer is the summation of this Y for all distinct values present in the list provided.
This can be done by making use of a map to keep track of frequencies of all the distinct values.

The complexity of accessing/inserting elements in the map is O (Log (N)).
Hence the total complexity turns out to be O (N \hspace{1 mm}Log (N)).

SOLUTION

Setter’s Solution -


[5]


  [1]: https://www.codechef.com/CODR2018/problems/KRYP4
  [2]: https://www.codechef.com/problems/KRYP4
  [3]: http://codechef.com/users/shivamg_isc
  [4]: http://codechef.com/users/lucifer2709
  [5]: https://www.codechef.com/viewsolution/17468659