Boss fight
Feb. 5th, 2024 08:14 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sassa_nfYes, 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 to try one warrior at a time O(N) and search the best pair for that warrior, if we can do that search in O(log N), because then the complexity of the whole solution is just like sorting O(N * log N).
I tried various less sophisticated approaches, like, can we sort all warriors by some criterion, then find the best pair, like, the top two. I quickly found refutations for multiple approaches. Below may be the explanation why there is no single global order of warriors that works.
I start by answering a different question.
Given a warrior (h, d) acting as the first fighter, which of the other two warriors, (h_a, d_a) and (h_b, d_b), is better suited as the second fighter? (First vs second is important)
Ok, the goal is to optimise their battle scores, so warrior A is better than warrior B if h*(d_a+d)+h_a*d_a > h*(d_b+d)+h_b*d_b. This inequality in its turn can be simplified like so:
h*d_a+h_a*d_a > h*d_b+h_b*d_b
and
h*(d_a-d_b) > h_b*d_b-h_a*d_a
Without loss of generality, let's assume d_a > d_b.
Here's the first important finding. If h_a*d_a > h_b*d_b, this inequality holds for any h, because the left side is non-negative. That is, warrior A is always better.
However, if it is the other way around, that is, h_b*d_b > h_a*d_a, then there is a threshold value h, when warrior A is better, and in other cases warrior B is better. So warrior A is better, if h > (h_b*d_b-h_a*d_a)/(d_a-d_b). So you can see why it is not possible to sort all warriors according to a single criterion.
Now, if we can order all warriors by this "threshold level h", for which warrior A is better than warrior B (warrior B is better than C, etc)... Turns out, it is possible to do this, if we discard some warriors. It also turns out that the warriors that we discard are no good, as better alternatives exist.
1. Order all warriors by their damage, D, in descending order. So we have d_a > d_b.
2. Discard warrior B where h_a*d_a > h_b*d_b. That is because h > (some negative number), so warrior B is such that warrior A is better for any positive h.
3. For any three consecutive warriors A, B, C discard B, if threshold level h between warriors A and B h_ab is less than the level between warriors B and C, h_bc.
We can easily show that (3) represents the case where both A and B are better than C, A is better than B in all cases where A is better than C. That is, if h_ab < h_bc, then also h_ac < h_bc, given that d_a > d_b > d_c, and the products are ordered the other way around, h_a * d_a < h_b * d_b < h_c * d_c.
After these 3 steps we have warriors ordered by threshold level h. This makes the list of warriors searchable using binary search by level h of the first warrior.
4. Cover corner cases: when discarding warriors, compute pairing scores for the neighbouring warriors that we retain. So, in steps (2) and (3), when discarding B, update the best second and best score so far for warrior A.
This will ensure that when searching for best pair for any warrior except A, we can choose A as the second; but when looking for the best second for warrior A, we can't pair it up with himself, and the best candidates for A may not be present - they were discarded during construction.
This step is O(1), so no extra cost for storage or time.
So we end up with a subset of warriors like so: (h, d, best_second_so_far), ordered by threshold level h when warrior A is better than warrior B.
Given the sorted subset of warriors, which we construct once, and a candidate (h,d), go to the middle of the sorted subset of seconds, and check whether A or B is better between the neighbouring warriors in the middle - compute the threshold level h_ab, and see if h_ab > h. This tells us whether max is to the left or to the right from there. Continue with the left or right half recursively, as you normally would with binary search. If you landed on itself, use best_second_so_far stored with it. Now you've found the best second warrior and the best score you can get for that pair.
We repeat this for all warriors, and discover the best score in O(N * log N) time.
(Of course, cover corner cases where the sorted subset of warriors is of size 1.)
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 to try one warrior at a time O(N) and search the best pair for that warrior, if we can do that search in O(log N), because then the complexity of the whole solution is just like sorting O(N * log N).
I tried various less sophisticated approaches, like, can we sort all warriors by some criterion, then find the best pair, like, the top two. I quickly found refutations for multiple approaches. Below may be the explanation why there is no single global order of warriors that works.
I start by answering a different question.
Given a warrior (h, d) acting as the first fighter, which of the other two warriors, (h_a, d_a) and (h_b, d_b), is better suited as the second fighter? (First vs second is important)
Ok, the goal is to optimise their battle scores, so warrior A is better than warrior B if h*(d_a+d)+h_a*d_a > h*(d_b+d)+h_b*d_b. This inequality in its turn can be simplified like so:
h*d_a+h_a*d_a > h*d_b+h_b*d_b
and
h*(d_a-d_b) > h_b*d_b-h_a*d_a
Without loss of generality, let's assume d_a > d_b.
Here's the first important finding. If h_a*d_a > h_b*d_b, this inequality holds for any h, because the left side is non-negative. That is, warrior A is always better.
However, if it is the other way around, that is, h_b*d_b > h_a*d_a, then there is a threshold value h, when warrior A is better, and in other cases warrior B is better. So warrior A is better, if h > (h_b*d_b-h_a*d_a)/(d_a-d_b). So you can see why it is not possible to sort all warriors according to a single criterion.
Now, if we can order all warriors by this "threshold level h", for which warrior A is better than warrior B (warrior B is better than C, etc)... Turns out, it is possible to do this, if we discard some warriors. It also turns out that the warriors that we discard are no good, as better alternatives exist.
1. Order all warriors by their damage, D, in descending order. So we have d_a > d_b.
2. Discard warrior B where h_a*d_a > h_b*d_b. That is because h > (some negative number), so warrior B is such that warrior A is better for any positive h.
3. For any three consecutive warriors A, B, C discard B, if threshold level h between warriors A and B h_ab is less than the level between warriors B and C, h_bc.
We can easily show that (3) represents the case where both A and B are better than C, A is better than B in all cases where A is better than C. That is, if h_ab < h_bc, then also h_ac < h_bc, given that d_a > d_b > d_c, and the products are ordered the other way around, h_a * d_a < h_b * d_b < h_c * d_c.
After these 3 steps we have warriors ordered by threshold level h. This makes the list of warriors searchable using binary search by level h of the first warrior.
4. Cover corner cases: when discarding warriors, compute pairing scores for the neighbouring warriors that we retain. So, in steps (2) and (3), when discarding B, update the best second and best score so far for warrior A.
This will ensure that when searching for best pair for any warrior except A, we can choose A as the second; but when looking for the best second for warrior A, we can't pair it up with himself, and the best candidates for A may not be present - they were discarded during construction.
This step is O(1), so no extra cost for storage or time.
So we end up with a subset of warriors like so: (h, d, best_second_so_far), ordered by threshold level h when warrior A is better than warrior B.
Given the sorted subset of warriors, which we construct once, and a candidate (h,d), go to the middle of the sorted subset of seconds, and check whether A or B is better between the neighbouring warriors in the middle - compute the threshold level h_ab, and see if h_ab > h. This tells us whether max is to the left or to the right from there. Continue with the left or right half recursively, as you normally would with binary search. If you landed on itself, use best_second_so_far stored with it. Now you've found the best second warrior and the best score you can get for that pair.
We repeat this for all warriors, and discover the best score in O(N * log N) time.
(Of course, cover corner cases where the sorted subset of warriors is of size 1.)
no subject
Date: 2024-02-05 09:18 pm (UTC)У тебе спрацювало? В смислі, Фейсбук зарахував відповідь для всіх своїх 24 test cases?
До речі, мушу сказати, що як тільки ти почав писати про warriors and damage, я одразу втратив нитку розмови. Математично все просто, задачка симетрична відносно переіменування H в D і навпаки
no subject
Date: 2024-02-05 09:40 pm (UTC)Я теж тільки за математичний запис, але коли з'являється max, то воно вже того не варте, бо всілякі аналітичні підходи ламаються.
Мені warriors та damage потрібно лише для того, щоб рівняння записати h*(d_a+d)... і привести однакові члени. Якби був max, то що робити?