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

$ curl repovive.com/contests/3/problems/h

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

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

$ curl repovive.com/contests/3/problems/h

Repovive

Max Mex - Repovive Premier Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

3H. Max Mex

3500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Page 1

We first simplify the definition of beauty.

For a subarray $b$ , a value $k$ is valid iff $k \le \min(b)$ . After subtracting such a $k$ , the resulting array contains $0$ (take $k=\min(b)$ ), and maximizing MEX is clearly best when we make the minimum equal to $0$ .

So the beauty of a subarray equals: the largest $m$ such that the subarray contains all values $\min(b), \min(b)+1, \dots, \min(b)+m-1$ . Equivalently, if the minimum is $x$ , then beauty is the maximum $y$ such that all numbers $x, x+1, \dots, x+y-1$ appear inside the subarray.

We first simplify the definition of beauty.