Sherlock and Pairs
All topics
Dictionary
A dictionary (map in c++) is a data structure used to implement an associative array, a structure that can map keys to values.
In most programming languages we have an in-built dictionary container that can take a key in the form of int, char, string, etc. and the value can be any data type of your choice.
Example in C++ STL:
map <type, type> arr;
Here, type can be anything (int, char, string, etc. even vector<int>).
Storing values is as easy as equating arr["key"] = value;
Counting
In combinatorics there are two types of counting problems.
For example, in how many ways can balls of different colors be arranged ? Let us consider 3 balls of colors red , blue and green respectively.
Possible different arrangements of 3 balls are :
- RGB
- RBG
- BRG
- BGR
- GBR
- GRB
Total count is 6 and it is given by . Or for balls it's .
Counting number of selections (Combinations)
Let us count the number of ways of selecting items out of distinguishable items :
Counting number of arrangements (Permutations)
Let us count the number of ways of selecting items out of distinguishable items and then arranging them in some order.:
Methods for calculating :
int nCr(int n,int r){
int res = 1 ;
r = min(r,n-r) ; // nCr = nC(n-r)
for(int i=r;i>=1;i--){
res = res * n ;
res /= i ;
n -- ;
}
return res ;
}
// this code works properly for small size input
we can also use following recurrence to build up the dynamic programming for repeated queries.