Boss fight
Feb. 5th, 2024 08:14 pmYes, I've done facebook online problems once, just because I like problems like that.
So, like here: https://malyj-gorgan.dreamwidth.org/187069.html
That's the mathematical notation. The statement is really about various warriors with damage D and health H fighting a "boss", and you've got to choose the best pair. The fighting arrangement is such that while the first warrior is receiving damage from the "boss" (health declines), both warriors can damage the boss. This explanation is here simply to explain the terminology I use in my solution.
I don't know whether there is a better solution, but here's my approach that worked well enough.
It is obvious that comparing each with each finds a solution, but given the possible magnitude of inputs it becomes intractable. So if we sort the warriors in some way, this would become tractable. We can also afford( ...spoiler )
So, like here: https://malyj-gorgan.dreamwidth.org/187069.html
N ∈ [2, 5×105]; i,j ∈ [1, N]; di, hi ∈ [1, 109];
maximize:
di hi + dj hj + max(di hj, dj hi)
That's the mathematical notation. The statement is really about various warriors with damage D and health H fighting a "boss", and you've got to choose the best pair. The fighting arrangement is such that while the first warrior is receiving damage from the "boss" (health declines), both warriors can damage the boss. This explanation is here simply to explain the terminology I use in my solution.
I don't know whether there is a better solution, but here's my approach that worked well enough.
It is obvious that comparing each with each finds a solution, but given the possible magnitude of inputs it becomes intractable. So if we sort the warriors in some way, this would become tractable. We can also afford( ...spoiler )