PROBLEM LINK:Author: Piyush Kumar DIFFICULTY:SIMPLEEASY PREREQUISITES:Binary search, Sorting, Hash table PROBLEM:You are given an array of heights of children h[1..n] and an integer F. If a child drops a ball from its height h[i], then it bounces back, to the height h[i] / F, falls down and bounces back again to the height h[i] / F^2 and so on. The task is to find the number of pair of students such that if the taller child drops a ball, it bounces back to the height of the second child after 0 or more bounces. If two children have equal height, then the pair is valid, because the ball reaches the height of the second child after 0 bounces and for each such pair you count it only once. In math words, the task is to find the number of pair of indices i, j such that h[i] < h[j] or h[i] = h[j] and i < j for which there exists a nonnegative integer k such that h[j] / F^k = h[i]. QUICK EXPLANATION:There are at least two approaches differ by the underlying data structure. You can sort array h in ascending order and then iterate over the array. For each element h[i] you divide it by F^0, F^1, ... while F^k <= h[i] and for each of these divisions if its result is an integer, you use binary search to determine the number elements in h equal to the result. The second approach uses a hash table t. Where t[i] is the number of elements in the array h with value i. Then you can use a similar approach to iterate over all elements and compute the result. You can read more about hash tables here EXPLANATION:You sort the array h in the ascending order at first. Then you iterate over elements of h. For each h[i], you compute h[i] / F^0, h[i] / F^1, ... while F^k <= h[i] and for each of these values, if it is an integer d, you use binary search to determine the number of elements in h[1..i1] with value d and add it to the result. This method guarantees that you count a pair i, j only once if h[i] = h[j]. In c++ there is a handy method which can be used for computing the number of elements in h[1..i1] equal to value d assuming that h is a vector: std::equal_range(h.begin(), h.begin() + i, d) You can use also two binary searches calling upper_bound and lower_bound respectively. Both these methods work in O(log n) time if the array is sorted. Time complexity:O(n (log n)^2) because sorting takes O(n log n) and for each of n times in a loop we use binary search at most O(log n) times  once for each valid F^k. Alternative Solution:For an approach which uses a hash table and described in quick explanation please look at the tester's code. For a partial credit, you can iterate over all pairs (i, j) and check if h[j] / F^k = h[i] for some k >=0 , where h[j] >= h[i]. This method works in O(n^2 * log 10^9) because there are O(n^2) pairs and for each pair we have to check at most log 10^9 values of k, because if h[i] = 10^9 and F = 2, then F^(log 10^9) = h[i]. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 26 Oct '14, 14:24

I used following approach which worked for me... firstly divide each h[i] with f till it is divisible... then sort resulting h array... count each pair of h[i] with same value...
answered 26 Oct '14, 14:56
pretty crisp (Y)
(26 Oct '14, 15:45)
Can you explain the logic behind your code?
(26 Oct '14, 16:14)
great man..This logic will work in O(n*log(n)) instead..
(26 Oct '14, 17:26)
@grayhathacker I was also approaching for same but ran out of time, good logic :)
(27 Oct '14, 09:25)
1
@ironmandhruv the logic is that if the division series have common parts, then they will result in the same smallest value. The smaller series is contained by the greater one. There is no reason to continue the division after the fractions appear as those will stay there and no integer result is possible any more. After sorting, the number of equal neighbors is counted that results the number of pairings. This algorithm naturally filters out the duplications in pairs too. Fabulous solution.
(02 Nov '14, 20:41)
can you explain in detail
(02 Nov '14, 22:38)
Your solution is even the better than the editorialist's.
(10 Mar '16, 21:36)
showing 5 of 7
show all

http://www.codechef.com/viewsolution/5220938 Can someone tell what is wrong in this solution? Gave AC for 2 test cases only. answered 26 Oct '14, 15:29

The following code gives SIGFPE on one test case, however gets AC when i change all int to long long(so its not divide by zero error for sure). The constraints seem ok for int ..are they not? http://www.codechef.com/viewsolution/5220261 (SIGFPE) http://www.codechef.com/viewsolution/5220513 (AC) answered 27 Oct '14, 13:40

Where am i Going Wrong Here
answered 22 Dec '14, 10:25
@grayhathacker I Tried to IMplement Your Logic , Maybe You can figure where i am going wrong
(22 Dec '14, 10:31)
I Figured It , This Line Had To Be Changed .... FROM ans+=(bounds.secondbounds.first); TO ans+=((bounds.secondbounds.first)*((bounds.secondbounds.first)1))/2LL;// C(N,2)
(22 Dec '14, 10:49)

in the first approach explained in the editorial how it will give the correct answer if all the elements of the vector h are same...!!!.. answered 29 Jun '17, 09:22

@siddharth067 I didn't understand why u did this ans+=((bounds.secondbounds.first)*((bounds.secondbounds.first)1))/2LL;// C(N,2) answered 29 Jun '17, 09:32

Thanks a lot for telling us about std::equal_range() :)
@wittyceaser great that you like it :) it simplify thinks often. If you want to read more from me, you can visit my blog here: chasethered.com