# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Manuj Nanthan

Tester: Aryan, Takuki Kurokawa

Editorialist: Pratiyush Mishra

# DIFFICULTY:

Easy

# PREREQUISITES:

None

# PROBLEM:

You are given an array B containing N integers, each of which is either −1 or a non-negative integer. Construct **any** integer array A of length N such that:

- 0≤A_i≤10^9 for every 1≤i≤N
- If B_i≥0, A must satisfy mex(A_1,A_2,…,A_i)=B_i
- Otherwise, B_i=−1 , which means there is no constraint on mex(A_1,A_2,…,A_i)

If there does not exist any array satisfying the constraints, print −1 instead.

**Note:** The mex of a set of non-negative integers is the smallest non-negative integer that does not belong to it. For example,

mex(1,2,3)=0 , mex(0,2,4)=3 , mex(0,0,0)=1

# Quick Explanation

Take two sets x and y. x contains integers coming in B_i as positive integers and y contains the remaining integers from 0 to N-1.

Construct greedily from B_1 to B_n.

If B_i is -1 , print the elements from y set. else If B_i is positive , print the previous element of set x.

In this way we can construct valid array.

Note that it won’t be possible to create array A if for any i we have B_i \geq (i+1) or for any i, there is a B_j such that 0 \leq j < i and B_j > B_i

# Explanation

There can be multiple ways to go about its implementation, one of which is discussed here.

First we check if for any i, if there exists any B_j such that 0 \leq j < i and B_j >B_i. If such B_j exists then it won’t be possible to create array and we would return -1.

Now we would create two separate sets slots and elements where slots represents the available slots of A that needs to be filled, while elements represents the available elements that can be used to fill the slots.

Let’s talk about the way we will go about filling. We will first remove duplicates from array B, i.e say array B = \{-1,1,1,1,2\}, then we would change duplicates to -1, so B would become \{-1,1,-1,-1,2\}. This way we would have increasing order of positive numbers and -1s. Now we will loop through array and upon reaching a positive value, we would loop through all available slots in A in increasing order and fill elements from set elements till Mex(A_1,A_2.....A_i) becomes B_i. If for any case we do not have slots available to fill then also it won’t be possible to create array A and we would return -1.

# TIME COMPLEXITY:

In this algorithm, we iterate through the array and when we find any positive B_i, we loop through all the available slots available and remove them from set after filling it. Thus we are basically iterating the array twice and in second iteration of going through availble slots, we are accessing from a set that takes O(logN) time, thus total time complexity would be O(NlogN).

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester-1’s Solution

Tester-2’s Solution