dreptunghi

Algoritmul, pas cu pas

Codul se citește recursiv, deci se parsează natural într-un arbore binar: nodurile interne sunt tăieturi (H sau V, cu poziția k), iar frunzele sunt *. De exemplu H5H3V2**V3**V5V2*** devine:

Intuiție

Codul descrie o serie de tăieturi care taie dreptunghiul în felii din ce în ce mai mici, iar * înseamnă „aici nu mai tai, scrie un număr". Dacă mai multe tăieturi consecutive merg în aceeași direcție (toate orizontale, sau toate verticale), ordinea în care le facem nu schimbă felul în care arată și se numerotează feliile finale — doar forma arborelui de parsare. Aici se ascunde toată „libertatea" problemei.

Ideea cheie

Parsăm codul într-un arbore binar (vezi diagrama de mai sus). Apoi observăm un fapt geometric: un șir maximal de tăieturi de același tip împarte o zonă în $g$ felii paralele, indiferent dacă în arbore lanțul e înclinat la stânga sau la dreapta. Un grup de $g$ felii poate fi obținut din orice arbore binar cu $g - 1$ tăieturi interne, adică în $C_{g-1}$ moduri ($C$ = numere Catalan). Toate aceste moduri dau aceeași partiție și aceeași numerotare — deci sunt coduri echivalente. De aici se obțin direct P=3 și P=4.