Editorial for ICPC NEERC 2012 C - Caravan Robbers - Olympiads Online Judge

Editorial for ICPC NEERC 2012 C - Caravan Robbers

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Sort all intervals by $a_i$ $a_{i}$ (they also get ordered by $b_i$ $b_{i}$ automatically). It is easy to prove that the new intervals must follow in the same order
- The solution is the minimum of $\frac{b_j-a_i}{j-i+1}$ $\frac{b_{j} - a_{i}}{j - i + 1}$ for all pairs of $i$ $i$ and $j$ $j$ when $i \le j$ $i \leq j$ , but this solution is $\mathcal O(n^2)$ $O (n^{2})$ and will not fit into the time limit.
The correct solution is to use binary search to find the answer length and then find the closest simple irreducible fraction $p/q$ $p / q$ to this answer

Comments

There are no comments at the moment.