INOI 2024 Monsters
Algorithms Used: Binary Search, Prefix Sums
In this problem, we are given the positions of Fire (F), Grass (G) and Water (W) monsters represented by a string of F, G, and W characters. A monster can attack any adjacent monster. The winner of each attack is determined as follows:
Fire beats Grass
Grass beats Water
Water beats Fire
In an attack consisting of two monsters of the same type, either one can win. We need to determine the number of possible winners of the entire string.
For each monster, we need to see if it can emerge as the ultimate winner or not. Let's say this monster is fire. In order for fire to win, all the water monsters on its left and right somehow need to die. This can only be done if there is a grass monster also present on the same side as the water monster because then the grass monster will kill all the water monsters and finally the fire monster can finish off the grass monster. So, for each monster, if a monster against which it loses is present on its left, then the monster against which it wins must also be present on its left and the same goes for the monster's right.
Let's assume, like in the example above, we're checking to see if a particular fire monster can win. We store the positions of each type of monster and then binary search (upper_bound in C++) on the positions of the water monster positions to check if there is one present to fire's right and if there is one, we check if there is also a grass monster present using the same technique. Do the same for the left side of the monster. If everything checks out, then this monster can emerge as the ultimate winner and we increment the answer by 1.
Comments