Editorial for Marcus Approximation

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.

Author: Plasmatic

The first subtask rewards any brute force too slow for the second subtask.

The second subtask rewards brute force solutions.

Time Complexity: $\mathcal{O}(Th^2)$ $O (T h^{2})$

The brute force can be optimized with a $2$ $2$ -pointer approach for the third subtask.

Time Complexity: $\mathcal{O}(Th)$ $O (T h)$

For the final subtask, we can try finding an approximate answer for cases with large $h$ $h$ . Observe that this question is similar to counting the number of lattice points under a quarter circle with radius $h$ $h$ . Thus, our approximation is $\frac{\pi h^2}{4}$ $\frac{π h^{2}}{4}$ .

For smaller $h$ $h$ , we can run the subtask 3 algorithm so our relative error stays small, and use our approximation for large $h$ $h$ .

Time Complexity: $\mathcal{O}(Th)$ $O (T h)$

Comments

There are no comments at the moment.