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:

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

1 Like
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: http://www.codechef.com/viewsolution/5225456

13 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

pretty crisp (Y)

8

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:

9

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

1 Like
10

Can you explain the logic behind your code?

11

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

12

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

1 Like
13

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

14

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

15

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

16

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)

17

@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

18

@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.

1 Like
19

can you explain in detail

20

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;
    }
}