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

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

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

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

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

Repovive

Graph Interval Connectivity - Repovive Premier Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

6G. Graph Interval Connectivity

3500 ptstype :zen to enter zen mode

by Hamed Ghaffari

Time: 2sMemory: 256 MB

Page 1

Think about the $n-1$ gaps between consecutive vertices:

$1|2,\ 2|3,\ \ldots,\ (n-1)|n$ .

If the final graph is connected, then for every gap $k$ , there must be at least one chosen edge with one endpoint at most $k$ and the other endpoint greater than $k$ . Otherwise, the vertices $1,\ldots,k$ would be completely separated from the vertices $k+1,\ldots,n$ .

For operation $i$ , we can choose $u_i$ from $[l_i,r_i]$ , while the other endpoint is fixed as $v_i$ . Since $l_i \le v_i \le r_i$ , this operation is able to cross gap $k$ exactly when

$l_i \le k < r_i$ .

So the problem is closely related to covering all gaps $1,\ldots,n-1$ by distinct operations.

Think about the $n-1$ gaps between consecutive vertices:

$1|2,\ 2|3,\ \ldots,\ (n-1)|n$ .

For operation $i$ , we can choose $u_i$ from $[l_i,r_i]$ , while the other endpoint is fixed as $v_i$ . Since $l_i \le v_i \le r_i$ , this operation is able to cross gap $k$ exactly when

$l_i \le k < r_i$ .

So the problem is closely related to covering all gaps $1,\ldots,n-1$ by distinct operations.