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.
You will get TLE while reading the queries.
Why?
q <= n^2 <= 1e10, so you will need 40/50 seconds to read the input.
As mentioned in the blog qn<=1e5.
this
Thank you. I understand the first solution but could you please explain the second one in the editorial?
idk, I also used 1st solution back in the day, dont really understand second one
i implemented solution one and got wa for precision in the contest. :(((
If K does not exceed 1e7, I can solve this problem, but K is as high as 1e10.
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.
It makes sense. Thanks for explanation. The maximum depth for the answer is bound by logn right?
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.
hello
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.
In your explanation does n stand for the length of the arrays or largest possible denominator (ai,bj<=1e6)?
$$$n$$$ stands for the maximal denominator.
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.
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
Very nice. I thought solutions using floating point numbers wouldn't work due to precision but I guess that is not the case.
I havent test long enough to find a counter test. But you should definitely aware of the precision
wow, very good implementation.