 # PHYSICS - Editorial

### PROBLEM LINK:

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*, then it bounces back, to the height h* / F, falls down and bounces back again to the height h* / 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* < h[j] or h* = h[j] and i < j for which there exists a non-negative integer k such that h[j] / F^k = h*.

### 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* you divide it by F^0, F^1, … while F^k <= h* 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* 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*, you compute h* / F^0, h* / F^1, … while F^k <= h* 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* = 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* for some k >=0 , where h[j] >= h*. 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* = 10^9 and F = 2, then F^(log 10^9) = h*.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

### RELATED PROBLEMS:

10 Likes

can someone help me to find error in this

``````
 !Thank you.

: http://www.codechef.com/viewsolution/5222654``````

Great editorial … 2 Likes

I used following approach which worked for me…

firstly divide each h* with f till it is divisible…

then sort resulting h array…

count each pair of h* with same value…

``````    cin>>n>>f;
for(i=0;i<n;i++)
{
cin>>a;
while(a%f==0)
a/=f;
h*=a;
}
sort(h,h+n);
a=h; p=1; ans=0;
for(i=1;i<n;i++)
{
if(h*!=a)
{
a=h*;
p=0;
}
ans+=p;
p++;
}
cout<<ans<<"
``````

";

14 Likes

http://www.codechef.com/viewsolution/5220938

Can someone tell what is wrong in this solution? Gave AC for 2 test cases only.

how come the time complexity comes to be O(n (log n)^2)? When we are doing sorting and searching in different loops.

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 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?

Where am i Going Wrong Here

``````    #include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
using namespace std;
typedef long long int ll;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll f, n,a;
cin>>n>>f;
vector<ll>h(n);
for(ll i=0;i<n;i++)
{
cin>>a;
while(a%f==0)
{
a/=f;
}
h*=a;
}
sort(h.begin(),h.end());
ll ans=0;
vector<ll>::iterator i=h.begin();
pair<vector<ll>::iterator,vector<ll>::iterator> bounds;
while(i<h.end())
{
bounds = equal_range(h.begin(),h.end(),*i);
ans+=(bounds.second-bounds.first);
i=bounds.second;
}
cout<<ans<<endl;
}
}``````

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…!!!..

@siddharth067 I didn’t understand why u did this ans+=((bounds.second-bounds.first)*((bounds.second-bounds.first)-1))/2LL;// C(N,2)

pretty crisp (Y)

O(2*log(n) + 1) = O(log(n))

1 Like

Can you explain the logic behind your code?

Yes, of course. The editorial didn’t state O(log(n)) steps, it states log(n) steps Thanks a lot for telling us about std::equal_range() 1 Like

great man…This logic will work in O(n*log(n)) instead…

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

@grayhathacker I was also approaching for same but ran out of time, good logic @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