By Lindsey L. (11th Grade)
https://codeforces.com/contest/2178/problem/D 12/30/25
Concepts: sorting, greedy
We notice that whenever two elves attack each other, at least one of them will die. Since we can only stop when all remaining elves have attacked, there must be at least n / 2 rounds, so if
m > n / 2 it is impossible.
When m > 0, we can leave the strongest m elves. They can attack m other elves, but there might be some elves remaining. We can start with the weakest elf, who will attack the second weakest elf and die, and so on, until there are 2m elves remaining. Then, we can pair the elves up and leave m elves alive. Since all elves will attack at most once and all start with distinct health and attack strengths, we don’t need to worry about the case that they both die.
For the case where m = 0, we need a different strategy because we need to make sure that the strongest elf will die. This is only possible when the sum of the strengths of all the elves is greater than the strongest elf. We can choose k of the elves to attack the strongest elf. For the other elves, we can do something similar to the m > 0 case where the weakest attacks the next weakest. The rest of the elves will attack the strongest elf. They will all die since their health is lower than the strongest elf’s attack, and the strongest elf should die right after the last elf attacks.
