← CSES Better

Monsters

INOI · 2024 · Indian National Olympiad in Informatics · Problem 1

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

interval-dp · game-theory · range-queries

The organizer’s problem statement is available at the official source link.

interval game

A survivor must win both sides of an interval

Adjacent monsters battle by Fire/Water/Grass dominance; count indices that can survive each queried subrange.

State table
Left intervalRight intervalCombine
survivor set Lsurvivor set Rcyclic-dominance rule
  1. 1

    Track survivor types

    For each interval, track which monster types can be its final survivor.
  2. 2

    Combine subranges

    Split a range into two surviving subranges, then apply the dominance rule at their boundary.
  3. 3

    Answer each interval

    Count feasible survivor indices for each query interval.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.