You are not logged in. Please login at www.codechef.com to post your questions!

×

PHYSICS - Editorial

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:

This question is marked "community wiki".

asked 26 Oct '14, 14:24

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 01 Jul '17, 08:13

1

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

(26 Oct '14, 16:20) wittyceaser2★

@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) pkacprzak ♦♦5★

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

link

answered 26 Oct '14, 14:56

grayhathacker's gravatar image

5★grayhathacker
3374514
accept rate: 0%

pretty crisp (Y)

(26 Oct '14, 15:45) sidgupta2342★

Can you explain the logic behind your code?

(26 Oct '14, 16:14) ironmandhruv4★

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

(26 Oct '14, 17:26) devenderissar4★

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

(27 Oct '14, 09:25) abcdexter242★
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) allprog2★

can you explain in detail

(02 Nov '14, 22:38) nil962★

Your solution is even the better than the editorialist's.

(10 Mar '16, 21:36) shubham992★
showing 5 of 7 show all

Great editorial .. :)

link

answered 26 Oct '14, 14:34

dextrous's gravatar image

5★dextrous
1582210
accept rate: 0%

can someone help me to find error in this code !Thank you.

link

answered 26 Oct '14, 14:31

marshalmathers's gravatar image

3★marshalmathers
61
accept rate: 0%

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

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

link

answered 26 Oct '14, 15:29

roxtar123's gravatar image

2★roxtar123
262
accept rate: 0%

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

link

answered 26 Oct '14, 15:29

sidgupta234's gravatar image

2★sidgupta234
2372717
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) devenderissar4★

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

link

answered 26 Oct '14, 16:12

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

edited 26 Oct '14, 16:17

1

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

(26 Oct '14, 16:13) neo1tech9_76★

Yes, of course. The editorial didn't state O(log(n)) steps, it states log(n) steps ;)

(26 Oct '14, 16:17) wittyceaser2★

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)

link

answered 27 Oct '14, 13:40

fauzdar65's gravatar image

2★fauzdar65
29114
accept rate: 21%

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

answered 22 Dec '14, 10:25

siddharths067's gravatar image

1★siddharths067
8027
accept rate: 4%

@grayhathacker I Tried to IMplement Your Logic , Maybe You can figure where i am going wrong

(22 Dec '14, 10:31) siddharths0671★

I Figured It , This Line Had To Be Changed .... FROM ans+=(bounds.second-bounds.first); TO

ans+=((bounds.second-bounds.first)*((bounds.second-bounds.first)-1))/2LL;// C(N,2)

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

(22 Dec '14, 10:49) siddharths0671★

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

link

answered 29 Jun '17, 09:22

himanshu98's gravatar image

3★himanshu98
271
accept rate: 0%

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

link

answered 29 Jun '17, 09:32

himanshu98's gravatar image

3★himanshu98
271
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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