Feb. 5th, 2024

Boss fight

Feb. 5th, 2024 08:14 pm
Yes, I've done facebook online problems once, just because I like problems like that.

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 )

Profile

sassa_nf

March 2025

S M T W T F S
      1
23 4567 8
9101112131415
16171819202122
23242526272829
3031     

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 13th, 2025 03:04 am
Powered by Dreamwidth Studios