PHYSICS - Editorial

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

21

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

can you explain in detail