TO FIND NEAREST FRACTION

general
,
1

problem (http://codeforces.com/problemset/problem/281/B) how to approach this problem …is there any article or concept which needs to be covered to solve this kind of problem(if it is please suggest )…i am stuck with this since 2 days …actually i have a logic but that is not efficient enough so getting TLE

1 Like
2

So, here is the approach:

Given that 1<=b<=n and a>=0, you have to find a pair a,b such that abs(x/y-a/b) is minimum.

1.Declare a variable min = 100000000;

2.Loop from i=1 to i<=n;

3.Do binary search for number, where low = 0 and high = 100001 and made a check for mid/i < z;

4.After binary search check which one is minimum (low/i-z) or (high/i-z), save it accordingly.

5.Now check for Minimum b/w saved number and min, change min accordingly.

Here is the heart of the problem:

for(int i = 1;i <= n;i++)
        {
            ll l = 0;
            ll r = 100001;
            ll mid;
            ll a;
            int b;
            double k;
            while(r - l > 1)
            {
                mid = (r + l) / 2;
                if((double)mid / i < z)l = mid;
                else r = mid;
            }
            if(fabs((double)l / i - z) <= fabs((double)r / i - z))
            {
                k = fabs((double)l / i - z);
                a = l;
                b = i;
            }
            else
            {
                k = fabs((double)r / i - z);
                a = r;
                b = i;
            }
            if(k < Min)
            {
                Min = k;
                flag1 = a;
                flag2 = b;
            }
        }

Happy coding!

2 Likes
3

I was bounding the search b/w 0 and 100001, according to the max. limit of constraints.

4

thanx man!! for the solution and the last problem you answered that was really helpful(union find ds)…