PHYSICS - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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.

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…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:

11 Likes
2

can someone help me to find error in this


[1] !Thank you.


  [1]: http://www.codechef.com/viewsolution/5222654
3

Great editorial … :slight_smile:

2 Likes
4

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<n;i++)
	{
		cin>>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<n;i++)
	{
		if(h[i]!=a)
		{
			a=h[i];
			p=0;
		}
		ans+=p;
		p++;
	}
	cout<<ans<<"\n";

link: CodeChef: Practical coding for everyone

14 Likes
5

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

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

6

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

7

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 :slight_smile:

8

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?

CodeChef: Practical coding for everyone (SIGFPE)
CodeChef: Practical coding for everyone (AC)

9

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[i]=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;
    }
}
10

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

11

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

12

pretty crisp (Y)

13

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

1 Like
14

Can you explain the logic behind your code?

15

Yes, of course. The editorial didn’t state O(log(n)) steps, it states log(n) steps :wink:

16

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

1 Like
17

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

18

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

19

@grayhathacker I was also approaching for same but ran out of time, good logic :slight_smile:

20

@wittyceaser great that you like it :slight_smile: it simplify thinks often. If you want to read more from me, you can visit my blog here: chasethered.com