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

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

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

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

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

Repovive

Maximum MEX - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

7D. Maximum MEX

2000 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

Page 1

We need to maximize the mex of the array.

Remember that the mex is the first non-negative integer that is missing. So if the final mex is at least $m$ , then the final array must contain all numbers

$0,1,2,\ldots,m-1$ .

Therefore, instead of trying to directly maximize the mex, we can check numbers from small to large and see whether we can create them one by one.

The operation is simple: we can replace some value $a_i$ by $a_i+k$ . If we apply this operation many times, the value can become

$a_i, a_i+k, a_i+2k, \ldots$ .

So an element with initial value $a_i$ can become a number $x$ if and only if both of these are true:

$x \ge a_i$
$x \equiv a_i \pmod k$

This means every element keeps the same remainder modulo $k$ forever.