← CSES Better

Domino Solitaire

INOI · 2008 · Indian National Olympiad in Informatics · INOI0802

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

grid · tiling · dynamic-programming · optimization

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

domino tiling

Tile the two-row grid for maximum score

Cover every cell of the 2-by-N grid exactly once with 2-by-1 tiles. A tile scores the difference between its two covered values.

Problem grid; highlighted cells show the illustrated path
top: a1a2...
bottom: b1b2...
  1. 1

    Place legal tiles

    Each tile covers two adjacent cells; tiles cannot overlap and every cell must be covered.
  2. 2

    Score each tile

    A tile contributes the larger covered value minus the smaller covered value.
  3. 3

    Maximize the total

    Choose a complete tiling with the greatest sum of tile scores.
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.