Hello!
I uploaded 2022-2023 Winter Petrozavodsk Camp, Day 2: GP of ainta to the CF Gym.
It is the collection of problems authored by ainta in 2015-2022. This contest is not related to me, I'm just stealing his contribution points.
Thanks to TLEwpdus, who found a solution to one of the problems.
Enjoy!
List of relevant previous contests
It seems there are many problems similar to problem H (GP of Moscow 2018-2019 B, Ptz Winter 2022 Yandex Cup D).
All three problems can be solved by $$$O(n \log^2 X)$$$ ternary search, but there exist solutions in $$$O(n \log X)$$$ and even $$$O(n)$$$. I can't tell if they are actually fast, or if they are numerically stable.
What is the best solution in terms of execution time, floating point accuracy, and generalizability (to $$$k$$$ dimensions)?
I solved H using an $$$O(n)$$$ solution. Simply said, the task can be modeled as an LP task with $$$4$$$ variables and $$$2n$$$ constraints. Thus, we can use methods to solve low-dimensional LP in linear time. Combining Seidel's method and Clarkson's method, this can be done in $$$O(d^2 n + \text{the rest is not really important whatsoever in low dimensions})$$$. When some paper says that low-dimensional LP can be done in $$$O(n)$$$, they're usually pointing towards this. But yet, builtin floating point types are not the best for numerical stability, so my solution's implementation (shamelessly stolen from dacin21's codebook) uses bigints and rational arithmetic. And then, this turns out to be slower than the ternary-search solution (but just enough to fit the TL).
I have not tested whether this works well on higher dimensions, but I believe it should be fine for at most $$$5$$$ variables in the LP formulation. If we have more than $$$5$$$ variables, then I would rather pray for the Simplex algorithm to work very well.
I made a bet that you would reply in 1 hour :)
Great work!
Are you sure that you have uploaded Problem I correctly (specifically, the tests)? UPDATE: ignore this, apologies; the problem was that the first test is not the sample. The tests have been uploaded, my mistake.