← CSES Better

Train ride

INOI · 2006 · Indian National Olympiad in Informatics · INOI0602

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

intervals · ordering · longest-chain

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

compatible routes

Chain the largest number of train routes

Routes are intervals on the ordered stations. Transfers stay in the same direction, overlap at a station, and move to a route with a later start. Interval positions below are schematic.

route a: [s_a,e_a]
0–4
route b: [s_b,e_b]
2–6
route c: [s_c,e_c]
5–8
  1. 1

    Model each route

    A route (i,j) serves stations from i through j, where i < j.
  2. 2

    Transfer legally

    Continue in the same direction and switch only to a route whose start is later than the current route start.
  3. 3

    Maximize route count

    Find the longest valid route chain beginning with a route from station 1.
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.