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

$ curl repovive.com/contests/7/problems/g

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

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

$ curl repovive.com/contests/7/problems/g

Repovive

Removing Graph via a Matching - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

7G. Removing Graph via a Matching

3500 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

Page 1

We want to count valid deletion sequences. The main difficulty is that the graph edges are not enough by themselves. The order of deletions also matters.

Think about one operation on an edge $(u,v)$ with $u < v$ . This operation is allowed only after every vertex between them, meaning $u+1,u+2,\ldots,v-1$ , has already been deleted.

So if vertices $u$ and $v$ are paired together in the final sequence, then the whole interval $(u,v)$ must be completely deleted before deleting $u$ and $v$ .

This creates a recursive interval structure.

For example, suppose the first vertex of an interval is $l$ , and in the final sequence it is deleted together with vertex $p$ . Then edge $(l,p)$ must exist. Also, before deleting $(l,p)$ , all vertices from $l+1$ to $p-1$ must already be deleted.

The vertices from $p+1$ to $r$ are outside this edge. They can be deleted before or after different operations inside $[l,p]$ , as long as their own rules are respected.