Editorial for COCI '22 Contest 5 #5 Zastave

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.

Let's look at the case n = 1. Let f(x) be the area of the flag with height x. It follows f(x) = x \sqrt{r^2-x^2}. The function is increasing until x = \frac{r}{\sqrt 2} and decreasing afterwards. It follows for x < \frac{r}{\sqrt 2} the solution is f(x) and for x \ge \frac{r}{\sqrt 2} the solution is \frac{r^2}{4}. Notice:

\displaystyle f'(x) = \sqrt{r^2-x^2}-\frac{x^2}{\sqrt{r^2-x^2}}

Now for the general case. The function f(x, r) will be analogous to the previous but for any r. Notice that the function f'(x) is decreasing on the interval (0, \frac{r}{\sqrt 2}). If we were solving the discrete version, it would be enough to always take the element which would increase our solution the most, the correctness of this algorithm relies on the fact that the discrete derivative is decreasing. In the continuous case, the analogous solution is to always move the point which currently has the largest derivative. But, it is easier to fix a derivative t and check whether the sum of x_i's such that f'(x_i, r_i) = t is smaller than S. Notice that for such x_i:

\displaystyle x_i = \sqrt{\frac{4r_i^2-t^2-\sqrt{(t^2-4r_i^2)^2-16(r_i^4-t^2 r_i^2)}}{8}}

Now it is enough to find such a t with binary search. It is enough to do 100 steps for the wanted precision. The final complexity is \mathcal O(100n). There are some edge cases that need to be checked by hand.


There are no comments at the moment.