Graph Tiling - Repovive Standard Round 3 | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/f

Reduce to a tree first

Ignore the extra edges for a moment. Root the tree at

1

and define two states for each node

u

$f[u]$ — configurations in the subtree where

u

is free (not matched upward).

u

can be a singleton or matched to exactly one child.

$g[u]$ — configurations where

u

is matched to its parent. Then

u

cannot pair with any child — every child subtree must independently cover itself (each child

v

can be free but NOT matched upward).

Transitions

For a leaf:

f[u] = 1 \quad \text{(singleton)} \qquad g[u] = 1 \quad \text{(no children — empty product)}

For an internal node with children set

C

$g[u]$ : $u$ is matched upward → no child matched to $u$ . Every child must be free: $g[u] = \prod_{v \in C} f[v]$

$f[u]$ : $u$ is free → either singleton or matched to exactly one child: $f[u] = \underbrace{\prod_{v \in C} f[v]}_{\text{singleton}} + \sum_{v \in C} \left( g[v] \cdot \prod_{w \in C,\; w \neq v} f[w] \right)$

The tree answer is

f[\text{root}]

(root has no parent).

Check your understanding: derive these on a path of length

3

and verify the tilings count by hand.

Reduce to a tree first

Ignore the extra edges for a moment. Root the tree at

1

and define two states for each node

u

$f[u]$ — configurations in the subtree where

u

is free (not matched upward).

u

can be a singleton or matched to exactly one child.

$g[u]$ — configurations where

u

is matched to its parent. Then

u

cannot pair with any child — every child subtree must independently cover itself (each child

v

can be free but NOT matched upward).

Transitions

For a leaf:

f[u] = 1 \quad \text{(singleton)} \qquad g[u] = 1 \quad \text{(no children — empty product)}

For an internal node with children set

C

$g[u]$ : $u$ is matched upward → no child matched to $u$ . Every child must be free: $g[u] = \prod_{v \in C} f[v]$

The tree answer is

f[\text{root}]

(root has no parent).

Check your understanding: derive these on a path of length

3

and verify the tilings count by hand.

8F. Graph Tiling

Hint 1

8F. Graph Tiling

Hint 1

Reduce to a tree first

Transitions

Reduce to a tree first

Transitions