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

×

TO FIND NEAREST FRACTION

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

asked 26 Jun '17, 13:20

popo_popo333's gravatar image

3★popo_popo333
154
accept rate: 0%


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!

link

answered 26 Jun '17, 16:14

ayushagg31's gravatar image

1★ayushagg31
2417
accept rate: 9%

edited 26 Jun '17, 16:15

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

(26 Jun '17, 18:23) ayushagg311★

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

(26 Jun '17, 18:24) popo_popo3333★
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:

×832
×682

question asked: 26 Jun '17, 13:20

question was seen: 438 times

last updated: 26 Jun '17, 18:24