×

# PHYSICS - Editorial

Author: Piyush Kumar
Tester: Minako Kojima
Editorialist: Pawel Kacprzak

SIMPLE-EASY

# 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 non-negative 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.

# 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..i-1] 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..i-1] 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.
Tester's solution can be found here.

# RELATED PROBLEMS:

This question is marked "community wiki".

75485097
accept rate: 12%

1

Thanks a lot for telling us about std::equal_range() :)

(26 Oct '14, 16:20)

@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

(29 Oct '14, 16:52)

 14 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...  cin>>n>>f; for(i=0;i>a; while(a%f==0) a/=f; h[i]=a; } sort(h,h+n); a=h[0]; p=1; ans=0; for(i=1;i
 2 Great editorial .. :) answered 26 Oct '14, 14:34 5★dextrous 158●2●2●10 accept rate: 0%
 0 can someone help me to find error in this code !Thank you. answered 26 Oct '14, 14:31 6●1 accept rate: 0%
 0 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 26●2 accept rate: 0%
 0 how come the time complexity comes to be O(n (log n)^2)? When we are doing sorting and searching in different loops. answered 26 Oct '14, 15:29 237●2●7●17 accept rate: 7% one log(n) factor comes from binary search and second log(n) comes since we are doing binary search for each k where F^k<=height (26 Oct '14, 17:32)
 0 Just a minor thing I would like to point out: std::equal_range() takes 2*log(n)+1 element comparisons in the average case and not exactly log(n) comparisons. Doesn't make much difference here, but I am mentioning this for an accurate analysis that's it :) answered 26 Oct '14, 16:12 3.4k●19●43●77 accept rate: 16% 1 O(2*log(n) + 1) = O(log(n)) (26 Oct '14, 16:13) Yes, of course. The editorial didn't state O(log(n)) steps, it states log(n) steps ;) (26 Oct '14, 16:17)
 0 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? answered 27 Oct '14, 13:40 291●1●4 accept rate: 21%
 0 Where am i Going Wrong Here  #include #include #include #include using namespace std; typedef long long int ll; int main() { ll t; cin>>t; while(t--) { ll f, n,a; cin>>n>>f; vectorh(n); for(ll i=0;i>a; while(a%f==0) { a/=f; } h[i]=a; } sort(h.begin(),h.end()); ll ans=0; vector::iterator i=h.begin(); pair::iterator,vector::iterator> bounds; while(i
 0 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 27●1 accept rate: 0%
 0 @siddharth067 I didn't understand why u did this ans+=((bounds.second-bounds.first)*((bounds.second-bounds.first)-1))/2LL;// C(N,2) answered 29 Jun '17, 09:32 27●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,056
×801
×67
×48
×47

question asked: 26 Oct '14, 14:24

question was seen: 4,263 times

last updated: 01 Jul '17, 08:13