coolboy19521's blog

Find k-th fraction
By coolboy19521, history, 10 months ago, In English

n<=1e5, q<=n^2, k<=n^2, qn<=1e5

a and b are integer arrays of length n. q queries are asked and you need to find k-th largest fraction among ai/bj (0<=i,j<n). You can do it offline.

(Note: binary searching on ai/bj as a float/double/long double does not work due to precision. I could not find any judge to submit the solution sorry.)

Edit: you need to output the nominator and denominator as the solution for each query.

Edit: ai,bi<=1e6

Edit: Apparently solutions binary searching float/double/long double work. Sorry for confusion.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
10 months ago, hide # |
← Rev. 2  
Vote: I like it -9 Vote: I do not like it

You will get TLE while reading the queries.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

this

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

If K does not exceed 1e7, I can solve this problem, but K is as high as 1e10.

→ Reply
»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It's an application of the Stern-Brocot tree. For each query, you stand at a node in the Stern-Brocot tree, and as you do in binary search, you can count how many fractions are present that are smaller than it and accordingly you go left or right in the tree.

How do you count the number of fractions smaller than a given fraction? You can iterate over the a array and do a binary search (or I think two pointers) over the b array.

This is $$$O(n \log n)$$$ or $$$O(n \log^2 n)$$$ per query so the total complexity is $$$O(qn \log^2 n)$$$. Note that nq≤10^5, so this should pass.

→ Reply
  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It makes sense. Thanks for explanation. The maximum depth for the answer is bound by logn right?

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      Oh, that's a good point. I assumed the search the way I described works in $$$O(\log n)$$$ time, but it appears that the length of the path to a fraction $$$\frac{p}{q}$$$ can be $$$O(p+q)$$$. I think that means my solution as described won't work.

      The article I linked does describe a way to implement the search in $$$O(\log(p+q))$$$ time. I haven't checked if my method works with that though.

      → Reply
»
10 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

hello

→ Reply
»
10 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Firstly, binary search to find the search interval $$$(\frac{i}{n}, \frac{i + 1}{n})$$$. Then for each denominator $$$q$$$ there is no more than one fraction falls into the interval. List out all such fractions and do binary search again.

→ Reply
  • »
    »
    10 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    In your explanation does n stand for the length of the arrays or largest possible denominator (ai,bj<=1e6)?

    → Reply
    • »
      »
      »
      10 months ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      $$$n$$$ stands for the maximal denominator.

      → Reply
      • »
        »
        »
        »
        10 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Ok, I got it. I also thought of a similar solution, but my first binary search was searching i/n where n is the minimal among b. That's why it was not guaranteed for each denominator the number of fractions falling into range was manageable. Thanks for the explanation.

        → Reply
»
10 months ago, hide # |
← Rev. 4  
Vote: I like it +3 Vote: I do not like it

My approach: Binary search to find the smallest real number that has k smaller fractions. Then find nearest fraction to that real number.

I managed to implement it using binary search + two pointers to optimize. Got accepted on Gym link

Code

→ Reply