AvadaKedavara's blog

Rate the difficulty of this problem from INOI 2024.
By AvadaKedavara, history, 5 months ago, In English

Problem Name: Monsters.

There are N Monsters numbered from 1 to N , each of type Fire, Water or Grass represented by a string A of length N . When two Monsters battle each other, one of them wins according to the following rules: • A Fire Monster always defeats a Grass Monster. • A Water Monster always defeats a Fire Monster. • A Grass Monster always defeats a Water Monster. • In a battle between two Monsters of the same type, either one can win. Answer Q queries of the following form: if the Monsters Lj ...Rj are standing in a line from left to right, and repeatedly, two adjacent Monsters battle each other with the loser leaving the line, how many Monsters can be the last remaining Monster in at least one valid sequence of events?

Problem Link: Monsters

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

900 maybe 1100

→ Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If there are 3 monsters, does the 2nd monster battle 1st monster or 3rd monster?

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If there are three monsters, First the first and the second monsters fight, whoever loses gets kicked out and there will be two monsters left.. whoever is left fights the third monster,

    → Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you can arbitrarily choose which pair of adjacent Monsters to battle, I think a Fire Monster $$$i$$$ can win if and only if:
- In the left side of $$$i$$$, there is at least one Grass Monster, or there is no Water Monster.
- In the right side of $$$i$$$, there is at least one Grass Monster, or there is no Water Monster.
We can use data structures to answer queries.

Please correct me if I'm wrong.

If this is intended, I'd rate it 1800+. But according to previous comments, this approach maybe severely over-complicated.

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you didn't understood the problem, please read the full problem statement.

    → Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    Yes, this is intended (as an INOI 2024 silver medalist). No, it is not overcomplicated; the official editorial uses the same solution.

    The previous comments are probably referring to solving the $$$Q=1$$$ subtask, which is actually quite easy and doesn't need any data structures (and surprisingly it yields you $$$84$$$ points)

    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Your overall approach is correct but you don't need data structures. You can simply use prefix sums to count the number of Fire Monsters between the first Water Monster and first Grass Monster, and so on. (I am the author of the problem.)

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AvadaKedavara (previous revision, new revision, compare).

→ Reply