← CSES Better

Count Permutations Matching a Range-Minimum Table

ZIO · 2023 · Zonal Informatics Olympiad · P3

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

permutations · range-minimum · combinatorics

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

interval minimum tree

Every interval specifies its minimum index

The supplied table names the index of the minimum value in every contiguous range; count consistent permutations.

State table
Interval [l,r]Required minimumStructure
[l,r]argmin(l,r)nested Cartesian tree
  1. 1

    Read interval minima

    Read each interval’s required minimum position.
  2. 2

    Constrain the Cartesian tree

    Use nested interval constraints to define the compatible Cartesian-tree order.
  3. 3

    Count compatible orders

    Count permutations that satisfy every interval entry.
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.